Struktur Data - Linked List

Nama    : Aga Nafta Filadelfiano
NRP      : 5025251055
Kelas     : Struktur Data (D) 

Linked List

1. Definisi Linked List

Linked List adalah struktur data yang terdiri dari kumpulan objek yang disebut node, yang tersimpan secara tidak berurutan di dalam memori. Berbeda dengan array, elemen pada linked list tidak harus berada pada alamat memori yang berdekatan

Struktur Node pada Linked List
Data                  : Berisi nilai atau informasi yang disimpan pada node tersebut.
Pointer (Next)  : Berisi alamat memori dari node berikutnya dalam list.

Pada node terakhir, pointer-nya tidak menunjuk ke node lain, dimana biasanya berisi nilai NULL yang artinya node tersebut adalah akhir dari linked list.

Syntax Program:



Output:


Penjelasan Code:
struct Node {
    int data;
    Node* next;
};
Mendefinisikan kerangka dasar (blueprint) untuk sebuah elemen bernama Node. Karena ini adalah singly linked list, strukturnya hanya memiliki dua bagian yaitu data (untuk menyimpan angka) dan next (sebuah pointer yang akan menunjuk ke node berikutnya).

int main() {
    Node* node1 = new Node();
    Node* node2 = new Node();
    Node* node3 = new Node();
Membuat tiga buah pointer (node1, node2, node3) dan langsung mengalokasikan memori untuk masing-masing node tersebut secara dinamis menggunakan perintah new.


node1->data = 10;
node2->data = 20;
node3->data = 30;
Mengisi nilai atau informasi ke dalam variabel data milik masing-masing node.

node1->next = node2;
node2->next = node3;
node3->next = NULL;
Menghubungkan rantai node, dimana node1 menunjuk ke node2, dan node2 menunjuk ke node3. Karena node3 adalah node terakhir, pointer next-nya disetel ke NULL yang menandakan akhir dari linked list.

    Node* current = node1;
    while (current != NULL) {
        cout << current->data << " -> ";
        current = current->next;
    }
    cout << "NULL";

    return 0;
}
Membuat pointer bantu bernama current yang dimulai dari node1 (sebagai kepala/head). Looping while akan terus berjalan selama current belum mencapai NULL. Di dalam loop, program akan mencetak data dari node saat ini, lalu menggeser current ke node selanjutnya (current = current->next).

2. Doubly Linked List

Doubly linked list merupakan variasi linked list di mana setiap node memiliki dua pointer, yaitu next (menunjuk ke node setelahnya) dan prev (menunjuk ke node sebelumnya). Hal ini memungkinkan penelusuran data dari dua arah (maju dan mundur).

Syntax Program:


Output:


Penjelasan Code:
struct Node {
    int data;
    Node* next;
    Node* prev;
};
Memodifikasi struktur node, dimana ditambahkan pointer prev. Ini membuat node tidak hanya bisa melihat siapa di depannya (next), tapi juga siapa di belakangnya (prev).

node1->prev = NULL;
node1->next = node2;

node2->prev = node1;
node2->next = node3;

node3->prev = node2;
node3->next = NULL;
Menyambungkan node menjadi dua arah.

cout << "Maju (Forward): ";
Node* current = node1;
Node* lastNode = NULL;
while (current != NULL) {
    cout << current->data << " <-> ";
    lastNode = current;
    current = current->next;
}
cout << "NULL\n";
Menambahkan variabel lastNode = current di dalam looping. Tujuannya adalah untuk "mengingat" node terakhir sesaat sebelum current bergeser menjadi NULL. Hal ini penting agar memiliki titik awal untuk jalan mundur.

cout << "Mundur (Backward): ";
current = lastNode;
while (current != NULL) {
    cout << current->data << " <-> ";
    current = current->prev;
}
cout << "NULL\n";
Melakukan penelusuran mundur, dimana looping berjalan dengan menggeser current ke belakang menggunakan current = current->prev sampai berakhir di NULL (sebelum node1).

3. Singly Circular Linked List 

Circular linked list merupakan variasi linked list di mana pointer dari node terakhir tidak menunjuk ke NULL, melainkan melingkar kembali dan menunjuk ke node pertama (head).

Syntax Program:


Output:


Penjelasan Code:
node1->next = node2;
node2->next = node3;
node3->next = node1;
Mengubah pointer next dari node3 menjadi melingkar dan menunjuk kembali ke node1 (head). Ini akan menciptakan siklus tak berujung.

Node* current = node1;

if (node1 != NULL) {
    do {
        cout << current->data << " -> ";
        current = current->next;
    } while (current != node1);
    cout << "(kembali ke " << node1->data << ")" << endl;
}
Membuat program mencetak data satu kali, bergeser ke node berikutnya, lalu mengecek kondisi apakah sudah kembali ke node awal. Jika sudah, looping diberhentikan agar tidak terjadi infinity loop.

4. Operasi Dasar Linked List

  • Insert : Proses menambahkan node (data) baru ke dalam linked list. Penambahan ini bisa dilakukan di berbagai posisi: di awal (head), di akhir (tail), atau di tengah-tengah list.
  • Deletion : Proses menghapus node tertentu dari linked list (misalnya berdasarkan nilainya). Jika node di tengah dihapus, proses ini akan menyambungkan node sebelumnya langsung ke node setelahnya agar rantai tidak terputus.
  • Searching : Proses menelusuri linked list satu per satu dari awal (head) untuk mencari apakah suatu nilai data tertentu ada di dalam list tersebut. Biasanya mengembalikan nilai true/false atau posisi data.
  • Updating : Proses menelusuri list untuk mencari node yang menyimpan nilai lama, kemudian mengganti nilai tersebut dengan nilai data yang baru.

Syntax Program:


Output:


Penjelasan Code:
class LinkedList {
private:
    Node* head;
Membuat sebuah Class bernama LinkedList dan meletakkan head di bagian private. Hal ini membuat pointer head hanya bisa diakses dan diubah oleh fungsi-fungsi di dalam class ini saja, tidak bisa diubah sembarangan dari luar.

public:
    LinkedList() {
        head = NULL;
    }
Membuat fungsi yang otomatis dijalankan pertama kali saat kita membuat objek LinkedList baru. Fungsi ini akan memastikan linked list dimulai dalam keadaan kosong dengan mengatur head bernilai NULL.

//INSERT
void insert(int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->next = NULL;
  
    if (head == NULL) {
        head = newNode;
    } else {
        Node* temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    cout << "Inserted: " << val << endl;
}
Membuat fungsi untuk memasukkan data. Pertama, buat newNode (node baru) dan isi datanya dengan val. Jika list masih kosong (head == NULL), maka node baru tersebut langsung menjadi head. Jika list sudah ada isinya, buat pointer bantu bernama temp dari head. Lakukan looping hingga menemukan node paling akhir (temp->next != NULL). Setelah menemukan ekornya, sambungkan node terakhir  ke newNode.

 //DELETE
 void deleteNode(int val) {
    if (head == NULL) return;

        if (head->data == val) {
        Node* temp = head;
        head = head->next;
        delete temp;
        cout << "Deleted: " << val << endl;
        return;
    }
Membuat fungsi untuk menghapus data. Jika list kosong, langsung hentikan proses (return). Jika data yang mau dihapus ternyata ada di node pertama (head->data == val), simpan node pertama di temp, lalu geser head ke node kedua (head = head->next). Setelah itu, hancurkan node pertama tadi dari memori menggunakan perintah delete temp;.

    Node* current = head;
    Node* prev = NULL;
    while (current != NULL && current->data != val) {
        prev = current;
        current = current->next;
    }

    if (current == NULL) {
        cout << "Value " << val << " not found for deletion." << endl;
        return;
    }

    prev->next = current->next;
    delete current;
    cout << "Deleted: " << val << endl;
}
Jika data yang mau dihapus ada di tengah atau akhir, looping berjalan mencari data. Selama bergeser, prev akan selalu mengikuti satu langkah di belakang current. Jika current sampai NULL, berarti datanya tidak ada. Jika ketemu, lompat dengan cara menyambungkan node sebelum yang dihapus (prev->next) langsung ke node setelah yang dihapus (current->next). Terakhir, hapus current dari memori.

//SEARCH
bool search(int val) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == val) {
            return true;
        }
        current = current->next;
    }
    return false;
}
Membuat fungsi pencarian dengan menelusuri satu per satu (current = current->next). Jika di tengah jalan menemukan data yang cocok, langsung kembalikan nilai true (benar). Jika looping selesai sampai akhir tapi tidak ketemu, kembalikan false (salah).

//UPDATE
void update(int oldVal, int newVal) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == oldVal) {
            current->data = newVal;
            cout << "Updated: " << oldVal << " -> " << newVal << endl;
            return;
        }
        current = current->next;
    }
    cout << "Value " << oldVal << " not found for updating." << endl;
}
Membuat fungsi untuk mengupdate data dengan jalan dari head mencari oldVal. Begitu ketemu, langsung timpa isi datanya dengan newVal, cetak pesan sukses, lalu menghentikan fungsi dengan return.


    //ISI LINKED LIST
    void display() {
        Node* current = head;
        while (current != NULL) {
            cout << current->data << " -> ";
            current = current->next;
        }
        cout << "NULL" << endl;
    }
};
Membuat fungsi untuk mencetak seluruh isi linked list dengan menelusuri dari head hingga NULL dan mencetak data di tiap node yang dilewatinya. 

int main() {
    LinkedList list;

    cout << "PROSES INSERT" << endl;
    list.insert(10);
    list.insert(20);
    list.insert(30);
    list.insert(40);
    list.display();
Menginisialisasi variabel bernama list dari class LinkedList yang sudah dibuat. Kemudian, memanggil fungsi .insert() untuk memasukkan datanya. Setelah itu memanggil fungsi untuk menampilkan hasilnya.

    cout << endl << "PROSES SEARCHING" << endl;
    int searchVal = 20;
    if (list.search(searchVal)) {
        cout << searchVal << " is found in the list." << endl;
    } else {
        cout << searchVal << " is not found." << endl;
    }

    cout << endl << "PROSES UPDATING" << endl;
    list.update(20, 25);
    list.display();

    cout << endl << "PROSES DELETION" << endl;
    list.deleteNode(30);
    list.deleteNode(10);
    list.display();

    return 0;
}
Menguji coba setiap fungsi yang telah dibuat dan memastikan semuanya sudah berjalan sebagaimana mestinya.


Source Code: GitHub

Postingan populer dari blog ini

Curiculum Vitae - Aga Nafta Filadelfiano

Gambar
Nama       : Aga Nafta Filadelfiano NRP          : 5025251055 Kelas        : Struktur Data (D) Aga Nafta Filadelfiano Marina Emas Timur - Kota Surabaya 60111 - aganafta1667@gmail.com - 085748483716 DESKRIPSI DIRI      Mahasiswa S1-Teknik Informatika Institut Teknologi Sepuluh Nopember (ITS) yang diterima melalui jalur Seleksi Nasional Berdasarkan Prestasi (SNBP). Memiliki ketertarikan dan kemampuan dalam bidang teknologi, analisa data, dan berpartisipasi baik dalam bidang akademik maupun non-akademik. Dikenal sebagai pribadi yang disiplin, memiliki semangat belajar tinggi, serta menjunjung nilai kerja sama dan tanggung jawab. PENDIDIKAN INSTITUT TEKNOLOGI SEPULUH NOPEMBER S1 Teknik Informatika (2025 - Sekarang) IPK Sementara : 4.0/4.0 SMA Negeri 2 Madiun (2022 - 2025) Nilai Akhir : 92.11/100.00 PENGALAMAN UKM MUSIK ITS - Anggota September 2025 - Sekarang ( Surabaya, Jawa Timur) INI LHO ITS X SUMMITS -...
Baca selengkapnya

Struktur Data - Studi Kasus Stack

Gambar
Nama    : Aga Nafta Filadelfiano NRP      : 5025251055 Kelas     : Struktur Data (D)   Studi Kasus Stack 1. Konversi Infix ke Postfix Infix adalah notasi yang menempatkan operator di antara dua operand ( A + B ), sedangkan Postfix menempatkan operator setelah operand (contoh: A B + ). Prosedur Konversi Infix ke Postfix Baca (scan) ekspresi infix dari kiri ke kanan. Jika simbol yang dibaca adalah tanda kurung buka '(' , maka Push ke dalam stack. Jika simbol adalah operand (nilai/variabel) tambahkan ke hasil postfix (output). Jika simbol adalah tanda kurung tutup ')' : Pop semua elemen dari stack Tambahkan ke postfix Lakukan sampai ditemukan pasangan tanda kurung buka '(' Buang tanda kurung buka tersebut (tidak dimasukkan ke output) Jika simbol adalah operator (+, -, *, /, dll): Selama Stack tidak kosong, dan Operator di atas stack memiliki prioritas lebih tinggi atau sama,...
Baca selengkapnya

Struktur Data - Tipe Data & Array

Gambar
Nama  : Aga Nafta Filadelfiano NRP    : 5025251055 Kelas   : Struktur Data (D) TIPE DATA & ARRAY 1. Deklarasi Array Array adalah struktur data yang digunakan untuk menyimpan banyak data dengan tipe yang sama dalam satu variabel . Setiap data dalam array memiliki indeks yang dimulai dari 0 . Syntax Program Output Penjelasan int myarray[] = {1,3,5,2,4,6}; Membuat array bernama myarray dengan tipe data  int yang  berisi 6 elemen cout << myarray[i] << " "; Mencetak nilai array sesuai indeks i 2. Mencetak Alamat pada Indeks Array Setiap elemen array disimpan di alamat memori yang berbeda . Alamat memori bisa diketahui menggunakan operator &. Syntax Program Output Penjelasan cout << myarray[i] << endl; Menampilkan isi array &myarray[i]   & berarti address of 3. Input Array Array dapat diisi langsung oleh user  menggunakan input cin . Syntax Program Output Penjelasan Menerima input dari user : for (int ...
Baca selengkapnya