# 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)$