Apa itu Linked List?

Apa itu Linked List?

Linked List adalah bagian dari Struktur Data

Linked list atau dikenal juga dengan sebutan senarai berantai adalah struktur data yang terdiri dari urutan record data dimana setiap record memliki field yang menyimoan alamat/ referensi dari record selanjutnya (dalam urutan) elemen data yang dihubungkan dengan link pada linked list disebut Node. Biasanya didalam suatu lnked list, terdapat istilah head and tail.

•             Head adalah elemen yang berada pada posisi pertama dalam suatu linked list

•             Tail adalah element yang berada pada posisis terakhir dalam suatu linked list

Ada Beberapa macam Linked List, yaitu:

1.            Single Linked List

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

Contoh:

Contoh Codingannya :

 struct Mahasiswa{

  char nama[25];

  int usia;

  struct Mahasiswa *next;

}*head,*tail;

2.            Double Linked List

Double Linked List Merupakan suatau linked list yang memiliki dua variabel pointer yaitu pointer yang menunjuk ke node selanjutnya dan pointer yang menunuk ke node sebelumnya. Setiap head dan tailnya juga menunjuk ke  NULL Contoh:

Contoh Codingannya:

Struct Mahasiswa{

 char nama[25];

 int usia;

 struct Mahasiswa *next,*prev;

}*head,*tail;

3.            Circular Linked List

Circular Linked List merupakan suatu linked list dimana tail (node terakhir) menunjuk ke head(node pertama).Jadi tidak ada pointer yang menunjuk NULL ada 2 jenis Circular Linked List Yaitu:

•             Circular Single Linked List

Contoh:

•             Circular Double Linked List

Contoh:

4.            Multiple Linked List

Multi Linked List Merupakan Suatu Linked List yang Memiliki Lebih dari 2 buat variabel pointer

Contoh:

Stack dan Queue

1. Stack

Stack atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep stack adalah LIFO yang merupakan singkatan dari Last In First Out, artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.[4] Berikut ilustrasi kerja sebuah stack:

      

Sebuah struktur data dari sebuah stack setidaknya harus mengandung dua buah variabel, misalnya variabel top yang akan berguna sebagai penanda bagian atas tumpukan dan array data dari yang akan menyimpan data-data yang dimasukkan ke dalam stack tersebut.

Operasi-operasi dasar dalam stack ada 2 yaitu operasi push dan pop:

• Operasi push, berfungsi untuk memasukkan sebuah nilai atau data ke dalam stack. Sebelum sebuah nilai atau data dimasukkan ke dalamstack, prosedur ini terlebih dahulu akan menaikkan posisi top satu level ke atas
• Operasi pop, berfungsi untuk mengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari stack, dengan cara menurunkan nilai top satu level ke bawah

2. Queue
pengertian queue dalam struktur data

Queue atau antrian merupakan struktur data linear dimana penambahan komponen dilakukan disatu ujung, sementara pengurangan dilakukan diujung lain. Kaidah utama dalam konsep queue adalah FIFO yang merupakan singkatan dari First In First Out, artinya adalah data yang pertama kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan.

Sebuah queue di dalam program komputer dideklarasikan sebagai sebuah tipe bentukan baru. Sebuah struktur data dari sebuah queue setidaknya harus mengandung dua tiga variabel, yakni variabel head yang akan berguna sebagai penanda bagian depan antrian, variabeltail yang akan berguna sebagai penanda bagian belakang antrian danarray dari yang akan menyimpan data-data yang dimasukkan ke dalam queue tersebut.

3. Perbedaan stack dan queue

• Stack merupakan tumpukan sedangkan queue merupakan antrian.
• Stack bersifat LIFO (Last in first out) yang artinya data yang terakhir masuk adalah data yang pertama keluar sedangkan queue bersifat FIFO ( First in first out) yaitu data yang pertama masuk akan pertama kali keluar.
• Perbedaan antara stack dan queue terdapat pada aturan penambahan dan penghapusan elemen. Pada stack, operasi penambahan dan penghapusan elemen dilakukan di satu ujung. Elemen yang terakhir kali dimasukkan akan berada paling dekat dengan ujung atau dianggap paling atas sehingga pada operasi penghapusan, elemen teratas akan dihapus paling awal (LIFO). Pada queue, operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan melalui salah satu ujung menempati posisi di belakang elemen-elemen yang sudah masuk sebelumnya atau menjadi elemen paling belakang. Sedangkan penghapusan elemen dilakukan di ujung yang berbeda, yaitu pada posisi elemen yang masuk paling awal atau elemen terdepan (FIFO).

4.Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

Jenis Binary Tree secara strukturnya ada 3 jenis yaitu:
1. Strict Binary Tree dimana harus punya 2 anak atau gak punya sama sekali
2. Completed Binary Ttee dimana sebelum anaknya 2 belum bisa nambah anak disebelah kanan, jika sudah 2 yang kanan boleh puyna anak.
3. Perfect Binary Tree dimana kiri kanan harus punya anak dengan jumlah sama dan seluruh segitiga seimbang.

5.Binary Search Tree

Binary Search Tree (BST) Adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree.

6.Hashing Table

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

2.      Operasi Pada Hash Tabel

insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

 find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

  remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

 getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu