LINKED LIST - TEKNIK INFORMATIKA

Linked List 1

Linked List atau senarai berantai adalah struktur data yang dibangun dari satu atau lebih node yang menempati lokasi memori secara dinamis dan disusun saling sambung – menyambung.

Elemen data yang dihubungkan dengan link pada Linked List di sebut node.

Perbedaan array dan linked list :

·         Array

1.      Bersifat statis

2.      Penambahan atau penghapusan data terbatas

3.      Random access

·         Linked List

1.      Bersifat dinamis

2.      Penambahan atau penghapusan data tidak terbatas

3.      Sequantial access

Macam – macam pointer yang terdapat dalam linked list yaitu :

• Head : elemen yang berada pada posisi pertama dalam suatu linked list
• Tail : elemen yang berada pada posisi terakhir dalam suatu linked list
• Curr : elemen yang berada pada linked list dan pointer ini bisa pindah - pindah
• Next
• Prev

Jumlah head, tail,dan curr hanya ada 1 sedangkan next dan prev jumlahnya sesuai data yang ada

.

Memory allocation Dinamic

Jika memerlukan untuk mengalokasikan memori secara dinamis (dalam runtime) dapat menggunakan malloc di C / C++;

Rumus :

struct = (struct data*) malloc(sizeof(struct data);

Contoh:

Int *px = (int*)malloc(sizeof(int));

char *px = (char*)malloc(sizeof(char));

struct nama *curr = (struct nama*)malloc(sizeof(struct nama));

Ada 4 macam linked list yaitu :

• Single Linked List
• Single Linked List adalah kumpulan dari node yang saling berhubungan dengan node lain melalui sebuah pointer(next).
• Double Linked Lis
• Double linked list adalah linked list dengan node yang memiliki data dan dua buah pointer(next dan prev) yang menunjuk ke node sebelum dan node sesudah.
• Circular Linked List
• Circular linked list adalah suatu linked list dimana tail / node terakhir menunjuk ke head/node pertama.
• Multiple Linked List
• Multiple linked list adalah linked list yang memiliki lebih dari 2 variabel pointer.

Single Linked List ketika belum ada data (ketika head == NULL)

curr ->angka = data; (misalkan diketahui int angka)

head = curr;

tail = curr;

tail ->next = NULL

Single Linked List Insert menambah data di belakang

Awal

Ketika ada data baru

Ketika data baru mau disambungkan dengan data lama

head-> next = curr;

curr = tail;

tail ->next = NULL; (baca: next yang ada di tail = NULL)

Ketika ada beberapa node terjadi kesalahan pada head -> next = curr; sehingga berubah menjadi tail ->next = curr; misalkan ada 3 node , pada saat node ketiga disambung ke node 2 maka head tidak bekerja melainkan tail.

Jadi code yang benar adalah:

tail -> next = curr;

Curr = tail;

tail -> next = NULL;

Single Linked List Insert menambah data di depan

Awal

Ketika ada data baru

Katika mau di sambungkan

 curr -> next = head;

head = curr;

Single Linked List Insert menambah data di tengah

Contoh:

Data baru

Ketika ada data mau di masukkan

Karna 12 mau dimasukkan di deretan angka dari yang terbesar ke terkecil maka nilai 12 harus ada diantara 15 dan 10. Caranya ambil 2 pointer baru , misalkan pointer x dan y.

x -> next = curr;

curr -> next = y;

x = head;

while(x -> next -> angka > curr ->angka){

      x = x -> next;

}

y = x -> next;

x -> next = curr;

curr -> next = y;

Untuk mencetak di program C / C++ adalah

curr = head;

while(curr != NULL){

           printf("%d ",curr ->angka);

           curr = curr->next;

}

Hapus Single Linked List

Untuk menghapus di linked list menggunakan free.

Rumus: free(curr);

Artinya tempat reservasi di hapus/ hapus allocation memory

Hapus depan

if(head ->angka==x){

               curr = head;

               head = head->next;

               free(curr);

}

Ket : angka = deretan dari banyak angka , x = nilai yang dihapus

Hapus tengah

If(tail->angka==x){

              curr = head;

              while(curr->next!=tail){

                   curr= curr->next;

             }

             free(tail);

             tail=curr;

             tail->next = NULL;

}

Ket : angka = deretan dari banyak angka , x = nilai yang dihapus

Hapus belakang

curr = head;

while(curr->next->score!=x){

     curr = curr->next;

}

temp = curr->next;

curr->next=temp->next;

free(temp);

Ket : angka = deretan dari banyak angka , x = nilai yang dihapus