LINKED LIST

Linked List adalah salah satu bentuk struktur data yang memuat kumpulan data (node) yang menempati memori dinamis dan setiap node menunjuk kepada node lain melalui pointer sehingga saling berhubungan dengan berurutan.

Dynamic Memory (Memori Dinamis) yaitu lokasi di memori dapat beragam dan jumlah memori fleksibel yaitu disesuaikan dengan ukuran data saat program dijalankan, serta memungkinkan untuk membebaskan kembali memori yang sudah tidak digunakan sehingga program dapat berjalan secara efisien.

Linked List  terbagi menjadi 2 jenis yaitu Single Linked List dan Double Linked List.

1. Single Linked List 

Single Linked List merupakan linked list yang setiap nodenya mempunyai 2 field yaitu field yang berisi data dan field yang berisi pointer ke node berikutnya, sehingga pointer bergerak hanya ke satu arah saja. 

Penjelasan komposisi node:

Node pertama memiliki field yang berisi data yaitu 35 dan field yang berisi pointer ke node kedua.
Node kedua memiliki field yang berisi data yaitu 27 dan field yang berisi pointer ke NULL.
Pada akhir linked list, node terakhir menunjuk ke NULL yang berarti berhenti membaca isi linked list.

Node pertama dalam linked list biasanya ditunjuk oleh pointer head dan node terakhir ditunjuk oleh pointer tail.

Operasi yang dapat dilakukan yaitu menambahkan data disebut insert / push dan menghapus data disebut delete / pop. 
Push depan berarti data yang paling baru dimasukkan menjadi head / data pertama dalam linked list. Sebaliknya, push belakang berarti data yang paling baru dimasukkan menjadi tail dalam linked list. Push tengah berarti menambahkan data baru diantara data-data yang sudah ada. Hal ini berlaku juga untuk operasi pop.

Contoh program bahasa C membuat Single Linked List.
#include<stdio.h>
#include<stdlib.h>

struct node{
    int num;
    // menyimpan data berupa angka
    struct node *next;
    // pointer yang menyimpan alamat data selanjutnya
} *head, *tail, *curr;
//head adalah pointer yang menyimpan alamat data pertama
//tail adalah pointer yang menyimpan alamat data terakhir
//curr adalah pointer yang digunakan sebagai temporary variabel

// memasukkan data dari depan
void pushDepan(int n){
    // alokasi memori untuk data baru
    curr = (struct node*) malloc(sizeof(struct node));
    // memasukkan data ke struct
    curr->num = n;
   
    // apabila linked list masih kosong / tidak ada data
    if(head == NULL){
        head = tail = curr;
        tail->next = NULL;
    }
    // apabila linked list sudah ada data
    else{
        curr->next = head;
        head = curr;
    }
}

// memasukkan data dari belakang
void pushBelakang(int n){
    // alokasi memori untuk data baru
    curr = (struct node*) malloc(sizeof(struct node));
    // memasukkan data ke struct
    curr->num = n;
   
    // apabila linked list masih kosong / tidak ada data
    if(head == NULL){
        head = tail = curr;
        tail->next = NULL;
    }
    // apabila linked list sudah ada data
        tail->next = curr;
        tail = curr;
        tail->next = NULL;
}

// memasukkan data dari tengah
void pushTengah(int n){
    //alokasi memory untuk data baru
    curr = (struct node*) malloc(sizeof(struct node));
    //assign data ke dalam struct
    curr->num = n;
   
    //apabila linked list kosong/tidak ada data
    if(head == NULL){
        head = tail = curr;
    }
    // apabila umur data yang baru dimasukkan lebih baru dari umur data pertama (head)
    else if(curr->num < head->num){
        pushDepan(n);
    }
    //jika umur data yang baru dimasukkan lebih besar dari umur data terakhir (tail)
    else if(curr->num > tail->num){
        pushBelakang(n);
    }
    //push ditengah-tengah
    else{
        struct node *temp = head;
        //mencari posisi data yang sesuai untuk diselipkan
        while(temp->next->num < curr->num){
            temp = temp->next;
        }
        curr->next = temp->next;
        //mengarahkan penunjuk ke alamat data baru
        temp->next = curr;
    }
}

// menghapus data dari depan
void popDepan(){
    //inisialisasi curr sebagai head
    curr = head;
    // apabila linked list kosong / tidak ada data
    if(head == NULL){
        //cetak tidak ada data
        printf("NO DATA.\n");
    }
    //jika head dan tail itu sama (hanya 1 data)
    else if(head == tail){
        //head dan tail dikosongkan
        head = tail = NULL;
        //hapus data curr (head)
        free(curr);
    }
    else{
        // mengatur head menjadi data selanjutnya dari head
        head = head->next;
        // hapus data curr (head)
        free(curr);
    }
}

// menghapus data dari belakang
void popBelakang(){
    //jika head kosong (tidak ada data)
    if(head == NULL){
        //cetak tidak ada data
        printf("NO DATA.\n");
    //jika head dan tail itu sama (hanya 1 data)
    }else if(head == tail){
        //head dan tail dikosongkan
        head = tail = NULL;
        //hapus data current (head)
        free(curr);
    }else{
        //buat variabel penampung baru dan assign nilai mulai dari head
        struct node *temp = head;
        //looping untuk mencari posisi 1 data sebelum tail
        while(temp->next != tail){
            //temp diubah menjadi 1 data selanjutnya
            temp = temp->next;
        }
        //set data current menjadi tail
        curr = tail;
        //set tail menjadi 1 data sebelum tail (hasil looping)
        tail = temp;
        //hapus data current (tail)
        free(curr);
        //data setelah next dikosongkan/pointer next punya tail diberi NULL
        tail->next = NULL;
    }
}

// menghapus data dari tengah
void popTengah(int n){
    //jika head kosong (tidak ada data)
    if(head == NULL){
        printf("NO DATA.\n");
    }
    //jika umur si head(data pertama) sama dengan data umur yang mau dihapus
    else if(head->num == n){
        popDepan();
    }
    //jika umur si tail(data terakhir) sama dengan data umur yang mau dihapus
    else if(tail->num == n){
        popBelakang();
    }
    else {
        //buat variabel penampung baru dan assign nilai mulai dari head
        struct node *temp = head;
        //looping untuk mencari posisi 1 data sebelum tail
        while(temp->next->num != n && temp != tail){
            //temp diubah menjadi 1 data selanjutnya
            temp = temp->next;
        }
        //set data current menjadi data selanjutnya dari temp
        curr = temp->next;
        //data selanjutnya dari temp diubah menjadi 2 data setelah temp
        temp->next = temp->next->next;
        //hapus data current
        free(curr);
    }
}

// menghapus semua data
void popAll(){
    while(head != NULL){
        popDepan();
    }
}

// mencetak data
void print(){
    curr = head;
    while(curr != NULL){
        printf("%d ",curr->num);
        curr = curr->next;
    }
    printf("\n");
}

int main(){
    pushBelakang(90);
    pushBelakang(58);
    pushBelakang(34);
    printf("Hasil push belakang:\n");
    print();
    printf("\n");
   
    popAll();
   
    pushDepan(90);
    pushDepan(58);
    pushDepan(34);
    printf("Hasil push depan:\n");
    print();
}

Output:

2. Double Linked List

Double Linked List benar-benar mirip seperti Single Linked List, opeasi yang dilakukan pun mirip seperti Single Linked List. Perbedaannya hanya pada setiap nodenya memiliki tambahan 1 field yang berisi pointer ke node sebelumnya, sehingga pointer bergerak kedua arah.

Node memiliki field yang berisi data yaitu 24, field yang berisi pointer ke selanjutnya dan field yang berisi pointer ke sebelumnya.

Node pertama (head) memiliki pointer yang menunjuk ke selanjutnya yaitu node kedua (5) dan menunjuk ke sebelumnya yaitu NULL.
Node kedua memiliki pointer yang menunjuk ke selanjutnya yaitu node ketiga (tail) dan menunjuk ke sebelumnya yaitu node pertama (head).
Node ketiga (tail) memiliki pointer yang menunjuk ke selanjutnya yaitu NULL dan menunjuk ke sebelumnya yaitu node kedua (5).
 
Contoh berikut adalah program bahasa C inisialisasi membuat Double Linked List.
 
#include<stdio.h>
#include<stdlib.h>

struct node {
    int num;
    // menyimpan data berupa angka
    struct node *next;
    // pointer yang menyimpan alamat data selanjutnya
    struct node *prev;
    // pointer yang menyimpan alamat data sebelumnya
} *head, *tail, *curr;
//head adalah pointer yang menyimpan alamat data pertama
//tail adalah pointer yang menyimpan alamat data terakhir
//curr adalah pointer yang digunakan sebagai temporary variabel