Linked List ( Data Structures ): Linked List

Linked List

Linked list adalah data structure yang linear, dimana data-data tidak disimpan berdempetan diantara data-data yang lainnya, melainkan disambungkan oleh suatu pointer.

Berikut adalah gambaran dari linked list :

Kasarnya, linked list terdiri atas simpul-simpul yang di dalamnya terdapat bagian data dan refrensi(link) untuk ke simpul yang berikutnya, yang berdasarkan gambar di atas digambarkan sebagai kotak kosong.

Linked List memberikan kita kebebasan untuk melakukan insertion (pemasukan) dan deletion (penghapusan) elemen dimanapun dalam suatu data

Sebelumnya, kita sudah mempelajari array, yang juga merupakan kumpulan dari elemen-elemen data.

Loh, jadi kenapa kita belajar tentang linked list lagi? Kan sama-sama kumpulan data?

Array dan Linked List mungkin sekilas terlihat mirip. Tetapi apabila kita lihat lebih lanjut lagi, linked list memilikki 3 perbedaan yang signifikan dengan Array. Perbedaan - perbedaan tersebut yakni :

Array merupakan kumpulan dari elemen-elemen data, dimana Linked List merupakan kumpulan dari elemen data yang dimasukan ke dalam satu simpul bersamaan dengan penyambung ke simpul yang lainnya
Array menyusun data secara konsekuensial (berurutan). Contoh : {0; 1; 2; 3; 4; 5; NULL}. Sedangkan Linked List tidak menyimpan simpul-simpulnya secara berurutan.
Dalam Array, kita dapat mengakses data secara acak. Sedangkan dalam Linked List. untuk mengakses data kita harus secara konsekuensial (berurutan).

Linked List sendiri terdiri atas dua jenis, yaitu :

Single Linked List, dan
Double Linked List.

Berikut adalah source code untuk Single Linked List sederhana ( 3 node) :

#include <bits/stdc++.h> 

using namespace std;  

class Node 

{

public: 

    int data; 

    Node* next; 

};

{ 

    Node* head = NULL; 

    Node* second = NULL; 

    Node* third = NULL; 

    Node* fourth = NULL;

    // buat 3 node baru

    head = new Node(); 

    second = new Node(); 

    third = new Node(); 

    fourth = new Node();

    head->data = 1; // tentukan data di node pertama

    head->next = second; // sambungkan node pertama dengan node kedua 

    second->data = 2; // tentukan data di node kedua

    second->next = third; // sambungkan node kedua dengan node ketiga

    third->data = 3; // tentukan data di node ketiga 

    third->next = fourth;

    fourth->data = 4;

    fourth->next = NULL;

// narasumber : rathbhupendra via geeksforgeeks.org

Hasil Linked List dari code di atas dapat dilihat di gambar di bawah ini :

Akan tetapi Single Linked List (SLL) memilikki beberapa kekurangan daripada Double Linked List (DLL), contohnya adalah

DLL dapat dilintasi maju maupun mundur
Operasi penghapusan di DLL lebih efisien apabila pointer ke node yang hendak dihapus diberikan
Kita dapat langsung memasukkan node baru ke node yang kita inginkan. Maksudnya, dri SLL kita harus memutari kembali Linked List kita untuk memasukkan node yang baru, dimana DLL ini kita tidak perlu memutari ulang Linked List kita

DLL juga memilikki beberapa kekurangan, diantaranya :

Setiap node DLL memerlukan tempat lebih untuk pointer ke node sebelumnya, akan tetapi kita masih dapat membuat node DLL dengan 1 pointer.
Semua operasi memerlukan pointer ke node sebelumnya yang extra. Contohnya di proses Insertion (pemasukan), kita harus mengatur pointer ke node yang sebelumnya dan pointer ke node yang berikutnya secara bersamaan

Gambar berikut merupakan contoh DLL:

Selain SLL dan DLL standar, ada juga Circular Single Linked List dan Circular Double Linked List. Circular Linked List adalah Linked List yang node terakhirnya memilikki pointer ke node yang pertama. Oleh karena itu, tidak ada value NULL di Circular Linked List.

Berikut adalah gambar dari Linked List- Linked List tersebut :

Circular Single Linked List