Introduction to Linked Lists

In data structures, a linear data structure is one where elements are arranged sequentially, one after another. The most familiar example is an array, where elements are stored in contiguous memory locations. Arrays allow quick access to elements by their index, but they come with some limitations:

• Fixed size: Once declared, the size of an array cannot be changed. If you need more space, you must create a new array and copy elements, which is inefficient.
• Memory wastage or shortage: If the array size is too large, memory is wasted; if too small, it cannot hold all data.
• Insertion and deletion: Adding or removing elements in the middle requires shifting many elements, which is time-consuming.

To overcome these problems, we use linked lists, a dynamic data structure that allows flexible memory usage and efficient insertions and deletions.

A linked list is made up of nodes. Each node contains two parts:

1. Data: The actual information stored (e.g., an integer, a name, or any data).
2. Pointer (or link): A reference to the next node in the list.

Unlike arrays, nodes in a linked list can be scattered anywhere in memory. The pointer connects them logically, forming a chain. This allows the list to grow or shrink dynamically as needed.

Think of a linked list like a treasure hunt: each clue (node) tells you where to find the next clue, rather than having all clues laid out in a row.

Singly Linked List

A singly linked list is the simplest form of linked list. Each node contains data and a pointer to the next node only. The list starts with a special pointer called the head, which points to the first node. The last node points to null, indicating the end of the list.

Each node points only to the next node, so traversal is unidirectional, from head to tail.

Doubly Linked List

A doubly linked list extends the singly linked list by adding a second pointer in each node. This pointer points to the previous node, allowing traversal in both directions - forward and backward.

This bidirectional feature makes certain operations, like deletion or reverse traversal, more efficient.

Circular Linked List

A circular linked list is a variation where the last node points back to the first node, forming a loop. This can be implemented with singly or doubly linked lists.

In a singly circular linked list, the last node's next pointer points to the head node instead of null. In a doubly circular linked list, the last node's next points to the head, and the head's previous points to the last node.

This circular structure is useful for applications requiring continuous cycling through data, such as round-robin scheduling or buffering.

Basic Operations on Linked Lists

Linked lists support three fundamental operations:

• Insertion: Adding a new node at the beginning, end, or a specific position.
• Deletion: Removing a node from the beginning, end, or a specific position.
• Traversal: Visiting each node to read or process data.

These operations involve updating pointers carefully to maintain the list's structure.

graph TD    Start[Start Operation] --> CheckType{Insertion or Deletion?}    CheckType -->|Insertion| InsertPos{Position?}    InsertPos -->|Beginning| InsertBegin[Update head pointer]    InsertPos -->|End| InsertEnd[Traverse to last node, update pointer]    InsertPos -->|Middle| InsertMiddle[Traverse to position, update pointers]    CheckType -->|Deletion| DeletePos{Position?}    DeletePos -->|Beginning| DeleteBegin[Update head pointer]    DeletePos -->|End| DeleteEnd[Traverse to second last node, update pointer]    DeletePos -->|Middle| DeleteMiddle[Traverse to position, update pointers]    InsertBegin --> EndOp[End]    InsertEnd --> EndOp    InsertMiddle --> EndOp    DeleteBegin --> EndOp    DeleteEnd --> EndOp    DeleteMiddle --> EndOp

Worked Examples