Tugas Latihan 9, 10, 11, 12

Linear Single Linked List


Linked List atau 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.

Linked list sering juga disebut dengan sebagai sebutan senarai brantai. Cara untuk menghubungkan satu node dengan node lainnya maka Linked List menggunakan pointer sebagai penunjuk node selanjutnya atau bisa disebut next.

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.

Ilustrasi Single Linked List :

Pada gambar di atas, data terletak pada sebuah lokasi dalam sebuah memory, tempat yang disediakan memory untuk menyimpan data disebut node ? simpul, setiap node memiliki pointer ( penunjuk ) yang menunjuk ke node berikutnya sehingga terbentuk suatu untaian yang disebut single LINKED LIST. Bila dalam single LINKED LIST pointer hanya dapat bergerak ke satu arah saja, maju / mundur, kanan / kiri, sehingga pencarian datanya juga hanya satu arah saja.

Pembuatan Single Linked List dapat menggunakan 2 metode:
  • LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)
  • FIFO (First In First Out), aplikasinya : Queue (Antrean)
Pembuatan Single Linked List

1. Mendeklarasikan dan Membuat Struct Node


Penjelasan :
- Pembuatan struct bernama TNode yang berisi 2 field, yaitu pada field pertama dengan variabel data dengna 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. Pembentukan Node Baru

Untuk pembentukan atau pembuatan node baru dapat menggunakan keyword new yang berarti untuk mempersiapkan sebuah node baru beserta alokasi memorinya, yang kemudian node tersebut akan diisi data dan kemudian pointer nextnya akan ditunjuk ke NULL.
3. Menginisialisasikan dan Menggunakan Node Head

Selanjutnya yaitu :
- Dibutuhkan satu buah variabel pointer yang telah dibuat tadi yaitu : head
- head tersebut akan selalu menunjuk pada node pertama


 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 di dalam linked list (dalam hal kasus ini adalah head). Deklarasinya sebagai berikut :

TNode *head; 

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


4. Penambahan Data

- Penambahan Data di Depan Single Linked List
Penambahan node baru akan dikaitkan di node paling depan, namun pada saat pertama kali atau data masing kosong bener, maka penambahan data dilakukan dengan cara head ditunjukkan ke node baru tersebut. Pada prinsipnya 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.


Ilustrasi dari Penambahan Data di depan :


 - Penghapusan Data pada Single Linked List
Berikut yaitu adalah sebuah Function untuk menghapus suatu data di Linked List terdepan atau hapus data depan di Linked List :



 Function atau Fungsi diatas akan menghapus data teratas (pertama) didepan yang ditunjuk oleh head pada linked list.

STACK DENGAN SINGLE LINKED LIST


Selain implementasi stack dengan array seperti telah dijelaskan sebelumnya, stack daat diimplementasikan dengan single linked list. Keunggulannya dibandingkan array adalah penggunaan alokasi memori yang dinamis sehingga menghindari pemborosan memori.
Misalnya pada stack dengan array disediakan tempat untuk stack berisi 150 elemen, sementara ketika dipakai oleh user stack hanya diisi 50 elemen, maka telah terjadi pemborosan memori untuk sisa 100 elemen, yang tak terpakai. Dengan penggunaan linked list maka tempat yang disediakan akan sesuai dengan banyaknya elemen yang mengisi stack.

Dalam stack dengan linked list tidak ada istilah full, sebab biasanya program tidak menentukan jumlah elemen stack yang mungkin ada (kecuali jika sudah dibatasi oleh pembuatnya). Namun demikian sebenarnya stack ini pun memiliki batas kapasitas, yakni dibatasi oleh jumlah memori yang tersedia.

Operasi-operasi untuk Stack dengan Linked List

•        IsEmpty
Fungsi memeriksa apakah stack yang adamasih kosong.
•        Push
Fungsi memasukkan elemen baru ke dalam stack. Push di sini mirip dengan insert dalam single linked list biasa.
•        Pop
Fungsi ini mengeluarkan elemen teratas dari stack.
•        Clear
Fungsi ini akan menghapus stack yang ada.
Ilustrasi untuk Stack dengan menggunakan simpul Head



Push : Selalu Kiri
Pop : Selalu Kanan

Fungsi-fungsi yang diperlukan :

1)Deklarasi struktur simpul dan pointer yang diperlukan



2) Inisialisasi stack



3) Fungsi pembuatan simpul baru



4) Fungsi pembuatan simpul Head



5) Fungsi PUSH/Insert Kiri



6) Fungsi POP/Delete Kiri



Program Stack dengan Linked List :

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next;
};
struct Node* top = NULL;
void push(int val) {
   struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
   newnode->data = val;
   newnode->next = top;
   top = newnode;
}
void pop() {
   if(top==NULL)
   cout<<"Stack Underflow"<<endl;
   else {
      cout<<"The popped element is "<< top->data <<endl;
      top = top->next;
   }
}
void display() {
   struct Node* ptr;
   if(top==NULL)
   cout<<"stack is empty";
   else {
      ptr = top;
      cout<<"Stack elements are: ";
      while (ptr != NULL) {
         cout<< ptr->data <<" ";
         ptr = ptr->next;
      }
   }
   cout<<endl;
}
int main() {
   int ch, val;
   cout<<"1) Push in stack"<<endl;
   cout<<"2) Pop from stack"<<endl;
   cout<<"3) Display stack"<<endl;
   cout<<"4) Exit"<<endl;
   do {
      cout<<"Enter choice: "<<endl;
      cin>>ch;
      switch(ch) {
         case 1: {
            cout<<"Enter value to be pushed:"<<endl;
            cin>>val;
            push(val);
            break;
         }
         case 2: {
            pop();
            break;
         }
         case 3: {
            display();
            break;
         }
         case 4: {
            cout<<"Exit"<<endl;
            break;
         }
         default: {
            cout<<"Invalid Choice"<<endl;
         }
      }
   }while(ch!=4);
   return 0;
}

Output :



Linear Double Linked List
 


Double Linked List adalah salah satu contoh lain implementasi linked list selain single. Sesuai namanya, Double artinya blok data yang kita miliki akan memiliki 2 penunjuk kiri dan kanan untuk menentukan data sebelum/sesudahnya. Berbeda dengan single linked list yang hanya mempunyai satu penunjuk, double linked list mempunyai 2 penunjuk kiri dan kanan untuk menentukan urutan datanya. Agar lebih paham, bisa perhatikan gambar di bawah ini :
Dalam pembelajaran struktur data, kita akan lebih sering mengenal dengan istilah :
  •   Push untuk menambah data.
  •   PushHead – Menambah data ke barisan paling awal
  •  PushTail – Menambah data ke barisan paling akhir
  •  PushMid – Menambah data ke barisan di tengah (sorting) 
  •  Pop untuk menghapus data.
  •   PopHead – Menghapus data paling awal
  •  PopTail – Menghapus data paling akhir
  •  PopMid – Menghapus data ditengah (sesuai parameter value)


QUEUE DENGAN DOUBLE LINKED LIST


Selain menggunakan array, queue juga dapat dibuat dengan linked list. Metode linked list yang digunakan adalah double linked list.
Operasi-operasi Queue dengan Double Linked List
  • IsEmpty

Fungsi IsEmpty berguna untuk mengecek apakah queue masih kosong atau sudah berisi data. Hal ini dilakukan dengan mengecek apakah head masih menunjukkan pada Null atau tidak. Jika benar berarti queue masih kosong.
  • IsFull

Fungsi IsFull berguna untuk mengecek apakah queue sudah penuh atau masih bisa menampung data dengan cara mengecek apakah Jumlah Queue sudah sama dengan MAX_QUEUE atau belum. Jika benar maka queue sudah penuh.
  • EnQueue

Fungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
  • DeQueue

Procedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).

Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.


Komentar

Posting Komentar

Postingan Populer