Tugas Linked List

Linked List

               Linked list adalah sebuah struktur data yang terdiri dari sebuah tahapan dari rekaman-rekaman data yang setiap datanya itu ada sebuah bidang(field) yang mencakupi suatu referensi mengenai rekaman di tahapan selanjutnya.

               Linked list sangatlah berguna khususnya dalam menyelesaikan masalah dalam waktu nyata atau waktu sebenarnya dimana beberapa unsur yang disimpan ialah tidak terprediksi dan juga saat tahapan akses dari unsur unsur itu.

               Linked list terdiri dari 2 tipe yaitu, single dan double linked list. Single linked list biasanya ditandai dengan memiliki satu jalur hubungan dari suatu senarai(list) penunjuk ke senarai(list) lainnya. sedangkan double linked list adalah linked list struktur data yang memiliki dua link, link yang satu memiliki referensi ke data selanjutnya dan yang satunya lagi memili referensi ke sata sebelumnya.

Linked List Ilustration

              Single Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

• Single linked list terdiri dari suatu unsur utama yang disebut Head
• Single linked list juga memiliki unsur yang dinamakan dengan First
• setiap link membawa suatu field data dan field link yang disebut Next
• Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
• link terakhir membawa link yang berisi null yang menandakan akhir dari list tersebut yang biasa di sebut Tail

              Double Linked list dapat diilustrasikan sebagai suatu rantai data(node), dimana setiap data menunjuk ke data selanjutnya dan juga data sebelumnya.

Seperti ilustrasi di atas, terdapat beberapa poin yang perlu dipertimbangkan :

• Double linked list terdiri dari suatu unsur utama yang disebut Head
• Double linked list memiliki yang namanya First dan Last
• Setiap link membawa field data dan dua field link yang disebut dengan Next dan Prev
• Setiap link yang terhubung dengan link selanjutnya menggunakan yang namanya Next Link
• Setiap link yang terhubung dengan link seblumnya menggunakan yang namannya Previous Link
• Link terakhir biasanya membawa null yang menandakan akhir dari list tersebut yang disebut dengan Tail

              Operation pada double linked terdapat operasi dasar yaitu, insert dan delete.

>>> Insert

         > Saat ingin menginsert node di belakang tail

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
 
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

         > saat memasukkan node pada posisi setelah suatu node

/* Given a node as prev_node, insert a new node after the given node */

void insertAfter(struct Node* prev_node, int new_data)

{

    /*1. check if the given prev_node is NULL */

    if (prev_node == NULL) {

        printf("the given previous node cannot be NULL");

        return;

    }

  

    /* 2. allocate new node */

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  

    /* 3. put in the data  */

    new_node->data = new_data;

  

    /* 4. Make next of new node as next of prev_node */

    new_node->next = prev_node->next;

  

    /* 5. Make the next of prev_node as new_node */

    prev_node->next = new_node;

  

    /* 6. Make prev_node as previous of new_node */

    new_node->prev = prev_node;

  

    /* 7. Change previous of new_node's next node */

    if (new_node->next != NULL)

        new_node->next->prev = new_node;

}

>>> Delete

          >Jika node di delete pada bagian head atau yang paling awal maka

head = head->next;

free(head->prev);

head->prev = NULL;

          >Jika node di delete pada bagian tail atau yang paling akhir maka

tail = tail->prev;

free(tail->next);

tail->next = NULL;

          >Jika node di delete pada bagian yang bukan head atau yang paling awal tail atau yang paling akhir maka

struct tnode *curr = head;

while ( curr->next->value != x ) curr = curr->next;

struct tnode *a   = curr;

struct tnode *del = curr->next;

struct tnode *b   = curr->next->next;

a->next = b;

b->prev = a;

free(del);

          >Jika node yang di delete adalah node yang hanya sendiri 

free(head);

head = NULL;

tail = NULL;

Circular Linked List

               Ada juga jenis linked list circular yang mencakupi circular single linked list dan circular double linked list.

1. Circular Single Linked List

               Dalam circular single linked list, node terakhir berisikan penunjuk ke node pertama. Pada circular linked list tidak ada tempat penyempinan nilai null dalam listnya

Biasanya dapat diilustrasikan sebagai berikut

2. Circular Double Linked List

              Dalam circular double linked list, setiap node memiliki dua pointer. Salah satu pointer itu menunjuk ke node yang selanjutnya dan pointer yang lain menunjuk ke node sebelumnya. Pada circular double linked list tidak terdapat nilai null pada pemnyimpanannya maka circular double linked list ini mirip dengan circular single linked list.