Linked List: A Complete Guide

Linked Lists are one of the most fundamental data structures in computer science. Understanding their operations is crucial for interviews, system designs, and efficient programming.

In this article, we’ll explore what a linked list is, and walk through all the key operations step-by-step.

What is a Linked List?

A Linked List is a linear data structure where elements (called nodes) are stored in non-contiguous memory locations.

Each node contains:

• Data: The value stored in the node.
• Pointer (next): A reference to the next node in the sequence.

Unlike arrays, linked lists are dynamic and efficient in insertions/deletions but slower in direct access.

Types of Linked Lists

Singly Linked List : Each node points to the next node.

Doubly Linked List : Each node points to both its next and previous nodes.

Circular Linked List :The last node points back to the head, forming a circle.

Basic Structure of a Node

Singly Linked List

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

Doubly Linked List

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

Core Operations

Basic

Node Creation and pointing

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

# Creating Node
head = Node(5)
fst  = Node(8)
snd  = Node(10)

# Pointer
head.next = fst
fst.next = snd
snd.next = None

Traverse

current = head
while current:
    print(current.data, end=" -> ")
    current = current.next
print("None")

#5 -> 8 -> 10 -> None


current = fst
while current:
    print(current.data, end=" -> ")
    current = current.next
print("None")

#8 -> 10 -> None

Traverse while current.next vs while current

# Way 1
current = head
while current:
    print(current.data, end=" -> ")
    current = current.next

#5 -> 8 -> 10 -> None


# Way 2
current = head
while current.next:
    print(current.data, end=" -> ")
    current = current.next
#5 -> 8 ->

Way 1:

• It will move forward as long as current is NOT None.
• When current becomes None, you exit the loop.
• Used to traverse all elements

Way 2:

• It will move forward only if current.next is NOT None
• When current.next == None, it means current is the last node.
• Used to traverse all elements except last
• Useful for inserting new node at last

Key Point

• Way 1 : current is None
• Way 2: current is last node

Common Mistake

def display():
  while head:
      print(head.data, end="  ")
      head = head.next
    
    

print(display())    # 5 8  10 
print(display())    #

Why 2nd display() behave different than 1st display()

• First call: It prints the list correctly, but it modifies head and moves it to None at the end of the list.
• Second call: Now, head is already None (after the first call), so the second time the function is called, it has nothing to print and outputs blank.

The Fix:

You should avoid modifying the global head inside the display() function. Instead, you can use a local variable (like current_node) to traverse the list. This way, head will stay intact for subsequent calls.

def display():
  current_node = head  # Use a local pointer
  while current_node:
      print(current_node.data, end="  ")
      current_node = current_node.next
    
    

print(display())    # 5 8  10 
print(display())    # 5 8  10 

How is current = current.next possible?

Aren’t the types different? (because current is a Node object, and current.next seems like something else?)

• self.data is the value (like integer, string, etc.).
• self.next is another Node object or None.

Both current and current.next are of the same type! (Node or NoneType)

Insertion

You can insert a node:

• At the beginning
• At the end
• After a given node
• At a specific position (index)

Insert At Beginning: This operation inserts a node at the beginning of the linked list, making it the head node. The previous head node becomes the second node of the linked list.

# Insert at the beginning
def insert_at_beginning(self, data):
  new_node = Node(data)
  new_node.next = self.head
  self.head = new_node

Insert At Position: This operation inserts a node at the position specified by the user.

Insert At End: This operation inserts a node at the end of the linked list, making it the tail node.

# Insert at the end
def insert_at_end(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
        return
    current = self.head
    while current.next:
        current = current.next
    current.next = new_node

Code Example

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

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

    # Insert at the beginning
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # Insert at the end
    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    # Insert after a specific node
    def insert_after(self, prev_node_data, data):
        current = self.head
        while current and current.data != prev_node_data:
            current = current.next
        if not current:
            print("Previous node not found")
            return
        new_node = Node(data)
        new_node.next = current.next
        current.next = new_node

# Create a LinkedList object
ll = LinkedList()

# Insert elements
ll.insert_at_beginning(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.insert_after(20, 25)  # Insert 25 after node with data 20

# A simple function to print the list
def print_linked_list(linked_list):
    current = linked_list.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")

# Print the linked list
print_linked_list(ll)

Deletion

Removing a node from the list.

We can delete:

• The first node
• A node by value
• The last node

  # Delete a node by value
  def delete_by_value(self, key):
      current = self.head

      # If head needs to be deleted
      if current and current.data == key:
          self.head = current.next
          current = None
          return

      prev = None
      while current and current.data != key:
          prev = current
          current = current.next

      if current is None:
          print("Node not found")
          return

      prev.next = current.next
      current = None

Traversal

Visiting all nodes and performing an action like printing or summarizing values.

# Print the linked list
def traverse(self):
    current = self.head
    while current:
        print(current.data, end=" -> ")
        current = current.next
    print("None")

Search

Finding whether a node with a specific value exists.

def search(self, key):
    current = self.head
    while current:
        if current.data == key:
            return True
        current = current.next
    return False

Update

Changing the value of a node once found.

def update_node(self, old_value, new_value):
    current = self.head
    while current:
        if current.data == old_value:
            current.data = new_value
            return
        current = current.next
    print("Node not found")

Reverse the Linked List

Reversing the direction of the list.

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

Finding the Length

Counting how many nodes are present.

def length(self):
    count = 0
    current = self.head
    while current:
        count += 1
        current = current.next
    return count

Detect Cycle in Linked List

Sometimes, due to coding mistakes, a linked list might form a cycle (i.e., a node points back to a previous node). Detecting this is crucial.

Floyd’s Cycle Detection Algorithm (Tortoise and Hare method):

Step 1: Detect if there is a cycle (fast and slow meet)

• Slow moves 1 step.
• Fast moves 2 steps.
• If they meet, there is a cycle.

def has_cycle(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Step 2: Find where the cycle starts

After slow and fast meet:

• Keep slow at meeting point.
• Move another pointer (say entry) from head.
• Now move both slow and entry one step at a time.
• The node where they meet again is the start of the cycle.

def detectCycle(head):
    slow = fast = head

    # Step 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Step 2: Find start of cycle
            entry = head
            while entry != slow:
                entry = entry.next
                slow = slow.next
            return entry  # start of the cycle
    return None  # No cycle

Note

• If the fast pointer reaches None (or null) but slow does not — it means there is no cycle.
• If fast and slow pointers meet at the same node — it means there is a cycle.

while fast and fast.next:

Case 1: “Why fast, not slow”

• You use fast pointer (instead of slow) when you want to quickly reach the end or middle.
• Fast reaches the end twice as fast, so when fast is at the end, slow is at the middle.
• Fast finishes traversal earlier, allowing slow to represent some important position like middle.

Case 2: “Why both fast and fast.next”

Sometimes you check both fast and fast.next to safely move two steps ahead. Even and odd case:

• If linked list length is odd, fast becomes null at the end.
• If length is even, fast.next becomes null.

Checking both avoids null pointer errors and handles even/odd differences.

Why not use only single pointer(slow) ?

• If you use just one pointer (slow) and it reaches None, you can indeed conclude: There is no cycle.
• But if there is cycle, the pointer will just keep moving endlessly inside the loop. It will never reach None
• But you won’t know whether you are looping or just moving forever — the program would just run infinitely.

That’s why one pointer cannot detect a cycle — it would hang forever if a cycle exists.

Why slow and faster alway meet?

Time and Space Complexity of Linked List Operations

n = number of nodes in the list.

Advantages of Linked Lists

• Dynamic size: Unlike arrays, they don’t need a fixed size.
• Efficient insertions/deletions: No shifting needed like arrays.
• Flexible memory usage: Ideal when memory is fragmented.

Disadvantages of Linked Lists

• Slow access: Cannot do random access; have to traverse from the head.
• More memory: Each node requires extra space for the pointer.
• Complex operations: More prone to bugs if not handled carefully.

Questions

Find the Duplicate Number – Floyd’s Cycle Detection – Leetcode 287

Intersection of Two Linked Lists – Leetcode 160

Conclusion

Linked Lists are powerful and flexible, forming the base of advanced structures like stacks, queues, graphs, and even hash tables!

Mastering their operations — insertion, deletion, traversal, searching, updating, reversing, and cycle detection — will sharpen your problem-solving skills dramatically.