Materi dan Pengertian linked list atau Untaian dalam struktur data

Materi Linked List (Untaian)

Apa sih Itu Linked list ?

apa sih pengertian Linked List?

pertanyaan pertanyaan seperti itu pasti muncul dalam otak kawan kawan sekalian...!!!

Jangan lupa untuk baca  Queue atau Untaian sebelumnya untuk pemahaman linked list lebih mendalam

Linked list merupakan sekumpulan elemen bertipe sama, yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian struktur berupa rangkaian elemen saling berkait dimana setiap elemen dihubungkan elemen lain melalui pointer.

nah Pointer sendiri adalah  alamat elemen. Penggunaan pointer untuk mengacu elemen berakibat elemen-elemen bersebelahan secara logik walau tidak bersebelahan secara fisik di memory.

gambar 1.1 Linked list

Bentuk Umum :

1. Infotype sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list
2. Next address dari elemen berikutnya (suksesor)

Jika L adalah list, dan P adalah address, maka alamat elemen pertama list L dapat diacu dengan notasi : Sebelum digunakan harus dideklarasikan terlebih dahulu : Elemen yang diacu oleh P dapat dikonsultasi informasinya dengan notasi :

Linked list dalam struktur data

• Single linked list
  Pada gambar di atas tampak bahwa sebuah data terletak pada sebuah lokasi memori area. Tempat yang disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan sebutan node atau simpul.
  Setiap node memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan demikian hanya diperlukan sebuah variabel pointer. Susunan berupa untaian semacam ini disebut Single Linked List(NULL memilik nilai khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List pada titik akhirnya akan menunjuk ke NULL). 
  1. Pembuatan Single Linked List dapat menggunakan 2 metode:a. LIFO (Last In First Out), aplikasinya : Stack (Tumpukan)b. FIFO (First In First Out), aplikasinya : Queue (Antrean)
  2. Double Linked ListDouble Linked List adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu 1 field pointer yang menunjuk pointer berkutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta sebuah field yang berisi data untuk node tersebut. Circular double linked list next dan prev nya menunjuk kedirinya sendiri secara circular (membentuk pola bundar). Setiap node pada linked list mempunyai field yang berisi data dan pointer ke node berikutnya. Untuk pembentukan node baru, mulanya pointer next dan prev akan menunjuk kedirinya sendiri. Jika sudah lebih dari satu node, maka pointer prev akan menunjuk ke node sebelumnya, dan pointer next akan menunjuk ke node sesudahnya. Semua sel yang terdapat pada list disambungkan dengan pointer, sedangkan setiap sel. memiliki tiga komponen yaitu value, pointer ke sel berikutnya. Dengan memiliki dua buah pointer ini, maka double-linked list dapat diakses dengan dua arah, ke arah depan dan ke belakang. Dibutuhkan dua variabel pointer yaitu Head dan Tail. Head akan selalu menunjuk pada node pertama, sedangkan Tail akan selalu menunjuk pada node terakhir.Adapun pun Operasi operasi pada double linked list yaituOperasi-operasi Queue dengan Double Linked List
     1. IsEmptyFungsi 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.
     2. IsFullFungsi 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.
     3. EnQueueFungsi EnQueue berguna untuk memasukkan sebuah elemen ke dalam queue (head dan tail mula-mula meunjukkan ke NULL).
     4. DeQueueProcedure DeQueue berguna untuk mengambil sebuah elemen dari queue. Hal ini dilakukan dengan cara menghapus satu simpul yang terletak paling depan (head).
  3. Circular linked listCircular linked list merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head (node pertama). Jadi jika ada pointer menunjuk pada NULL.
     2 jenis linked list yaitu :
     a. single linked list
     b. double linked list.

Share this post