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

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

#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.