CSE Learn - Master Computer Science

What is a Linked List?

A Linked List is a linear data structure where elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays, linked list elements are not stored in contiguous memory locations - they are connected through pointers.

Advantages

Dynamic size - grows and shrinks as needed
Efficient insertions/deletions at known positions
No memory wastage (allocate as needed)
Easy implementation of stacks and queues

Disadvantages

No random access - must traverse from head
Extra memory for storing pointers
Poor cache locality
Reverse traversal difficult in singly linked list

Node Structure

Each node in a linked list contains two parts:

Data

value

pointer

Points to next node or NULL

Types of Linked Lists

1. Singly Linked List

Each node has data and a pointer to the next node. Traversal is only possible in one direction (forward).

[A|→] → [B|→] → [C|→] → NULL

2. Doubly Linked List

Each node has data, a pointer to the next node, AND a pointer to the previous node. Allows bidirectional traversal.

NULL ← [←|A|→] ↔ [←|B|→] ↔ [←|C|→] → NULL

3. Circular Linked List

The last node points back to the first node instead of NULL, forming a circle. Useful for round-robin scheduling.

[A|→] → [B|→] → [C|→] → (back to A)

Interactive Visualization

Experiment with linked list operations. Watch how nodes are connected and how traversal works.

HEAD

data

ptr

data

ptr

data

ptr

data

NULL

Click on operations to visualize linked list

Time Complexity

Operation	Singly Linked List	Doubly Linked List	Notes
Insert at Head	O(1)	O(1)	Direct pointer update
Insert at Tail	O(n)	O(1)*	*With tail pointer
Insert at Position	O(n)	O(n)	Need to traverse
Delete Head	O(1)	O(1)	Direct pointer update
Delete Tail	O(n)	O(1)*	*With tail pointer
Search	O(n)	O(n)	Linear search required
Access by Index	O(n)	O(n)	No random access

Implementation

Complete linked list implementation with all basic operations:

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

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_head(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
    
    def insert_at_tail(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
    
    def delete_node(self, key):
        current = self.head
        if current and current.data == key:
            self.head = current.next
            return
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        if current:
            prev.next = current.next
    
    def search(self, key):
        current = self.head
        position = 0
        while current:
            if current.data == key:
                return position
            current = current.next
            position += 1
        return -1
    
    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
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)) + " -> NULL")

# Usage
ll = LinkedList()
ll.insert_at_head(10)
ll.insert_at_tail(20)
ll.insert_at_tail(30)
ll.display()  # 10 -> 20 -> 30 -> NULL

Key Operations Explained

Reversing a Linked List

One of the most common interview questions. Use three pointers: prev, current, and next.

Initialize prev = NULL, current = head
Store next = current.next
Reverse the link: current.next = prev
Move prev and current one step forward
Repeat until current is NULL
Set head = prev

Detecting a Cycle (Floyd's Algorithm)

Use two pointers: slow (moves 1 step) and fast (moves 2 steps). If they meet, there's a cycle.

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

Finding Middle Element

Use slow and fast pointers. When fast reaches end, slow is at middle.

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # Middle node

Arrays vs Linked Lists

Aspect	Array	Linked List
Memory	Contiguous	Non-contiguous
Size	Fixed (static)	Dynamic
Access	O(1) random access	O(n) sequential
Insert/Delete	O(n) - shifting needed	O(1) if position known
Cache Performance	Excellent (locality)	Poor (scattered)
Extra Space	None	Pointer overhead

Interview Patterns

Two Pointer Technique

Many linked list problems use slow/fast pointers: cycle detection, finding middle, nth node from end, palindrome check.

Dummy Node Pattern

Create a dummy node before head to simplify edge cases. Useful when the head might change (merge lists, remove elements, partition).

Common Interview Questions

• Reverse a linked list (iterative and recursive)
• Detect and remove cycle
• Merge two sorted lists
• Find intersection of two lists
• Remove nth node from end
• Check if palindrome

Common Mistakes

Losing reference to head

Always save the head before traversing. Use a temporary pointer for iteration.

Not handling NULL/empty list

Always check if head is NULL before accessing head.next or head.data.

Memory leaks (C/C++)

Remember to free/delete nodes when removing them. Use smart pointers in modern C++.

Off-by-one errors in traversal

Be careful with while(current) vs while(current.next) - know when to stop.

Test Your Knowledge

Linked List Quiz

Question 1 of 6

What is the time complexity of inserting a node at the head of a singly linked list?