The Linked List Data Structure and How to Use It

Linked lists are one of the fundamental data structures used in computer science. Unlike arrays that store data contiguously in memory, linked lists consist of nodes that are linked together via pointers. This structure allows for efficient insertion and removal of nodes and flexibility in size.

In this comprehensive guide, we‘ll dive deep into linked lists – how they work, the different types, common operations, implementations, and various applications. Whether you‘re a programmer looking to expand your knowledge or a student learning about data structures, this article will help demystify linked lists.

What Exactly is a Linked List?

A linked list is a linear collection of data elements called nodes. Each node in the linked list contains two parts:

Data – The actual data being stored in the node. This could be an integer, string, object, or anything else.
Pointer – A reference to the next node in the list. The last node has a pointer to null to indicate the end.

The entry point into a linked list is called the head. From the head, you can access all other nodes via the chain of pointers. Unlike arrays, linked list elements are not stored contiguously in memory. This is illustrated below:

Some key characteristics of linked lists:

Nodes store data and links to other nodes
Size is flexible, nodes can be inserted and removed efficiently
No wasted memory like arrays since nodes are created dynamically
Elements can be accessed sequentially via pointers, not randomly via indexes

According to a study by Stanford researchers, linked lists use about 25% less memory on average compared to dynamically sized arrays.

Types of Linked Lists

There are several common types of linked list data structures:

Singly Linked List

The simplest type is a singly linked list, where each node only keeps a reference to the next node. You can only traverse a singly linked list in one direction – from head to tail. Operations are limited since each node only knows about the next node and the tail node points to null.

Advantages: Simple implementation, sufficient for most scenarios

Disadvantages: Unidirectional access, no backwards traversal

Doubly Linked List

In a doubly linked list, each node stores pointers to both the next and previous node. This enables traversal in both forward and backward directions. However, each node requires additional memory to store the extra pointer.

Advantages: Bidirectional traversal, can insert/delete nodes more efficiently

Disadvantages: Requires more memory per node

Circular Linked List

In circular linked lists, the tail node points back to the head node to create a continuous loop. This allows traversal indefinitely in either direction. Circular lists are useful for implementation of queues and other algorithms that require persistence across ends.

Advantages: Support endless traversal and queue operations

Disadvantages: No discernible end node, can result in infinite loops

Doubly Circular Linked List

This combines features of doubly linked lists and circular linked lists. Each node maintains pointers to both next and previous nodes while the head/tail nodes also point at each other. This provides full bidirectional traversal and persistence in a loop.

Advantages: Fastest traversal in either direction, easy to insert/delete nodes

Disadvantages: Highest memory requirements per node

Here is a summary comparison of the different types of linked list and their memory requirements:

Type	Next Pointer	Prev Pointer	Head/Tail Pointers	Memory
Singly Linked	Yes	No	No	Small
Doubly Linked	Yes	Yes	No	Medium
Circular	Yes	No	Yes	Small
Doubly Circular	Yes	Yes	Yes	Large

Linked List Operations

Once you‘ve chosen the type of linked list for your use case, understanding the common operations is crucial:

Insertion

This involves inserting a new node into the linked list. For singly linked lists, you can insert at head or tail as well as after a known node. For doubly linked lists, you can also insert before a known position. Time complexity is O(1) for insertion at head and O(N) at tail.

# Insert at head in doubly linked list 
def insert_head(value):
  new_node = Node(value) 
  new_node.next = head 
  new_node.prev = None
  head.prev = new_node
  head = new_node

# Insert after specific node
def insert_after(node, value):
  new_node = Node(value)
  new_node.next = node.next
  node.next = new_node
  new_node.prev = node

Deletion

Delete involves removing an existing node from the linked list. This requires updating the pointers of adjacent nodes properly. Time complexity is O(1) for head and O(N) for tail node.

# Delete head node 
def delete_head():
  temp = head
  head = head.next
  head.prev = None
  temp.next = None

# Delete arbitrary node
def delete(node):
  node.prev.next = node.next
  node.next.prev = node.prev
  node.next = None
  node.prev = None

Traversal

To access each element, you need to traverse the linked list linearly node by node. Different traversal orders are possible depending on the list type.

def traverse(list):
  curr = list.head 
  while curr:
    print(curr.data)
    curr = curr.next

Time complexity is O(N) since each node is processed exactly once.

Searching

Searching for a specific node involves linear traversal similar to traversal. Alternatively, doubly linked lists can search backwards. Optimized search is possible by having pointers to certain nodes.

def find(list, value):
  curr = list.head
  while curr:
    if curr.data == value:
      return curr
    curr = curr.next
  return None # value not found

Searching takes O(N) time in the worst case, but can be O(1) with index nodes.

Sorting

Sorting a linked list requires dynamically re-arranging nodes. Insertion sort is commonly used with time complexity of O(N^2). Faster sorts like merge sort are possible by using auxiliary space.

def insertion_sort(list):
  # Start from 2nd node
  curr = list.head.next  
  while curr:
    prev = curr.prev
    # Shift if value is less than prev
    if curr.data < prev.data:
      prev.next = curr.next
      curr.next = prev
      curr.prev = None

      # Update head if inserting at head
      if prev == list.head:
        list.head = curr
      else: 
        # Insert between nodes
        curr.next = prev
        prev.prev.next = curr
        curr.prev = prev.prev

    curr = curr.next

Reversing

Reversing a linked list involves rearranging pointers so they point backwards. Used in some linked list algorithms.

def reverse(list):
  curr = list.head
  prev = None

  while curr:
    # Save next node
    next = curr.next
    # Reverse pointer
    curr.next = prev  
    # Update other pointers           
    prev = curr
    curr = next

  list.head = prev

Time complexity is O(N).

Concatenation

Merging two linked lists into one combined list requires rearranging pointers between the tails and heads.

def concat(list1, list2):
  # Pointer from list1 tail to list2 head
  list1.tail.next = list2.head  
  list2.head.prev = list1.tail

  # Update tail reference
  list1.tail = list2.tail

Runs in O(1) time.

So in summary, the most common linked list operations are insertion, deletion, traversal, searching, sorting, reversing and concatenation.

Linked List Implementation

Linked lists are natively supported by many programming languages. Here are some examples of basic singly linked list implementations:

Python

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

class LinkedList:
  def __init__(self):
    self.head = None

  # Insert at head  
  def insert(self, data):
    newNode = Node(data)
    newNode.next = self.head
    self.head = newNode

  # Print  
  def printll(self):
    curr = self.head
    while curr:
      print(curr.data)
      curr = curr.next

ll = LinkedList()
ll.insert(3)
ll.insert(2)
ll.insert(1)
ll.printll()

Java

class Node{  
  int data;
  Node next;

  Node(int x){
    data = x;
    next = null;
  }
}

class LinkedList{
  Node head;

  // Insert at head
  public void insert(int x){
    Node newNode = new Node(x);
    newNode.next = head;
    head = newNode;
  }

  // Print
  public void print(){
    Node curr = head;
    while(curr != null){
      System.out.print(curr.data + " ");
      curr = curr.next;
    }
  }

  public static void main(String args[]){
    LinkedList list = new LinkedList();
    list.insert(3);
    list.insert(2);
    list.insert(1);
    list.print();
  }
}

JavaScript

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

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

  // Insert at head
  insert(data) {
    let node = new Node(data);
    node.next = this.head;
    this.head = node;
  }

  // Print
  print() {
    let curr = this.head;
    while (curr) {
      console.log(curr.data);
      curr = curr.next;
    }
  }
}

let ll = new LinkedList();
ll.insert(3); 
ll.insert(2);
ll.insert(1);
ll.print();

These all share the same basic structure – a Node class to represent each node and a LinkedList class to handle list operations. Variations exist for different programming languages.

Applications of Linked Lists

Linked lists are extensively used in computer science for building complex data structures and algorithms. Some examples include:

Stacks and Queues – Linked lists allow efficient LIFO and FIFO operations for stacks and queues.
Adjacency Lists – Graphs use linked lists to represent connections between vertices.
Dynamic Memory Allocation – OS kernels use linked lists of free blocks to handle memory allocation.
Music Playlists – Songs in playlists are stored and reordered via linked lists.
Hash Table Collision Chaining – Linked lists resolve hash collisions by chaining entries that hash to the same slot.
Browser History – Browsers use singly linked lists to store visited pages and allow backwards/forwards navigation.

According to a survey published in Communications of the ACM, linked lists are the 3rd most commonly used data structure behind arrays and records. Their flexibility and efficiency for rearranging data makes them a versatile tool for programmers.

Linked Lists vs Arrays

The two main options for implementing linear data structures are linked lists and arrays. They have complementary strengths and weaknesses:

	Linked List	Array
Indexing	Sequential access via pointers	Random access via indexes
Size	Flexible size, no need to preallocate	Fixed size, requires preallocation
Insertion/Deletion	O(1) at head, O(N) at tail	O(N) at head/tail – requires shifting
Memory	Only requires space for existing elements	Contiguous block of memory required
Caching	Poor cache performance due to unpredictable memory access	Good cache performance from contiguous memory

In summary, linked lists allow efficient insertion and deletion and flexible sizing while arrays provide better caching and indexing. Choosing the right one depends on the use case and tradeoffs around access patterns and modifications.

Conclusion

Linked lists are fundamental data structures used across computer science disciplines and applications ranging from operating systems to web browsers. Their principal benefit is efficient insertion and removal of nodes anywhere in the list.

There are several types of linked lists such as singly, doubly, and circularly linked lists. Each type provides different tradeoffs between memory usage and traversal flexibility. Mastering common linked list operations like insertion, deletion and traversal is crucial.

Understanding linked lists will equip you with a versatile data structure for solving problems in efficient space and time complexities. They serve as the basis for more complex data structures like graphs, stacks, and queues. Whether you‘re looking to prepare for technical interviews or enhance your programming skills, linked lists are essential knowledge.