Linear DS

Linked Lists

A foundational sequential data structure utilizing dynamic pointer connections.

What is Linked Lists?

A Linked List is a linear data structure where elements are stored in nodes. Each node contains a data field and a reference (pointer) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, allowing for efficient insertions and deletions at any point without shifting elements.

Key Characteristics:

  • Nodes are dynamically allocated in memory
  • Pointers connect nodes sequentially
  • Efficient insertion and deletion (O(1)) at known locations
  • Sequential access only — no random index access

Complexity Analysis

Avg Time Complexity: O(n) for Search/Access, O(1) for Insert/Delete (at cursor)
Space Complexity: O(n) auxiliary space
Best Case: O(1) (operating at the head of the list)
Worst Case: O(n) (traversing to the tail of the list)

How it Works Step-by-Step

  1. Initialize: Create a Head pointer referencing NULL.
  2. Insert at Head: Create node, point its NEXT to current Head, and update Head to the new node.
  3. Insert at Tail: Traverse from Head until NEXT is NULL, then point that node's NEXT to the new node.
  4. Delete Node: Point the previous node's NEXT directly to the target node's NEXT, skipping and freeing the target.

Code Implementation

Worked Trace Example

Let's trace adding a node 30 to a list 10 ➔ 20:

1. Create node 30: [30 | NULL]
2. Traverse to index 1 (node 20)
3. Point node 30 NEXT to node 20's NEXT (NULL)
4. Point node 20 NEXT to node 30
Result: 10 ➔ 20 ➔ 30