Linked Lists

Linked List - Insert at Head

O(1)

Linked List - Remove from head

O(1)

Linked List - Insert at tail

O(1) (with tail pointer)

O(n) (without tail pointer)

Linked List - Remove from tail

O(n)

Linked List - Search/Contains

O(n)

Doubly Linked List - Insert at head

O(1)

Doubly Linked List - Remove from head

O(1)

Doubly Linked List - Insert at tail

O(1)

Doubly Linked List - Remove from tail

O(1)

Doubly Linked List - Search/Contains

O(n)

Linked List - Pros

• Lower memory overhead compared to doubly linked lists and arrays

• Can grow dynamically in size

Linked List - Cons

• Removal of tail is inefficient O(n)

• Can only traverse in the forward direction

• No direct access to previous nodes

• O(n) for searching

Doubly Linked List - Pros

• Can perform operations at both ends efficiently O(1)

• Can traverse in both directions

Doubly Linked List - Cons

• High memory overhead

• More complex insertion and deletion operations

General Linked List Operations

• peekHead()

• peekTail()

• insertAtHead()

• insertAtTail()

• deleteFromHead()

• deleteFromTail()

• contains()