DSA Linked Lists

A linked list is a chain of nodes, where each node points to the next one.

What is a Linked List?

Think of a treasure hunt. Each clue tells you where the next clue is. You cannot jump to clue number 5; you must follow the chain from the start.

A linked list works the same way. Each node holds:

the data (for example a number or a name)
a pointer (link) to the next node

The first node is called the head. The last node points to None.

Example

text

head -> [10] -> [20] -> [30] -> None

Unlike an array, the nodes do not need to sit next to each other in memory.

Building a Linked List in Python

Example

python

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

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

    def add_front(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    def add_end(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = node

    def show(self):
        items = []
        current = self.head
        while current:
            items.append(str(current.data))
            current = current.next
        print(" -> ".join(items) + " -> None")

stops = LinkedList()
stops.add_end("Orangi")
stops.add_end("Nazimabad")
stops.add_end("Saddar")
stops.add_front("Baldia")
stops.show()

Output

Baldia -> Orangi -> Nazimabad -> Saddar -> None

add_front is O(1): just change two pointers. add_end is O(n) here because it walks to the last node. Keeping a tail pointer would make it O(1).

Searching and Deleting

To delete a node, find the node before it and make that node skip over it.

Example

python

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

def contains(head, target):
    current = head
    while current:
        if current.data == target:
            return True
        current = current.next
    return False

def delete(head, target):
    if head and head.data == target:
        return head.next
    current = head
    while current and current.next:
        if current.next.data == target:
            current.next = current.next.next
            break
        current = current.next
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.data)
        head = head.next
    return out

head = Node(10, Node(20, Node(30, Node(40))))
print(contains(head, 30))
head = delete(head, 20)
print(to_list(head))
head = delete(head, 10)
print(to_list(head))

Output

True
[10, 30, 40]
[30, 40]

Deleting the head is a special case: the function simply returns the second node as the new head. That is why we always write head = delete(head, ...).

Arrays vs Linked Lists

Operation	Array (Python list)	Linked list
Read item number i	O(1)	O(n), must walk from head
Insert at the front	O(n)	O(1)
Insert at the end	O(1) on average	O(1) with a tail pointer
Delete a known node's neighbour	O(n)	O(1)
Search for a value	O(n)	O(n)
Extra memory	Low	One pointer per node

Use a linked list when you add and remove at the front a lot. Use an array when you need fast access by index.

Types of Linked Lists

Singly linked list: each node points to the next one only
Doubly linked list: each node points to both the next and the previous node, so you can move both ways
Circular linked list: the last node points back to the head

A music playlist with "next" and "previous" buttons is like a doubly linked list.

Exercise

What is the time complexity of adding a new node at the front of a linked list?

O(1)O(log n)O(n)O(n^2)