Linked List

Terminologi

Terdapat beberapa istilah yang akan sering digunakan dalam mendeskripsikan linked list.

• Node: Sebuah elemen data yang dapat berisikan suatu nilai atau informasi yang dibutuhkan serta pada setiap node mengandung pointer ke node selanjutnya.
• Head: Node pertama dari linked list.
• Tail: Node terakhir dari linked list.

Apa itu Linked List?

Linked list adalah struktur data linear, di mana elemen tidak disimpan di lokasi memori yang berdekatan. Elemen-elemen pada lineked list ditautkan menggunakan pointer seperti gambar dibawah ini:

Dari Gambar tersebut, satu node di linked list terdiri atas:

• Data atau informasi yang disimpan.
• Referensi (tautan) ke node selanjutnya.

Linked List vs Array

Perbedaan antara Linked List dengan Array:

No	Linked List	Array
1	Linked list tidak disimpan di lokasi memori yang berdekatan.	Array disimpan di lokasi memori yang berdekatan.
2	Ukurannya dinamis.	Ukurannya tetap.
3	Memori dialokasi pada run time.	Memori dialokasi pada compile time.
4	Menggunakan memori yang lebih banyak dibandingkan array karena menyimpan data dan referensi ke node selanjutnya.	Menggunakan memori yang lebih sedikit dibandingkan array.
5	Element membutuhkan traversal ke seluruh linked list.	Elemen dapat dengan mudah diakses.
6	Operasi insert dan delete membutuhkan waktu.	Operasi insert dan delete dilakukan dengan lebih cepat

Ilustrasi

Linked list dapat diilustrasikan dengan beberapa node yang saling terhubung satu dengan yang lain sehingga membentuk rangkaian yang saling berurutan. Contohnya terdapat list A dengan beberapa kumpulan data A =[2,6,8,9,15].

Operasi Dasar

• isEmpty Untuk memeriksa apakah list kosong atau tidak.

• pushBack

  Untuk menambahkan data baru dari belakang list. Untuk ilustrasinya terdapat pada gambar dibawah.

• pushFront

  Untuk menambahkan data baru dari depan list. Untuk ilustrasinya terdapat pada gambar dibawah.

• insertAt

  Untuk menambahkan data baru pada posisi yang diinginkan. Untuk ilustrasinya terdapat pada gambar dibawah.

• back Untuk mendapatkan data yang ada di paling belakang.

• front Untuk mendapatkan data yang ada di paling depan.

• getAt Untuk mendapatkan data pada posisi tertentu.

• popBack

  Untuk menghapus data yang berada di posisi paling belakang. Untuk ilustrasinya terdapat pada gambar dibawah.

• popFront

  Untuk menghapus data yang berada di posisi paling depan. Untuk ilustrasinya terdapat pada gambar dibawah.

• remove(x)

  Untuk menghapus data x yang pertama muncul dalam list. Untuk ilustrasinya terdapat pada gambar dibawah.

Variasi Linked List

• Singly-Linked List Setiap node memiliki data dan pointer ke node berikutnya. Untuk ilustrasinya terdapat pada gambar dibawah.

• Double-Linked List Terdapat penambahan pointer ke node sebelumnya dalam double-linked list. Sehingga dapat menuju pada node sebelumnya dan node selanjutnya. Dua tautan ini disebut dengan next dan prev. Untuk ilustrasinya terdapat pada gambar dibawah.

• Circular-Linked List Pada variasi ini elemen terakhir ditautkan ke elemen pertama. Ini membentuk lingkaran melingkar. Untuk ilustrasinya terdapat pada gambar dibawah.

Implementasi ADT: SinglyList

Representasi dan Implementasi yang akan dijelaskan dalam modul ini adalah Singly Linked List yang menyimpan tipe data int. Representasi akan dibawa ke dalam bentuk Abstract Data Type (ADT) yang nantinya akan menjadi tipe data baru bernama SinglyList.

Dalam implementasinya, kompleksitas waktunya yaitu:

Operasi	Keterangan	Kompleksitas Waktu
pushBack	Memasukkan data baru dari belakang.	O(N)
pushFront	Memasukkan data baru dari depan.	O(1)
insertAt	Memasukkan data baru pada posisi tertentu.	O(N) (Worst-case)
popBack	Menghapus node paling belakang.	O(N)
popFront	Menghapus node paling depan.	O(1)
remove(x)	Menghapus node pertama dengan data x.	O(N) (Worst-case)
front	Mendapatkan nilai node terdepan.	O(1)
back	Mendapatkan nilai node paling belakang.	O(N)
getAt	Mendapatkan nilai node pada posisi tertentu.	O(N) (Worst-case)
isEmpty	Memeriksa apakah list kosong.	O(1)

• Representasi Node

  Node direprsentasikan oleh struct bernama SListNode yang menyimpan variabel data bertipe int dan referensi kepada node selanjutnya next.

    typedef struct snode_t {
        int data;
        struct snode_t *next;
    } SListNode;
  

• Struktur SinglyList

    typedef struct slist_t {
        unsigned _size;
        SListNode *_head;
    } SinglyList;
  

• isEmpty

  Untuk memeriksa apakah list kosong, cukup dengan memeriksa apakah head dari list tersebut bernilai NULL atau tidak.

    bool slist_isEmpty(SinglyList *list) {
        return (list->_head == NULL);
    }
  

• pushBack

  Secara umum langkah-langkah untuk melakukan pushBack adalah sebagai berikut.

  • Membuat node baru
  • Jika list kosong, maka sudah jelas bahwa head-nya adalah node baru tadi.
  • Jika tidak kosong, telusuri hingga paling belakang, kemudian node paling belakang diarahkan kepada node baru. Penelusuran dilakukan dengan bantuan variabel temporary temp.

    void slist_pushBack(SinglyList *list, int value)
    {
        SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
        if (newNode) {
            list->_size++;
            newNode->data = value;
            newNode->next = NULL;
  
            if (slist_isEmpty(list))
                list->_head = newNode;
            else {
                SListNode *temp = list->_head;
                while (temp->next != NULL)
                    temp = temp->next;
                temp->next = newNode;
            }
        }
    }
  

• pushFront

  Untuk melakukan pushFront, langkah-langkahnya adalah sebagai berikut.

  • Membuat node baru.
  • Jika list kosong, jadikan node baru sebagai head.
  • Jika tidak kosong, maka jelas bahwa next dari node baru adalah head.

    void slist_pushFront(SinglyList *list, int value)
    {
        SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
        if (newNode) {
            list->_size++;
            newNode->data = value;
  
            if (slist_isEmpty(list)) newNode->next = NULL;
            else newNode->next = list->_head;
            list->_head = newNode;
        }
    }
  

• insertAt

  Operasi insertAt mempunyai proses yang cukup rumit. Terdapat beberapa kasus yang harus diperhatikan.

  1. Kasus 1: index 0
     • Cukup melakukan pushFront dan selesai.
  2. Kasus 2: index berada di akhir
     • Cukup melakukan pushBack dan selesai.
  3. Kasus 3: index berada di tengah
     • Buat node baru.
     • Dengan bantuan variabel temp, lakukan penelusuran hingga mencapai posisi node berada pada index -1.
     • Arahkan next dari node baru menuju node selanjutnya dari node terakhir hasil penelusuran.
     • Sambungkan node hasil penelusuran menuju node baru.

    void slist_insertAt(SinglyList *list, int index, int value)
    {
        if (slist_isEmpty(list) || index >= list->_size) {
            slist_pushBack(list, value);
            return;
        }
        else if (index == 0) {
            slist_pushFront(list, value);
            return;
        }
  
        SListNode *newNode = (SListNode*) malloc(sizeof(SListNode));
        if (newNode) {
            SListNode *temp = list->_head;
            int _i = 0;
  
            while (temp->next != NULL && _i < index-1) {
                temp = temp->next;
                _i++;
            }
            newNode->data = value;
            newNode->next = temp->next;
            temp->next = newNode;
            list->_size++;
        }
    }
  

• back

  Cukup dengan menelusuri hingga paling akhir dan return nilainya.

    int slist_back(SinglyList *list)
    {
        if (!slist_isEmpty(list)) {
            SListNode *temp = list->_head;
            while (temp->next != NULL)
                temp = temp->next;
            return temp->data;
        }
        return 0;
    }
  

• front

  Manfaatkan nilai data dari head.

    int slist_front(SinglyList *list)
    {
        if (!slist_isEmpty(list)) {
            return list->_head->data;
        }
        return 0;
    }
  

• getAt

  Untuk melakukan operasi getAt, caranya cukup mudah, yakni:

  • Lakukan penelusuran dengan mencatat index penelusurannya.
  • Ketika sudah mencapai index yang diinginkan, maka return nilai data yang ada pada node tersebut.

    int slist_getAt(SinglyList *list, int index)
    {
        if (!slist_isEmpty(list)) {
            SListNode *temp = list->_head;
            int _i = 0;
            while (temp->next != NULL && _i < index) {
                temp = temp->next;
                _i++;
            }
            return temp->data;
        }
        return 0;
    }
  

• popBack

  Untuk melakukan operasi popBack, dapat dilakukan dengan:

  • Melakukan penelusuran dengan bantuan dua node, yakni nextNode (node selanjutnya) dan currNode (node sekarang).
  • Jika next dari currNode kosong, maka artinya jumlah data hanya satu. Hapus langsung node tersebut.
  • Lakukan penelusuran hingga akhir.
  • Saat sampai akhir, hilangkan referensi dari node sekarang (currNode).
  • Hapus node selanjutnya (nextNode).

    void slist_popBack(SinglyList *list)
    {
        if (!slist_isEmpty(list)) {
            SListNode *nextNode = list->_head->next;
            SListNode *currNode = list->_head;
  
            if (currNode->next == NULL) {
                free(currNode);
                list->_head = NULL;
                return;
            }
  
            while (nextNode->next != NULL) {
                currNode = nextNode;
                nextNode = nextNode->next;
            }
            currNode->next = NULL;
            free(nextNode);
            list->_size--;
        }
    }
  

• popFront

  Operasi popFront dapat dilakukan dengan :

  • Tampung head pada variabel temp (temporary).
  • Mengganti head dengan referensi/next dari head.
  • Menghapus node temp.

    void slist_popFront(SinglyList *list)
    {
        if (!slist_isEmpty(list)) {
            SListNode *temp = list->_head;
            list->_head = list->_head->next;
            free(temp);
            list->_size--;
        }
    }
  

• remove(x)

  Untuk operasi remove(x), yakni menghapus data x yang pertama kali ditemukan, dapat dilakukan dengan cara berikut.

  1. Kasus 1: data yang dihapus dijumpai di depan
     • Cukup melakukan popFront dan selesai.
  2. Kasus 2: data yang dihapus dijumpai tidak di depan
     • Lakukan penelusuran dengan memeriksa apakah data pada node penelusuran sama dengan data yang hendak dihapus. Pada saat penelusuran, catat node sebelumnya (prev) dan node sekarang (temp).
     • Ketika menemukan datanya, berhenti.
     • Sambungkan node prev dengan next dari node sekarang.
     • Hapus node sekarang (temp).
  3. Kasus 3: data tidak dijumpai
     • Pada saat berhenti melakukan penelusuran, periksa apakah node bernilai NULL. Jika bernilai NULL, maka dapat dipastikan data tidak ditemukan.

    void slist_remove(SinglyList *list, int value)
    {
        if (!slist_isEmpty(list)) {
            SListNode *temp, *prev;
            temp = list->_head;
  
            if (temp->data == value) {
                slist_popFront(list);
                return;
            }
            while (temp != NULL && temp->data != value) {
                prev = temp;
                temp = temp->next;
            }
  
            if (temp == NULL) return;
            prev->next = temp->next;
            free(temp);
            list->_size--;
        }
    }