Linked Lists in Action

After understanding arrays, which store data in contiguous memory, it’s time to explore a data structure that breaks free from that constraint: Linked Lists. Linked lists offer a flexible way to store collections of data, making insertions and deletions incredibly efficient in many cases, especially when compared to arrays.

Unlike arrays, which rely on indices and physical proximity, linked lists rely on pointers to establish logical connections between elements.

🔗 What is a Linked List?

A linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, each element (called a node) points to the next element in the sequence.

Core Components:

• Node: The fundamental building block. Each node typically contains:
  • Data: The actual value or information being stored.
  • Pointer (or Reference): A link to the next node in the sequence.
• Head: A pointer to the very first node of the list. If the list is empty, the head is NULL (or equivalent).
• Tail: (Optional, but common in many implementations) A pointer to the last node of the list, allowing for O(1) appends.

Analogy: Imagine a treasure hunt where each clue (node) tells you where to find the next clue (pointer) until you reach the final treasure (the last node). The clues aren’t necessarily physically next to each other, but they form a logical chain.

➡️ Singly Linked List

The most basic type of linked list, where each node has a pointer only to the next node in the sequence. Traversal is only possible in one direction (forward).

Operations & Complexity:

• Access (by index): O(N) - You must start from the head and traverse N nodes to reach the N-th element.
• Insertion (at beginning): O(1) - Just update the head pointer.
• Insertion (at end): O(1) if you maintain a tail pointer, O(N) otherwise (must traverse to find the last node).
• Insertion (in middle): O(N) - You need to traverse to the node before the insertion point.
• Deletion (at beginning): O(1) - Just update the head pointer.
• Deletion (at end): O(N) - Must find the second-to-last node to update its pointer.
• Deletion (in middle): O(N) - Must traverse to the node before the deletion point.
• Search: O(N) - Must traverse the list until the item is found.
• Space Complexity: O(N) - Stores N nodes, each with data and a pointer.

        
          
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
  int data;
  struct Node* next;
} Node;

// Function to add a new node at the beginning of the list
Node* add_to_head(Node* head, int new_data) {
  // 1. Allocate new node
  Node* new_node = (Node*) malloc(sizeof(Node));
  if (new_node == NULL) { /* Handle error */ return head; }

  // 2. Put in the data
  new_node->data = new_data;

  // 3. Link the new node to the old head
  new_node->next = head;

  // 4. Move the head to point to the new node
  head = new_node;
  return head; // Return new head
}

// Function to print the list
void print_list(Node* node){
printf("List: ");
while (node != NULL) {
  printf("%d -> ", node->data);
  node = node->next;
}
printf("NULL\n");
}

// Main
int main() {
  Node* head = NULL; // Start with an empty list

  head = add_to_head(head, 10); // List: 10 -> NULL
  print_list(head);
  head = add_to_head(head, 20); // List: 20 -> 10 -> NULL
  print_list(head);
  head = add_to_head(head, 30); // List: 30 -> 20 -> 10 -> NULL
  print_list(head);

  // Free allocated memory (important in C!)
  Node* current = head;
  while (current != NULL) {
      Node* next = current->next;
      free(current);
      current = next;
  }

  return 0;
}
        
      

        
          
class Node:
def __init__(self, data):
  self.data = data
  self.next = None # Pointer to the next node

class LinkedList:
def __init__(self, head=None):
    self.head = head # Head of the list.

def add_to_head(self, new_data):
  new_node = Node(new_data)
  new_node.next = self.head
  self.head = new_node

def print_list(self):
  current = self.head
  print("List: ", end="")
  while current:
    print(f"{current.data} ->  ", end="")
    current = current.next
  print("NULL")

# Main for demonstration
my_list = LinkedList()
my_list.add_to_head(10) # List: 10 -> NULL
my_list.print_list()
my_list.add_to_head(20) # List: 20 -> 10 -> NULL
my_list.print_list()
my_list.add_to_head(30) # List: 30 -> 20 -> 10 -> NULL
my_list.print_list()
    
        
      

        
          
class Node {
constructor(data) {
  this.data = data;
  this.next = null;
}
}

class LinkedList {
constructor() {
  this.head = null;
}

addAtHead(newData) {
  const newNode = new Node(newData);
  newNode.next = this.head;
  this.head = newNode;
}

printList() {
  let current = this.head;
  let result = "List: ";
  while (current) {
    result += ${current.data} ->;
    current = current.next;
  }
  result += "NULL";
  console.log(result);
}
}
// Main for demonstration
const myList = new LinkedList();
myList.addAtHead(10); // List: 10 -> NULL
myList.printList();
myList.addAtHead(20); // List: 20 -> 10 -> NULL
myList.printList();
myList.addAtHead(30); // List: 30 -> 20 -> 10 -> NULL
myList.printList();
    
        
      

Practical Usages:

• Implementing Stacks and Queues: Linked lists allow O(1) push/pop for stacks (at head) and enqueue/dequeue for queues (with head/tail pointers).
• Browser History (forward/backward): Each page is a node, allowing traversal.
• Polynomial Representation: Each term in a polynomial can be a node (coefficient, exponent).
• Memory Management: Free lists in low-level memory allocators.

Note: The biggest advantage of linked lists is their flexibility for insertions and deletions. You don’t need to shift elements around in memory, only redirect pointers. This makes them ideal for scenarios where the list size changes very frequently, or elements are often inserted/deleted in the middle.

↔️ Doubly Linked List

A doubly linked list is an extension of a singly linked list where each node has two pointers: one to the next node and one to the previous node. This allows for traversal in both forward and backward directions.

Characteristics:

• next pointer: Points to the subsequent node.
• prev pointer: Points to the preceding node.
• Bidirectional Traversal: Can move from head to tail or tail to head.

Operations & Complexity (Compared to Singly Linked List):

• Access (by index): Still O(N).
• Insertion/Deletion (at beginning/end): Still O(1) if head/tail pointers maintained.
• Insertion/Deletion (in middle): O(N) to find the position, but once found, the actual insertion/deletion is O(1) because you have immediate access to both prev and next nodes.
• Deletion (at end): O(1) (if tail pointer maintained), as you can directly access the prev of the tail. This is a significant improvement over singly linked lists where it’s O(N).
• Space Complexity: O(N) - Stores N nodes, each with data and two pointers (more memory overhead per node).

        
          
#include <stdio.h>
#include <stdlib.h>

typedef struct DNode {
  int data;
  struct DNode* next; // Pointer to next node
  struct DNode* prev; // Pointer to previous node
} DNode;

// Function to add a new node at the beginning of the list
DNode* add_to_head_dll(DNode* head, int new_data) {
  DNode* new_node = (DNode*) malloc(sizeof(DNode));
  if (new_node == NULL) { /* Handle error */ return head; }

  new_node->data = new_data;
  new_node->prev = NULL; // New head, so no previous node

  new_node->next = head; // Link new node to old head
  if (head != NULL) {
      head->prev = new_node; // Old head's prev points to new node
  }
  head = new_node; // Update head
  return head;
}

// Function to print the list (forward)
void print_dll(DNode* node) {
  printf("DLL: NULL <-> ");
  while (node != NULL) {
      printf("%d <-> ", node->data);
      node = node->next;
  }
  printf("NULL\n");
}

int main() {
  DNode* head = NULL;

  head = add_to_head_dll(head, 10);
  print_dll(head);
  head = add_to_head_dll(head, 20);
  print_dll(head);

  // Free memory...
  DNode* current = head;
  while (current != NULL) {
      DNode* next = current->next;
      free(current);
      current = next;
  }
  return 0;
}
        
      

        
          
class DNode:
  def __init__(self, data):
      self.data = data
      self.next = None
      self.prev = None

class DoublyLinkedList:
  def __init__(self):
      self.head = None
      self.tail = None # Often maintain a tail for DLL

  # Add new node at the beginning
  def add_to_head_dll(self, new_data):
      new_node = DNode(new_data)
      new_node.next = self.head
      if self.head:
          self.head.prev = new_node
      else: # If list was empty
          self.tail = new_node
      self.head = new_node

  # Print list forward
  def print_dll(self):
      current = self.head
      print("DLL: NULL <-> ", end="")
      while current:
          print(f"{current.data} <-> ", end="")
          current = current.next
      print("NULL")

my_dll = DoublyLinkedList()
my_dll.add_to_head_dll(10)
my_dll.print_dll()
my_dll.add_to_head_dll(20)
my_dll.print_dll()
my_dll.add_to_head_dll(30)
my_dll.print_dll()

        
      

        
          
class DNode {
  constructor(data) {
      this.data = data;
      this.next = null;
      this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
      this.head = null;
      this.tail = null;
  }

  // Add new node at the beginning
  addAtHeadDll(newData) {
      const newNode = new DNode(newData);
      newNode.next = this.head;
      if (this.head) {
          this.head.prev = newNode;
      } else {
          // If list was empty, new node is both head and tail
          this.tail = newNode;
      }
      this.head = newNode;
  }

  // Print list forward
  printDll() {
      let current = this.head;
      let result = "DLL: NULL <-> ";
      while (current) {
          result += ${current.data} <->;
          current = current.next;
      }
      result += "NULL";
      console.log(result);
  }
}

const myDll = new DoublyLinkedList();
myDll.addAtHeadDll(10);
myDll.printDll();
myDll.addAtHeadDll(20);
myDll.printDll();
myDll.addAtHeadDll(30);
myDll.printDll();

        
      

Practical Usages:

• Undo/Redo Functionality: Easy to move both forward and backward through a sequence of actions.
• Web Browser History: Allows “back” and “forward” navigation.
• Least Recently Used (LRU) Cache: Often implemented with a doubly linked list to quickly move recently accessed items to the head.
• Music Playlists: Move to next/previous song easily.

Note: While doubly linked lists offer more flexibility, they come with a slight memory overhead per node (due to the extra prev pointer) and slightly more complex logic for insertion/deletion, as two pointers must be updated instead of one.

⭕ Circular Linked List

A circular linked list is a linked list where the last node’s next pointer points back to the first node (the head), forming a circle. It can be singly or doubly circular.

Characteristics:

• No NULL pointers (unless the list is empty).
• Can traverse the entire list starting from any node.
• Often managed by a single pointer (e.g., to the last node), from which you can find the head (last->next).

Practical Usages:

• Round-robin scheduling: Processes take turns, and when the last one finishes, it loops back to the first.
• Music players: Looping playlists.
• Game loops: Continuously iterating through game elements.

Note: Circular linked lists simplify certain traversal patterns and eliminate the need for special checks for the “end” of the list, but they do require careful handling to avoid infinite loops during iteration if not managed correctly.

⚖️ Linked Lists vs. Dynamic Arrays

Key Considerations for Choice:

• If you need fast random access by index, choose a dynamic array.
• If you need fast insertions and deletions anywhere in the list (once the position is found), and sequential access is more common than random access, a linked list might be better.
• Memory locality often gives dynamic arrays a performance edge due to CPU caching, even if the theoretical time complexity for an operation is the same. Linked lists often incur more cache misses.
• Space overhead is for pointers in linked lists vs. potentially wasted capacity in dynamic arrays.

Note: The concept of “nodes” and “pointers” introduced with linked lists is foundational for understanding many other complex data structures, such as trees and graphs, which rely heavily on non-contiguous, pointer-based connections.