Double Linked List

Definition

A doubly linked list (also called a two-way linked list) is a linked list in which every node contains three fields:

1. PREV (Left Link) - a pointer that points to the previous node in the list
2. INFO (Data) - the actual data stored in the node
3. NEXT (Right Link) - a pointer that points to the next node in the list

The PREV pointer of the first node and the NEXT pointer of the last node both contain NULL.

Node Structure

+--------+--------+--------+
|  PREV  |  INFO  |  NEXT  |
+--------+--------+--------+

In C, the node can be declared as:

struct node {
    struct node *prev;
    int info;
    struct node *next;
};

Diagrammatic Example

Consider a doubly linked list containing three elements: 10, 20, 30

START
  |
  v
+------+----+------+    +------+----+------+    +------+----+------+
| NULL | 10 |  o---+--->|  o---| 20 |  o---+--->|  o---| 30 | NULL |
+------+----+------+    +------+----+------+    +------+----+------+
        Node 1      <---+---o        Node 2  <---+---o        Node 3

• Node 1: PREV = NULL, INFO = 10, NEXT = address of Node 2
• Node 2: PREV = address of Node 1, INFO = 20, NEXT = address of Node 3
• Node 3: PREV = address of Node 2, INFO = 30, NEXT = NULL

Key Characteristics

Advantages of Doubly Linked List

1. Bidirectional traversal is possible (forward and backward).
2. Deletion of a node is easier because we can access the previous node directly without traversing from the beginning.
3. Insertion before a given node is simpler compared to singly linked list.

Disadvantage

• Each node requires an extra pointer (PREV), which uses more memory than a singly linked list.

Summary

A doubly linked list allows movement in both directions through the list, making operations like reverse traversal, deletion, and insertion more efficient compared to a singly linked list, at the cost of slightly more memory per node.

Sorting and Bubble Sort

What is Sorting?

Sorting is the process of arranging data elements in a specific order (either ascending or descending) so that the data can be searched, accessed, or processed more efficiently. Sorting organizes a collection of data into a sequence ordered by some criterion.

Example: Arranging [5, 2, 8, 1, 9] into [1, 2, 5, 8, 9] (ascending order).

Bubble Sort

Definition: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. The basic idea is to pass through the array sequentially several times. Each pass consists of comparing each element a[i] with its adjacent element a[i+1] and interchanging them if they are not in proper order.

After each pass, the largest unsorted element "bubbles up" to its correct position at the end of the array.

Algorithm

for i = 0 to n-2:
    for j = 0 to n-2-i:
        if a[j] > a[j+1]:
            swap(a[j], a[j+1])

Time Complexity

Worked Example

Array: [5, 3, 8, 1, 4]

Pass 1 (i = 0)

Largest element 8 is now at its correct position.

Pass 2 (i = 1)

Second largest element 5 is now at its correct position.

Pass 3 (i = 2)

Pass 4 (i = 3)

Final Sorted Array

[1, 3, 4, 5, 8]

Summary

• Bubble sort is simple but inefficient for large datasets due to O(n^2) complexity.
• It performs a maximum of n-1 passes for an array of n elements.
• It is an in-place sorting algorithm (no extra memory required).