Introduction to Linked Lists

 

1. Introduction to Linked Lists

A linked list is a linear data structure where elements (nodes) are connected using pointers. Each node contains two main components:

1. Data – The value stored in the node.
2. Pointer (Link) – A reference to the next node in the sequence.

Unlike arrays, linked lists can grow and shrink dynamically, making them ideal for applications requiring frequent insertions and deletions.

---

2. Array vs. Pointer Implementation of Linked Lists

(a) Array Implementation of Linked Lists

Even though linked lists are inherently pointer-based, they can be simulated using arrays. In this approach, we use:

• An array to store data elements.
• Another array to store the "next" index of each element, simulating pointers.

Example (Singly Linked List Using Arrays)

c
#define SIZE 100  
int data[SIZE];     // Stores the values  
int next[SIZE];     // Stores the next index  
int head = -1;      // Points to the first element  

Operations like insertion and deletion require maintaining free list indexes, making this approach complex but useful in environments where pointer usage is restricted (e.g., embedded systems).

(b) Pointer Implementation of Linked Lists

This is the conventional way of implementing linked lists using dynamic memory allocation. Each node is represented as a structure or class containing a pointer to the next node.

Example (Singly Linked List Using Pointers in C)

c
struct Node {
    int data;
    struct Node* next;
};

Here, we use dynamic memory allocation (malloc() in C, new in C++/Java) to create nodes at runtime.

---

3. Types of Linked Lists and Their Implementations

(a) Singly Linked List

A singly linked list consists of nodes where each node points to the next node in the sequence. The last node’s pointer is set to NULL.

Pointer Implementation of Singly Linked List

c
struct Node {
    int data;
    struct Node* next;
};

Operations:

• Insertion: Add a node at the beginning, end, or at a given position.
• Deletion: Remove a node by updating pointers.
• Traversal: Access elements using a loop.

(b) Doubly Linked List

A doubly linked list allows traversal in both directions. Each node contains:

• A data field.
• A pointer to the next node.
• A pointer to the previous node.

Pointer Implementation of Doubly Linked List

c
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};

Operations:

• Bidirectional traversal: You can move forward or backward in the list.
• Efficient deletion: Unlike singly linked lists, we can delete a node without traversing from the head.

(c) Circular Linked List

A circular linked list is a variation where the last node’s pointer does not point to NULL. Instead:

• Singly Circular Linked List: The last node points to the first node.
• Doubly Circular Linked List: The last node’s next points to the first node, and the first node’s prev points to the last node.

Pointer Implementation of Circular Linked List

c
struct Node {
    int data;
    struct Node* next;
};

• In a singly circular linked list, tail->next points to the head.
• In a doubly circular linked list, head->prev points to tail, and tail->next points to head.

Operations:

• Continuous traversal: Useful in applications like round-robin scheduling.
• Efficient insertion and deletion: No need to check for NULL.

---

4. Comparison of Different Linked Lists

Feature	Singly Linked List	Doubly Linked List	Circular Linked List
Memory usage	Low (1 pointer per node)	High (2 pointers per node)	Similar to singly/doubly
Traversal	One direction only	Both directions	Cyclic traversal
Insertion/Deletion	O(1) at head, O(n) elsewhere	O(1) at head/tail, O(n) elsewhere	O(1) at head/tail
Reverse Traversal	Not possible	Possible	Possible (if doubly circular)
Use Cases	Basic linked list needs	Complex structures (e.g., undo/redo, navigation)	Scheduling, real-time applications

---

5. Applications of Linked Lists

• Singly Linked List: Memory-efficient storage, stacks, queues.
• Doubly Linked List: Text editors (undo/redo operations), browser history.
• Circular Linked List: Operating system scheduling, multiplayer gaming.