Understanding Linked List

DefinisiDefinition of Linked List

A Linked List adalahis struktura linear data linearstructure yangconsisting terdiriof darielements elemen-elemencalled yangnodes. disebut node. SetiapEach node memilikihas duatwo bagianmain utama:parts:

• Data – menyimpanstores nilaithe elemen.value of the element.

• Pointer/ReferensiReference – menunjukpoints keto the next node berikutnya(or (atauthe sebelumnyaprevious padanode in a Doubly Linked List).

PerbedaanDifferences Between Linked List danand Array

AspekAspect	Array	Linked List
PenyimpananStorage	ElemenElements disimpanare secarastored bersebelahancontiguously dalamin memori.memory.	NodeNodes disimpanare stored in tersebarnon-contiguous dimemory memoriand danlinked dihubungkanby oleh pointer.pointers.
AksesElement ElemenAccess	AksesDirect langsungaccess menggunakanusing indeks,an kompleksitasindex, complexity O(1).	AksesAccess harus dilakukan denganrequires traversal darifrom awal,the kompleksitasstart, complexity O(n).
UkuranSize	BersifatStatic, statis,size ukurandetermined ditentukanat saat deklarasi.declaration.	BersifatDynamic, dinamis,can dapatgrow bertambah/berkurangor sesuaishrink kebutuhan.as needed.
Insert/Delete	MahalExpensive karenadue perluto menggeserelement elemen,shifting, kompleksitascomplexity O(n).	LebihMore efisienefficient, karenaonly hanyapointer mengubahadjustments pointer,needed, kompleksitascomplexity O(1) jikaif posisiposition diketahui.is known.

ManfaatBenefits of Linked List

1. UkuranDynamic DinamisSize

   • TidakNo perluneed menentukanto ukurandefine disize awalin sepertiadvance padalike an array.

   • DapatCan bertambahgrow atauor berkurangshrink sesuaiaccording kebutuhanto program.program needs.

2. EfisiensiEfficiency pada Operasiin Insert/Delete Operations

   • MenambahkanAdding atauor menghapusremoving elemenelements tidakdoes memerlukannot pergeseranrequire shifting data.

   • KompleksitasComplexity dapatcan menjadibe O(1) jikaif the pointer sudahis diketahui.known.

3. MemanfaatkanMore MemoriFlexible SecaraMemory Lebih FleksibelUsage

   • NodeNodes dapatcan disimpanbe distored lokasiin memoriscattered yangmemory tersebar.locations.

   • BergunaUseful padain sistemsystems denganwith memorifragmented yang terfragmentasi.memory.

4. DukunganSupport untukfor StrukturComplex Data KompleksStructures

   • MenjadiForms dasarthe untukbasis strukturfor other data lainstructures sepertisuch as Stack, Queue, Deque, danand Graph.Graph.

   • MemungkinkanEnables pembuatancreation varianof sepertivariants like Circular Linked List danand Doubly Linked List.List.

5. Two-Way Traversal Dua Arah (padain Doubly Linked List)

   • MemudahkanMakes navigasinavigation keforward depanand maupunbackward ke belakang dalam list.easier.

Applications of Linked Lists

1. Dynamic Memory Allocation

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

2. Undo/Redo Operations in Text Editors

   • Linked lists are used to storeStores changes and navigatenavigates through editing history.

3. Graph Representation

   • ImplementEfficiently implements adjacency lists efficiently in graph data structures.

4. Implementation of Other Data Structures

   • UsedServes as a base for stacks, queues, and deques.

Advantages of Linked List

• InsertingEfficient insertion and deleting nodes is efficientdeletion since no 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 means lessreduces wasted space.

• Suitable for applications requiringwith large or frequently changing datasets.

• Uses non-contiguous memory blocks, making it useful in memory-limited systems.

Disadvantages of Linked List

• Direct access to an element is not possible; traversal is required from the start.start is required.

• Each node requires extra memory to store a pointer.

• More complex to implement and manage compared to arrays.

• Pointer mismanagement can lead tocause bugs, memory leaks, or segmentation faults.

ContohShort KodeCode SingkatExample

#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;
}

PenjelasanCode KodeExplanation::

• Node adalahis strukturthe dasarbasic structure of a Linked List.

• pushFront menambahkanadds a new node baruat dithe awalbeginning of the list.

• printList menelusuritraverses the list danand menampilkandisplays semuaall elemen.elements.