Linked Lists

Linked Lists

What is a Linked List?

A Linked List is a collection of specially designed elements called nodes.

Node: An element that can be further divided into minimum 2 parts:

1. Data — the value stored
2. Address — address of the next element (next pointer)

head
 |
 v
[11|2000]-->[22|3000]-->[33|4000]-->[44|NULL]
  1000        2000        3000        4000

How it differs from array:

• Elements not stored in contiguous memory
• Each node contains a pointer to the next node
• Dynamic size — grows and shrinks at runtime

Self-Referential Structure

A self-referential structure is a structure that has at least one member as a pointer pointing to the same type in which it is declared.

typedef struct node {
    int data;
    struct node *next;   // pointer to same type  <-- self-referential!
} node_t;

// Create a new node
node_t *p;
p = (node_t *) malloc(sizeof(node_t));  // allocate memory on heap
p->data = 42;
p->next = NULL;

Types of Linked Lists

Operations on Linked List

Singly Linear Linked List — C Implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
} node_t;

// Create a new node
node_t *create_node(int value) {
    node_t *p = (node_t *)
malloc(sizeof(node_t));
    p->data = value;
    p->next = NULL;
    return p;
}

// Add at first
node_t *add_at_first(node_t *head, int value) {
    node_t *new_node =
create_node(value);
    new_node->next = head;
    head = new_node;
    return head;
}

// Add at last
node_t *add_at_last(node_t *head, int value) {
    node_t *new_node =
create_node(value);
    if (head == NULL) return new_node;

    node_t *current = head;
while (current->next != NULL) {
        current = current->next;
    }
    current->next =
new_node;
    return head;
}

// Delete from first
node_t *del_from_first(node_t *head) {
    if (head == NULL) {
printf("List is empty\n");
        return NULL;
    }
    node_t *temp = head;
    head =
head->next;
    free(temp);
    return head;
}

// Traverse
void traverse(node_t *head) {
    node_t *current = head;
    while (current !=
NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
printf("NULL\n");
}

// Search
int search(node_t *head, int target) {
    node_t *current = head;
    int
position = 0;
    while (current != NULL) {
        if (current->data == target) return
position;
        current = current->next;
        position++;
    }
    return -1;  // not
found
}

// Reverse a linked list
node_t *reverse(node_t *head) {
    node_t *prev = NULL;
    node_t
*current = head;
    node_t *next_node;

    while (current != NULL) {
        next_node
= current->next;   // save next
        current->next = prev;        // reverse link
prev = current;              // advance prev
        current = next_node;         // advance
current
    }
    return prev;  // new head
}

int main() {
    node_t *head = NULL;

    head = add_at_last(head, 11);
    head = add_at_last(head, 22);
    head = add_at_last(head, 33);
    head = add_at_first(head, 5);

    printf("List: ");
    traverse(head);
    // Output: 5 -> 11 -> 22 -> 33 -> NULL

    head = reverse(head);
    printf("Reversed: ");
    traverse(head);
    // Output: 33 -> 22 -> 11 -> 5 -> NULL

    return 0;
}

Doubly Linked List

typedef struct dnode {
    int data;
    struct dnode *prev;   // pointer to previous node
    struct dnode *next;   // pointer to next node
} dnode_t;

NULL <-- [11] <--> [22] <--> [33] <--> [44] --> NULL
head                                    tail

Advantages over SLL:

• Can traverse both forward and backward
• Deletion is O(1) if node pointer is given (no need to find prev)

Disadvantages:

• Extra memory per node (prev pointer)
• More complex insertion/deletion code

Advantages of Linked List

1. Dynamic size — We can add/delete elements at runtime; actual number of elements can be increased or decreased
2. Optimized memory usage — Memory allocated only when needed

Disadvantages of Linked List

1. Pointer overhead — Each node has a member as pointer storing address of next element; memory for pointer is overhead against each element
2. Cumbersome access — Accessing elements in linked list requires traversal from head; no random access

Linked List vs Array Comparison

Time Complexity of Linked List Operations