Linked Lists

Advantages

• Dynamic Size: Linked lists can grow and shrink in size dynamically in constant time, which is useful for applications where the number of elements is not known in advance.
• Efficient Insertions/Deletions: Inserting or deleting elements in a linked list is generally more efficient than in an array, especially for large lists, as it does not require shifting elements.
• Memory Utilization: Linked lists can utilize memory more efficiently than arrays, as they do not require a contiguous block of memory.

Disadvantages

• Memory Overhead: Each element in a linked list requires additional memory for storing pointers, which can lead to higher memory usage compared to arrays.
• Sequential Access: Linked lists do not support random access, meaning that accessing an element requires traversing the list from the head to the desired node, which can be slower than accessing an element in an array.
• Cache Locality: Linked lists do not have good cache locality, as their elements may be scattered throughout memory, leading to more cache misses and slower access times.

Doubly Linked List

A node contains a pointer to the next node and a pointer to the previous node. This allows for traversal in both directions.

graph LR
    A["Node A"]
    B["Node B"]
    C["Node C"]
    D["Node D"]

    A -- prev --> Null1["Null"]
    A -- next --> B
    B -- prev --> A
    B -- next --> C
    C -- prev --> B
    C -- next --> D
    D -- prev --> C
    D -- next --> Null    

Memory efficient version

Each node contains only one pointer field to traverse back or front on the list. This pointer contains the xor of pointer to next node and previous node.

Circular Linked List

Each node contains a pointer to the next node similar to single-linked lists, except the next of last node points to first node.

graph LR
    A["Node A"]
    B["Node B"]
    C["Node C"]
    D["Node D"]

    A --> B
    B --> C
    C --> D
    D --> A    

Can be used to implement stacks and queues.

Unrolled Linked List

An unrolled linked list stores multiple elements in each node(block). In each block, circular linked list is used to store the elements. Each block except the last one contains exactly \(\sqrt{n}\) elements. This allows for searching in O(\(\sqrt{n}\)) time.

Skip Lists

Skip lists are a probabilistic alternative to balanced trees. It is basically a linked list with additional pointers to skip over some nodes.

Performance If a second pointer pointing 2 nodes ahead is added to every node, the number of comparisons goes down to \(n/2 + 1\). If every node with \(i\) pointers points to \(2*i - 1\) nodes ahead then the number of comparisons goes down to O(log n), while number of pointers have only doubled (n + n/2 + n/4 + n/8 + ... = 2n).

Operations

Method	Array	Linked List	Double LL
Indexing	O(1)	O(n)	O(n)
Insert/deletion at beginning	O(n)	O(1)	O(1)
Insert at end	O(1)	O(n)	O(n)
Deletion at end	O(1)	O(n)	O(n)
Insert in middle	O(n)	O(n)	O(n)
Deletion in middle	O(n)	O(n)	O(n)
Wasted space	0	O(n)	O(n)