Linked lists and their variants notes — Unit 2

A Linked List is a linear data structure, but unlike arrays, its elements are not stored at contiguous memory locations. Instead, the elements (nodes) are linked using pointers.

⇒1.1 The Concept of a Node

Each element in a linked list is called a Node. A basic node consists of two parts:

• Data Field: Stores the actual data/value.
• Link/Next Field: A pointer that stores the memory address of the next node in the sequence.

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

⇒1.2 Head Pointer

A linked list is always accessed via a special pointer called `head`, which points to the very first node. If the list is empty, `head` is `NULL`. The last node in the list points to `NULL`, indicating the end of the list.

Understanding when to choose a linked list over an array is a fundamental concept in data structures.

Linked lists rely heavily on Dynamic Memory Allocation, which allows programs to request memory from the operating system (specifically from the Heap) at runtime.

⇒3.1 malloc()

`malloc` (memory allocation) allocates a single block of requested memory size. It returns a void pointer to the memory, which must be cast to the desired type. The memory contains garbage values initially.

```c
struct Node ptr = (struct Node)malloc(sizeof(struct Node));
```

⇒3.2 calloc()

`calloc` (contiguous allocation) allocates multiple blocks of memory, each of the same size, and initializes all bytes to zero.

⇒3.3 free()

Memory allocated in the heap is not automatically destroyed when a function ends. The programmer must explicitly release it using `free()` to avoid memory leaks.

```c
free(ptr);
ptr = NULL; // Good practice to avoid dangling pointers
```

A Singly Linked List is the simplest type of linked list. Navigation is forward-only; you can traverse from the first node to the last, but you cannot move backward.

⇒4.1 Traversing a Singly Linked List

Traversal involves visiting every node exactly once to perform an operation (like printing data). We use a temporary pointer (`temp`) to walk the list so we don't lose the `head` pointer.

```c
void traverse(struct Node head) { struct Node temp = head;
while(temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
```

⇒4.2 Counting Nodes

To count nodes, we modify the traversal to increment a counter instead of printing.

Inserting a new node into a singly linked list can occur in three positions.

⇒5.1 Insertion at the Beginning ($O(1)$)

• Create a new node and assign data.
• Make the new node's `next` point to the current `head`.
• Update `head` to point to the new node.

```c
newNode->next = head;
head = newNode;
```

⇒5.2 Insertion at the End ($O(n)$)

• Create a new node. Make its `next` point to `NULL`.
• Traverse the list using a `temp` pointer until `temp->next == NULL`.
• Make `temp->next` point to the new node.

⇒5.3 Insertion after a Given Node ($O(1)$ if pointer known)

• Create a new node.
• Make `newNode->next` point to `prevNode->next`.
• Make `prevNode->next` point to `newNode`.

Deleting a node requires adjusting pointers and freeing the memory of the removed node.

⇒6.1 Deletion at the Beginning ($O(1)$)

• Store the current `head` in a temporary pointer.
• Update `head` to point to `head->next`.
• Free the temporary pointer.

```c
struct Node* temp = head;
head = head->next;
free(temp);
```

⇒6.2 Deletion at the End ($O(n)$)

• Traverse the list while keeping track of the `prev` node and `current` node.
• Stop when `current->next == NULL`.
• Set `prev->next = NULL`.
• Free `current`.

⇒6.3 Deletion of a Specific Node ($O(n)$ to find, $O(1)$ to delete)

Traverse to find the node. Adjust `prev->next` to skip the node to be deleted, then free it.

Reversing a linked list is a classic university and interview question. The goal is to change the direction of all pointers so the last node becomes the new head.

⇒7.1 Iterative Approach ($O(n)$ Time, $O(1)$ Space)

We use three pointers: `prev`, `current`, and `next`.

• Initialize `prev` to `NULL` and `current` to `head`.
• Loop while `current` is not `NULL`:
• - Save the next node: `next = current->next`
• - Reverse the link: `current->next = prev`
• - Move `prev` forward: `prev = current`
• - Move `current` forward: `current = next`
• Update `head` to `prev`.

```c
struct Node reverse(struct Node head) {
struct Node prev = NULL, current = head, *next = NULL;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
```

A Doubly Linked List (DLL) contains nodes that have two link pointers: one pointing to the next node and one pointing to the previous node. This allows traversal in both forward and backward directions.

⇒8.1 Node Structure

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

⇒8.2 Advantages over Singly Linked List

• Can traverse backward using the `prev` pointer.
• Deleting a node is $O(1)$ if the node pointer is given, because we immediately have access to the previous node.
• Inserting before a given node is simpler.

⇒8.3 Disadvantages

• Requires more memory (extra pointer per node).
• Operations are more complex because both `next` and `prev` pointers must be maintained during insertion/deletion.

⇒9.1 Insertion at the Beginning

```c
newNode->next = head;
newNode->prev = NULL;
if(head != NULL) {
head->prev = newNode;
}
head = newNode;
```

⇒9.2 Deletion of a Node

When deleting a node `del` from a DLL, we must connect its predecessor and successor directly.

```c
if(head == NULL || del == NULL) return;

// If node to be deleted is head node
if(head == del) head = del->next;

// Change next only if node to be deleted is NOT the last node
if(del->next != NULL) del->next->prev = del->prev;

// Change prev only if node to be deleted is NOT the first node
if(del->prev != NULL) del->prev->next = del->next;

free(del);
```

A Circular Linked List is a variation where the last node points back to the first node instead of pointing to `NULL`. It can be singly circular or doubly circular.

⇒10.1 Characteristics

• There is no `NULL` pointer in a standard circular linked list.
• Any node can be a starting point for traversal.
• Often used in OS scheduling (e.g., Round Robin) where the queue loops back to the start.

⇒10.2 The 'Tail' Pointer Variation

In many implementations, instead of keeping a `head` pointer, we keep a `tail` pointer (pointing to the last node). This provides a massive advantage:

• `tail->next` immediately gives us the first node (head).
• Insertion at the beginning takes $O(1)$ time.
• Insertion at the end also takes $O(1)$ time.

Without a tail pointer, insertion at the end of a circular list requires $O(n)$ traversal to find the last node.

Linked lists are highly effective for representing sparse polynomials. Each node represents a non-zero term.

⇒11.1 Node Structure

```c
struct Term {
int coeff;
int exp;
struct Term* next;
};
```

⇒11.2 Polynomial Addition Algorithm

To add two polynomials ($P_1$ and $P_2$), we use two pointers to traverse them. Both lists must be sorted in descending order of exponents.

• If `P1->exp > P2->exp`: Add $P_1$ node to result, move $P_1$ pointer.
• If `P1->exp < P2->exp`: Add $P_2$ node to result, move $P_2$ pointer.
• If `P1->exp == P2->exp`: Add coefficients. If sum $\neq 0$, add to result. Move both pointers.
• If one list is exhausted, append the remaining terms of the other list to the result.

Time Complexity: $O(m + n)$, where $m$ and $n$ are the number of terms in $P_1$ and $P_2$.

Also known as the Tortoise and Hare Algorithm, this is a famous technique to detect if a linked list contains a cycle (loop).

⇒12.1 The Algorithm

• Use two pointers: `slow` and `fast`.
• Initialize both pointers to `head`.
• Move `slow` by one step (`slow = slow->next`).
• Move `fast` by two steps (`fast = fast->next->next`).
• If there is a cycle, the `fast` pointer will eventually catch up and equal the `slow` pointer inside the loop.
• If `fast` reaches `NULL`, there is no cycle.

⇒12.2 Why does it work?

Imagine two runners on a circular track, one running twice as fast as the other. They are guaranteed to meet. The distance between them decreases by one node per step, so they must eventually collide.

Time Complexity: $O(n)$, Space Complexity: $O(1)$.

A very common interview question: How do you find the middle node of a singly linked list in a single pass?

⇒13.1 Two-Pointer Approach

We use a variation of the Tortoise and Hare method.

• Initialize two pointers, `slow` and `fast`, to `head`.
• Traverse the list. In each iteration:
• Move `slow` by one step.
• Move `fast` by two steps.
• When `fast` reaches the end of the list (`fast == NULL` or `fast->next == NULL`), `slow` will be pointing exactly at the middle node.

```c
struct Node getMiddle(struct Node head) {
if (head == NULL) return NULL;
struct Node slow = head, fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
```

Before moving to Stacks and Queues, ensure you have mastered these concepts.

⇒14.1 University Exam Checklist

• Differentiate between arrays and linked lists.
• Write a C function to insert a node at the beginning, end, and middle of a singly linked list.
• Write a C function to reverse a singly linked list iteratively.
• Explain the advantages and disadvantages of a Doubly Linked List.
• Explain how two polynomials are added using linked lists.

⇒14.2 Placement Interview Focus

• Explain Floyd's cycle detection algorithm. How would you find the starting node of the cycle?
• How do you find the $N$-th node from the end of a linked list in a single pass? (Hint: Two pointers separated by $N$ steps).
• How do you merge two sorted linked lists into a single sorted linked list in $O(1)$ auxiliary space?
• What causes a Segmentation Fault when working with linked lists?