# Module 2 - Linked List

Theoretical basics of Linked Lists, their types, benefits, and example code.

# Part 1 - Understanding Linked List

#### Definition of Linked List

A Linked List is a linear data structure consisting of elements called nodes. Each node has two main parts:

- **Data** – stores the value of the element.
- **Pointer/Reference** – points to the next node (or the previous node in a Doubly Linked List).

#### Differences Between Linked List and Array

<table id="bkmrk-aspect-array-linked-" style="width: 100%;"><thead><tr><th style="width: 17.1565%;">Aspect</th><th style="width: 37.9988%;">Array</th><th style="width: 44.9242%;">Linked List</th></tr></thead><tbody><tr><td style="width: 17.1565%;">Storage</td><td style="width: 37.9988%;">Elements are stored contiguously in memory.</td><td style="width: 44.9242%;">Nodes are stored in non-contiguous memory and linked by pointers.</td></tr><tr><td style="width: 17.1565%;">Element Access</td><td style="width: 37.9988%;">Direct access using an index, complexity O(1).</td><td style="width: 44.9242%;">Access requires traversal from the start, complexity O(n).</td></tr><tr><td style="width: 17.1565%;">Size</td><td style="width: 37.9988%;">Static, size determined at declaration.</td><td style="width: 44.9242%;">Dynamic, can grow or shrink as needed.</td></tr><tr><td style="width: 17.1565%;">Insert/Delete</td><td style="width: 37.9988%;">Expensive due to element shifting, complexity O(n).</td><td style="width: 44.9242%;">More efficient, only pointer adjustments needed, complexity O(1) if position is known.</td></tr></tbody></table>

#### Benefits of Linked List

**Dynamic Size**

- No need to define size in advance like an array.
- Can grow or shrink according to program needs.

**Efficiency in Insert/Delete Operations**

- Adding or removing elements does not require shifting data.
- Complexity can be O(1) if the pointer is known.

**More Flexible Memory Usage**

- Nodes can be stored in scattered memory locations.
- Useful in systems with fragmented memory.

**Support for Complex Data Structures**

- Forms the basis for other data structures such as Stack, Queue, Deque, and Graph.
- Enables creation of variants like Circular Linked List and Doubly Linked List.

**Two-Way Traversal (in Doubly Linked List)**

- Makes navigation forward and backward easier.

#### Applications of Linked Lists

**Dynamic Memory Allocation**

- Used to keep track of free and allocated memory blocks.

**Undo/Redo Operations in Text Editors**

- Stores changes and navigates through editing history.

**Graph Representation**

- Efficiently implements adjacency lists in graph structures.

**Implementation of Other Data Structures**

- Serves as a base for stacks, queues, and deques.

#### Advantages of Linked List

- Efficient insertion and deletion since shifting of elements is not required as in arrays.
- Dynamic size allows growth or shrinkage at runtime.
- Memory utilization is more efficient; no pre-allocation reduces wasted space.
- Suitable for applications with large or frequently changing datasets.
- Uses non-contiguous memory blocks, useful in memory-limited systems.

#### Disadvantages of Linked List

- Direct access to an element is not possible; traversal from the start is required.
- Each node requires extra memory to store a pointer.
- More complex to implement and manage compared to arrays.
- Pointer mismanagement can cause bugs, memory leaks, or segmentation faults.

#### Short Code Example

```c
#include <iostream>
using namespace std;

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

void pushFront(Node*& head, int value) {
    Node* newNode = new Node(); // Buat node baru
    newNode->data = value;      // Isi data
    newNode->next = head;       // Hubungkan ke head lama
    head = newNode;             // Jadikan node baru sebagai head
}

void printList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "NULL\n";
}

int main() {
    Node* head = nullptr;  // List kosong

    pushFront(head, 10);
    pushFront(head, 20);
    pushFront(head, 30);

    printList(head); // Output: 30 -> 20 -> 10 -> NULL

    return 0;
}

```

**Code Explanation:**

- `Node` is the basic structure of a Linked List.
- `pushFront` adds a new node at the beginning of the list.
- `printList` traverses the list and displays all elements.

# Part 2 - Types of Linked List

#### Types of Linked Lists

Based on the structure of linked lists, they can be classified into several types:

- **Singly Linked List**
- **Doubly Linked List**
- **Circular Linked List**

#### 1. Singly Linked List

The singly linked list is the simplest form of linked list, where each node contains two members: **data** and a **next pointer** that stores the address of the next node. Each node in a singly linked list is connected through the next pointer, and the next pointer of the last node points to `NULL`, denoting the end of the list.

#### Singly Linked List Representation

A singly linked list can be represented as a pointer to the first node, where each node contains:

- **Data:** Actual information stored in the node.
- **Next:** Pointer to the next node.

```cpp
// Structure to represent the singly linked list
struct Node {
    int data;       // Data field
    struct Node* next; // Pointer to the next node
};

```

#### 2. Doubly Linked List

The doubly linked list is a modified version of the singly linked list. Each node contains three members: **data**, **next**, and **prev**. The `prev` pointer stores the address of the previous node. Nodes are connected via both `next` and `prev` pointers. The `prev` pointer of the first node and the `next` pointer of the last node point to `NULL`.

#### Doubly Linked List Representation

Each node contains:

- **Data:** Actual information stored.
- **Next:** Pointer to the next node.
- **Prev:** Pointer to the previous node.

```cpp
// Structure to represent the doubly linked list
struct Node {
    int data;       // Data field
    struct Node* next; // Pointer to the next node
    struct Node* prev; // Pointer to the previous node
};

```

#### 3. Circular Linked List

A circular linked list is similar to a singly linked list, except the next pointer of the last node points to the **first node** instead of `NULL`. This circular nature is useful in applications like media players.

#### Circular Linked List Representation

Each node contains:

- **Data:** Actual information stored.
- **Next:** Pointer to the next node; the last node points to the first node.

```cpp
// Structure to represent the circular linked list
struct Node {
    int data;       // Data field
    struct Node* next; // Pointer to the next node
};

```

# Part 3 - Searching

#### 1. Searching in a Custom Singly Linked List

```cpp
#include <bits/stdc++.h>
using namespace std;

// Linked list node
class Node 
{ 
public:
    int key; 
    Node* next; 
}; 

// Add a new node at the front
void push(Node** head_ref, int new_key) 
{ 
    Node* new_node = new Node();
    new_node->key = new_key; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

// Search for a value in the linked list
bool search(Node* head, int x) 
{ 
    Node* current = head; 
    while (current != NULL) 
    { 
        if (current->key == x) 
            return true; 
        current = current->next; 
    } 
    return false; 
} 

int main() 
{ 
    Node* head = NULL; 
    int x = 21; 

    // Construct list: 14->21->11->30->10
    push(&head, 10); 
    push(&head, 30); 
    push(&head, 11); 
    push(&head, 21); 
    push(&head, 14); 

    search(head, 21) ? cout << "Yes" : cout << "No"; 
    return 0; 
}

```

**Explanation:**

- `Node` class represents each node in the linked list.
- `push` adds a new node at the beginning.
- `search` traverses the list iteratively to find the key.

#### 2. Searching in STL `std::list`

C++ Standard Template Library (STL) provides the `list` container which can be used to implement a linked list. Searching can be done using the `std::find` algorithm.

```cpp
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int main() {
    list<int> l = {14, 21, 11, 30, 10};
    int x = 21;

    auto it = find(l.begin(), l.end(), x);

    if (it != l.end())
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

```

**Explanation:**

- `std::list` is a doubly linked list implementation.
- `std::find` iterates through the list to locate the element.
- Returns an iterator to the element if found, or `l.end()` if not found.

# Part 4 - Manual VS STL List

A **doubly linked list** is a data structure where each node contains a pointer to the **next** and **previous** nodes, allowing traversal in both directions. In C++, you can implement it manually or use the built-in STL `std::list`.

**Differences between Manual Doubly Linked List and STL `std::list`:**

<table id="bkmrk-feature-manual-doubl"><thead><tr><th>Feature</th><th>Manual Doubly Linked List</th><th>STL `std::list`</th></tr></thead><tbody><tr><td>Implementation</td><td>You define the `Node` structure and pointers manually.</td><td>Already implemented as a doubly linked list in the STL.</td></tr><tr><td>Memory Management</td><td>Manual allocation and deallocation using `new` and `delete`.</td><td>Automatic memory management.</td></tr><tr><td>Operations</td><td>Insert, delete, traversal, and search must be implemented manually.</td><td>Provides built-in functions like `push_back`, `push_front`, `erase`, and `find`.</td></tr><tr><td>Complexity</td><td>More control but more prone to errors like memory leaks.</td><td>Safer and easier to use, less prone to bugs.</td></tr></tbody></table>

#### 1. Manual Doubly Linked List Example

```cpp
#include <iostream>
using namespace std;

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

// Add a node at the end
void pushBack(Node*& head, int value) {
    Node* newNode = new Node{value, nullptr, nullptr};
    if (!head) {
        head = newNode;
        return;
    }
    Node* temp = head;
    while (temp->next) temp = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
}

// Print the list
void printList(Node* head) {
    Node* temp = head;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    Node* head = nullptr;
    pushBack(head, 10);
    pushBack(head, 20);
    pushBack(head, 30);

    printList(head); // Output: 10 20 30
}

```

#### 2. STL `std::list` Example

```cpp
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l;

    l.push_back(10);
    l.push_back(20);
    l.push_back(30);

    for (int x : l)
        cout << x << " "; // Output: 10 20 30
    cout << endl;
}

```

**Explanation:**

- Manual doubly linked list requires defining nodes and managing pointers yourself.
- `std::list` simplifies everything: memory management and operations like insertion, deletion, and traversal are built-in.