DSA Linked Lists

A linked list is a linear data structure where elements are stored in individual units called nodes. Unlike arrays, the nodes in a linked list are not stored in contiguous memory. Instead, each node holds two things: the data it stores and a pointer (reference) to the next node in the sequence.

This structure makes linked lists particularly efficient for insertions and deletions, especially when the position is already known.

How a Linked List Looks

Visualize a linked list like a chain of train cars. Each car (node) carries cargo (data) and is connected to the next car via a coupling (pointer). The first car is called the head, and the last car has no coupling — its pointer is None.


# [10] --> [20] --> [30] --> [40] --> None

Building a Linked List in Python

Python does not have a built-in linked list, so one must be created manually using classes.

Step 1: Define the Node Class


class Node:
    def __init__(self, data):
        self.data = data    # The value stored in this node
        self.next = None    # Pointer to the next node (default: None)

Step 2: Define the LinkedList Class


class LinkedList:
    def __init__(self):
        self.head = None    # Initially the list is empty

Core Linked List Operations

Inserting at the End — O(n)

To add a node at the end, traverse to the last node, then attach the new node there.


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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node

# Usage
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)

Inserting at the Beginning — O(1)

Adding at the front is faster because only the head pointer needs to change.


    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

Traversing the List — O(n)

To display or process all elements, start from the head and follow the next pointers until reaching None.


    def display(self):
        current = self.head
        while current is not None:
            print(current.data, end=" --> ")
            current = current.next
        print("None")

# Output: 10 --> 20 --> 30 --> None

Deleting a Node — O(n)

To delete a node, find the node just before the target and update its next pointer to skip over the target node.


    def delete(self, data):
        if self.head is None:
            return

        # If the node to delete is the head
        if self.head.data == data:
            self.head = self.head.next
            return

        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next   # Skip the target node
                return
            current = current.next

Searching for a Value — O(n)


    def search(self, target):
        current = self.head
        position = 0
        while current is not None:
            if current.data == target:
                return position
            current = current.next
            position += 1
        return -1   # Not found

ll = LinkedList()
ll.append(5)
ll.append(15)
ll.append(25)
print(ll.search(15))   # Output: 1

Types of Linked Lists

1. Singly Linked List

Each node points only to the next node. Traversal is one-directional — from head to tail.


# [A] --> [B] --> [C] --> None

2. Doubly Linked List

Each node has two pointers: one pointing to the next node and one to the previous node. This allows traversal in both directions.


class DNode:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None   # Extra pointer to previous node

# None <-- [A] <--> [B] <--> [C] --> None

3. Circular Linked List

The last node's next pointer points back to the head instead of None, forming a loop. Useful in applications like round-robin scheduling.


# [A] --> [B] --> [C] --> back to [A]

Complete Working Example


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

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

    def append(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 display(self):
        current = self.head
        while current:
            print(current.data, end=" --> ")
            current = current.next
        print("None")

# Create list and add items
ll = LinkedList()
ll.append(100)
ll.append(200)
ll.append(300)
ll.display()
# Output: 100 --> 200 --> 300 --> None

Arrays vs Linked Lists

  • Access: Arrays allow O(1) random access; linked lists require O(n) traversal.
  • Insertion at front: Linked lists do it in O(1); arrays require O(n) shifting.
  • Memory: Arrays use less memory (no pointers); linked lists use extra memory per node for pointers.
  • Dynamic size: Linked lists naturally grow and shrink; arrays need resizing.

Big O Summary for Linked Lists

  • Access by index — O(n)
  • Search — O(n)
  • Insert at beginning — O(1)
  • Insert at end — O(n) for singly; O(1) with tail pointer
  • Delete at beginning — O(1)
  • Delete by value — O(n)

Key Points

  • A linked list consists of nodes, each storing data and a pointer to the next node.
  • The first node is called the head; the last node points to None.
  • Insertion at the beginning is O(1), making linked lists ideal for frequent front insertions.
  • Singly linked lists travel in one direction; doubly linked lists travel in both directions.
  • Circular linked lists form a loop and are useful for cyclic processes.
  • Linked lists use more memory than arrays but are more efficient for certain insert/delete operations.
Previous lessons
Back to courses
Next lessons

Leave a Comment