Single Linked List Pada C++

Selasa, 03 Maret 2020

Single Linked List Pada C++

Single Linked List merupakan suatu bentuk struktur data yang berisi kumpulan data yang disebut sebagai node yang tersusun secara sekuensial, saling sambung menyambung, dinamis, dan terbatas. Cara untuk menghubungkan satu node dengan node lainnya maka Linked List menggunakan pointer sebagai penunjuk node selanjutnya.

Node merupakan sebuah struct atau tipe data bentukkan yang menempati suatu lokasi memori secara dinamis yang terdiri dari beberapa field, minimal 2 buah field. Field tersebut adalah field untuk isi struct datanya sendiri dan 1 field arbitari bertipe pointer sebagai penunjuk node selanjutnya.

struct tnode {

          int value;

          struct tnode *next;

}

struct tnode *head = 0;

Kenapa menggunakan Linked List? Kenapa tidak menggunakan Array?

Array merupakan salah satu variabel yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu, ruang memori yang dipakai oleh array tersebut tidak dapat dihapus bila array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Setiap ingin menambahkan data, anda akan selalu menggunakan variabel pointer yang baru, maka akibatnya anda akan sangat banyak membutuhkan sebuah variabel pointer. Oleh karena itu sebaiknya menggunakan satu variabel pointer saja untuk menyimpan banyak data dengan menggunakan metode yang kita sebut dengan Single Linked List atau Linked List.

Perbedaan Array dan Linked List

Array:
- Statis
- Penambahan dan penghapusan data terbatas
- Random access
- Penghapusan Array tidak mungkin

Linked List:
- Dinamis
- Penambahan dan penghapusan tidak terbatas
- Sequential access
- Penghapusan mudah

Pembuatan Single Linked List 

1. Membuat struct node

struct TNode{
          int data;
          TNode *next;
}

Pembuatan struct bernama TNode yang berisi 2 field, yaitu pada field pertama dengan variabel data dengan tipe data integer dan field kedua yaitu next yang bertipe pointer dari TNode. Setelah selesai pembuatan struct, selanjutnya buat variabel head yang bertipe pointer dari TNode yang berguna untuk sebagai kepala dari linked list.

2. Membentuk node baru

Untuk pembentukan atau pembuatan node baru dapat menggunakan keyword new yang berarti untuk mempersiapkan sebuah node baru beserta alokasi memorinya, kemudian node tersebut akan di isi data dan kemudian pointer nextnya akan ditunjuk ke NULL.

TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = baru;

      3. Single Linked List menggunakan head

Deklarasi Pointer penunjuk kepala Single Linked List manipulasi Linked List tidak bisa dilakukan langsung ke node yang dituju, melainkan harus menggunakan suatu pointer penunjuk terlebih dahulu ke node pertama didalam linked list. Deklarasinya sebagai berikut :

TNode *head;

Fungsi Insialisasi Single Linked List
void int(){
read = NULL;
}

Function untuk mengetahui kosong atau tidaknya didalam Single Linked List jika pointer head tidak menunjuk pada suatu node maka kosong.

int isEmpty(){

if(head == NULL) return 1;

else return 0;

}

4. Penambahan data pada Single Linked List

Pada konsepnya adalah untuk mengkaitkan node baru dengan pointer atau head, yang kemudian head tersebut akan menunjuk pada data baru tersebut sehingga head akan tetap selalu menjadi data terdepan. 

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. pada akhir linked list, node terakhir menunjuk ke node terdepan sehingga linked list tersebut berputar, lalu node terakhir menunjuk lagi ke head.

Penghapusan data pada Single Linked List 

Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus dilakukan penunjukan terlebih dahulu dengan variabel hapus pada head, kemudian dilakukan pergeseran ke node berikutnya sehingga data setelah head menjadi head baru.

struct tnode *curr = head;

// if x is in head node

  if ( head->value == x ) {

  head = head->next;

  free(curr);

}

// if x is not in head node, find the location

  else {

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

  struct tnode *del = curr->next;

  curr->next = del->next;

  free(del);

}