Linked list

Definition

Data stored in nodes with each node pointing to another one. Two types:

• Singly linked: data + pointer to next node
• Doubly linked: data + pointer to both previous and next nodes
• Circular linked: tail points to the head

Applications

Used for implementation of stacks, queues (performance for insertion/deletion), trees and graph.

Pros and Cons

Pros:

• Fast insertion/deletion of elements.
• Efficient memory utilization.
• Can grow and shrink during runtime.

Cons:

• Consumes more memory because of pointer.
• Slow access to nth element.
• No random access.

Complexity

Operation	Complexity
Access	$O(n)$
Search	$O(n)$
Append	$O(1)$
Insertion	$O(1)$
Delete	$O(1)$

• Access: traverses structure until given index is reached.
• Search: traverses structure until element is found.
• Append: change value of pointers of neighbours.
• Insertion: same as append.
• Deletion: delete element and reorganise pointers of previous neighbours.