Linked List Data Structure

Definition

A linked list is a linear data structure consisting of nodes where each node contains data and a reference (pointer) to the next node in the sequence. Unlike arrays, linked lists don't store elements in contiguous memory locations. The first node is called the head, and the last node points to null.

Key Properties

Dynamic Size

Size can grow or shrink during runtime

Non-contiguous Memory

Nodes can be stored anywhere in memory

Sequential Access

Must traverse from head to access elements

Easy Insertion/Deletion

O(1) insertion/deletion at known position

Memory Efficient

Only uses memory for actual data

No Wasted Space

No unused memory allocation

Time Complexity

Operation	Time Complexity	Description
Access	O(n)	Must traverse from head
Search	O(n)	Linear search through nodes
Insertion (at head)	O(1)	Direct insertion at beginning
Insertion (at tail)	O(n)	Must traverse to end
Deletion (at head)	O(1)	Direct deletion from beginning
Deletion (at tail)	O(n)	Must traverse to end

Python Code Examples

Python Implementation

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

# Linked List class
class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

    def prepend(self, data):
        """Add element at the beginning"""
        new_node = ListNode(data)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def append(self, data):
        """Add element at the end"""
        new_node = ListNode(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1

    def insert_at(self, data, index):
        """Insert at specific position"""
        if index < 0 or index > self.size:
            return False
        
        if index == 0:
            self.prepend(data)
            return True

        new_node = ListNode(data)
        current = self.head
        for i in range(index - 1):
            current = current.next
        
        new_node.next = current.next
        current.next = new_node
        self.size += 1
        return True

    def remove(self, data):
        """Remove element"""
        if not self.head:
            return False
        
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return True

        current = self.head
        while current.next and current.next.data != data:
            current = current.next
        
        if current.next:
            current.next = current.next.next
            self.size -= 1
            return True
        return False

    def find(self, data):
        """Search element"""
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1

    def display(self):
        """Display list"""
        current = self.head
        result = []
        while current:
            result.append(str(current.data))
            current = current.next
        return " -> ".join(result)

    def reverse(self):
        """Reverse the linked list"""
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

# Usage
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
print(ll.display())  # "0 -> 1 -> 2 -> 3"

# Find element
print(f"Index of 2: {ll.find(2)}")  # 2

# Remove element
ll.remove(1)
print(ll.display())  # "0 -> 2 -> 3"

# Reverse list
ll.reverse()
print(ll.display())  # "3 -> 2 -> 0"

Common Use Cases

Dynamic Memory Allocation

When size is unknown at compile time

Implementation of Stacks/Queues

Base structure for other data structures

Music Playlists

Sequential access to songs

Undo Functionality

Storing command history

Browser History

Forward/backward navigation

Polynomial Representation

Mathematical expressions