Tuesday, February 25, 2020

LINKED LIST

LINKED LIST

Pengertian Linked List
Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat/referensi dari record selanjutnya (dalam urutan). Elemen data yang dihubungkan dengan link pada linked list disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail. Head adalah elemen yang berada pada posisi pertama dalam suatu linked list. Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list.

Terdapat beberapa macam Linked List, yaitu :
  1. Single Linked List
  2. Double Linked List

Single Linked List

Single Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya. Biasanya field pada tail menunjuk ke NULL.

Operasi Pada Single Linked List 
1.     Insert = Istilah  Insert berarti menambahkan  sebuah  simpul baru ke dalam  suatu linked  list.
2.     Konstruktor = Fungsi ini membuat sebuah  linked  list yang baru dan masih kosong. 
3.     IsEmpty = Fungsi ini menentukan apakah  linked list kosong atau  tidak.
4.     Find First = Fungsi ini mencari elemen pert ama dari linked  list 
5.     Find Next = Fungsi ini mencari elemen  sesudah elemen yang ditunjuk now. 
6.     Retrieve = Fungsi  ini  mengambil  elemen  yang  ditunjuk  oleh  now.  Elemen  tersebut  lalu dikembalikan oleh fungsi. 
7.     Update = Fungsi ini mengubah elemen yang ditunjuk oleh  now dengan  isi dari  sesuatu. 
8.     Delete Now = Fungsi  ini  menghapus  elemen  yang  ditunj uk  oleh  now.  J ika  yang  dihapus  adalah elemen pertama dari  linked  list (head), head akan berpindah ke elemen berikut. 


Double Linked List
Double Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.



Operasi –operasi pada Double Linked List
  1. Insert Tail = Fungsi  insert  tail  berguna  untuk  menambah  simpul  di  belakang  (sebelah  kanan)  pada sebuah linked list. 
  2. Insert Head = Sesuai dengannamanya, fungsi Insert Head berguna untuk menambah simpul di depan (sebelah  kiri).   Fungsi  ini  tidak  berada  jauh  dengan  fungsi  Insert  Tail    yang  t elah dijelaskan  sebelumnya.
  3. Delete Tail = Fungsi  Delete  Tail  berguna  untuk  menghapus  simpul  dari  belakang.  Fungsi  ini merupakan kebalikan dari fungsi I nsert Tail yang menambah simpul dibelakang. Fungsi Delete  Tail  akan  mengarahkan  Now  kepada  Tail  dan  kemudian  memanggil  fungsi Delete Now.
  4. Delete Head  = Fungsi  Delete  Head  merupakan  kebalikan  dari  fungsi  Delete  Tail  yang  menghapus simpul  dari  belakang,  sedangkan  Delete  Head  akan  menghapus  simpul  dari  depan (sebelah  kiri).  Fungsi  Delete  Head  akan  mengarahkan  Now  kepada  Head  dan kemudianm memanggil fungsi Delete Now.

CIRCULAR DAN NON-CIRCULAR

1. Linked List Circular

Double Linked List
Pengertian secara umumnya DLLC itu Linked list yang menggunakan pointer, dimana setiap node memiliki 3 field, yaitu: 1 field pointer yang menunjuk pointer berikutnya "next", 1 field menunjuk pointer sebelumnya " prev ", 1 field yang berisi data untuk node tersebut . 

Double Linked List Circular pointer next dan prev nya menunjuk kedirinya sendiri secara circular. Bentuk Node DLLC 


Single Linked List
Single Linked List Circular (SLLC) adalah Single Linked List yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node terdepannya. 



2. Linked List Non Circular

Double Linked List Non Circular (DLLNC) adalah Double Linked List yang memiliki 2 buah pointer yaitu pointernext dan prev. Pointer next menunjuk pada node setelahnya dan pointer prev menunjuk pada node sebelumnya. 

Pengertian: Double : artinya field pointer-nya dua buah dan dua arah, ke node sebelum dan sesudahnya. Linked List : artinya node-node tersebut saling terhubung satu sama lain. Non Circular : artinya pointer prev dan next-nya akan menunjuk pada NULL. 



Single Linked List Non Circular (SLLNC) Adalah Linked List yang pointer nya selalu mengarah ke Node yang menampung *next bernilai NULL, jadi arahnya tidak menunjuk pointer didepannya sehingga tidak dapat kembali ke pointer - pointer sebelumnya. SLLNC ini juga memiliki 2 bagian, ada Tambah dan ada Hapus, masing - masing bagian ini juga masih meliputi 3 fungsi lain yaitu Belakang, Tengah, dan depan. untuk Contoh Tambah & Hapus (Depan & belakang).


Kita akan sering mengenal kata Push dan Pop. Apa itu Push dan Pop?
1.  Push digunakan 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)
2.  Pop digunakan untuk menghapus data
     - PopHead -  Menghapus data paling awal
     - PopTail - Menghapus data paling akhir
     - PopMid - Menghapus data di tengah (sesuai parameter value)

Perbedaan Singly Linked List, Double Linked List, Dan Circular Linked List

  1. Singly Linked List merupakan suatu linked list yang hanya memiliki satu variabel pointer saja. Dimana pointer tersebut menunjuk ke node selanjutnya, biasanya field pada tail menunjuk ke NULL.
  2. Doubly Linked List merupakan suatu linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunjuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke NULL.
  3. Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi tidak ada pointer yang menunjuk NULL.

Linked List vs Array

Array : 
- kumpulan linear elemen data
- Menyimpan nilai dilokasi memori yang berurutan
- Dapat acak dalam mengakses data

Linked List :
- Kumpulan linear node
- Tidak menyimpan nodenya dilokasi memori yang berurutan
- Dapat diakses hanya secara berurutan








Referensi :
http://rizkiyantikolono.blogspot.com/p/1-penjelasan-dari-linked-list-linked.html
https://oneeio13.blogspot.com/2012/07/pengertian-macam-macam-dan-penggunaan.html
https://www.mahirkoding.com/struktur-data-single-linked-list-dengan-bahasa-c/
http://temanbukuku.blogspot.com/2016/01/operasi-operasi-dasar-single-dan-double.
http://www.mampirlah.com/teknik-informatika/perbedaan-sll-dll-dan-cll.html

Terima Kasih.




Dibuat oleh : 
Livia Leonita
NIM : 2301905726
Class : CB01