Skip to main content

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

AspectArrayLinked List
**Storage**Elements are stored **contiguously** in memory.Nodes are stored in **non-contiguous** memory and linked by pointers.
**Element Access**Direct access using an index, complexity O(1).Access requires traversal from the start, complexity O(n).
**Size**Static, size determined at declaration.Dynamic, can grow or shrink as needed.
**Insert/Delete**Expensive due to element shifting, complexity O(n).More efficient, only pointer adjustments needed, complexity O(1) if position is known.

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.

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.
Back to top