Linked list

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Rather, it is a dynamic data structure comprised of nodes pointing to other nodes which together represent a sequence. Each node contains a single item and a link to the node containing the next item. The last node in the linked list has a null value.

Advantages:

• No capacity limit (provided there is enough memory)
• Easy to insert/delete an item (no need to “shift” other items)

Disadvantages:

• No random access (must “walk down” the list to access an item)
• There is memory overhead for the links

Where are linked lists used?

• Used in many list, queue, and stack implementations
• Great for creating circular lists
• Can easily model real world objects such as trains
• Used in separate chaining
• Often used in the implementation of adjacency lists for graphs

Terminology

• Head: the first node in a linked list
• Tail: the last node in a linked list
• Pointer: reference to another node
• Node: an object containing data and pointer(s)

Singly vs doubly linked lists

Singly linked lists only hold a reference to the next node. Doubly linked lists hold a reference to the next and previous nodes and can therefore be traversed in both directions.

	Pros	Cons
Singly linked	Uses less memory, simpler implementation	Cannot easily access previous elements
Doubly linked	Can be traversed backwards	Takes 2x memory

Complexity analysis of linked lists

	Singly linked	Doubly Linked
Search	$O(n)$	$O(n)$
Insert at head	$O(1)$	$O(1)$
Insert at tail	$O(1)$	$O(1)$
Remove at head	$O(1)$	$O(1)$
Remove at tail	$O(n)$	$O(1)$
Remove in middle	$O(n)$	$O(n)$