Linked Lists - Data Structures

A linked list is a linear data structure where elements are not stored at contiguous memory locations. Elements are linked using pointers.

Introduction

Unlike arrays, linked lists are dynamic data structures that can grow or shrink during runtime. Each element (node) contains data and a reference to the next node.

Types of Linked Lists

1. Singly Linked List

Each node points to the next node in the sequence.

[Data|Next] -> [Data|Next] -> [Data|NULL]

2. Doubly Linked List

Each node has pointers to both next and previous nodes.

[Prev|Data|Next] <-> [Prev|Data|Next] <-> [Prev|Data|Next]

3. Circular Linked List

The last node points back to the first node, forming a circle.

Basic Operations

Insertion

At the beginning: O(1) At the end: O(n) for singly linked list, O(1) with tail pointer At specific position: O(n)

Deletion

At the beginning: O(1) At the end: O(n) for singly linked list At specific position: O(n)

Searching

Linear search: O(n) time complexity

Implementation 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

Advantages

• Dynamic size
• Efficient insertion/deletion at beginning
• No memory waste
• Easy to implement

Disadvantages

• No random access
• Extra memory for pointers
• Not cache-friendly
• Traversal required for most operations

Common Problems

1. Reverse a linked list
2. Detect cycle in linked list
3. Merge two sorted lists
4. Find middle element
5. Remove duplicates
6. Palindrome check