Nama : IKetut Suardana
Nim : 060010165
Kls : F081
Linked list (list bertaut) adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. 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.
Secara umum linked list tersusun atas sejumlah bagian-bagian data yang lebih kecil yang terhubung (biasanya melalui pointer). Linked list dapat divisualisasikan seperti kereta, bagian kepala linked list adalah mesin kereta, data yang disimpan adalah gerbong, dan pengait antar gerbong adalah pointer.
Jenis-Jenis Linked List
- Singly linked list
- Double linked list
- Circular Linked List
-------- -------- --------
Mesin Data Data
-------- -------- --------
(kepala) ---> Pointer ---> Pointer --
-------- -------- --------
Cotoh gambar linked list.
- Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis dan terbatas.
- Linked List sering disebut juga Senarai Berantai
- Linked List saling terhubung dengan bantuan variabel pointer
- Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field.
Single Linked List
Merupakan struktur data dinamis yang terdiri dari kumpulan komponen yang disusun secara berurutan dengan menggunakan bantuan pointer. Komponen-komponen tersebut disebut sebagai simpul (node).
Tiap simpul dapat dibagi menjadi dua bagian yaitu medan informasi/data yang akan diolah dan medan penyambung (link field) yang berisi alamat simpul berikutnya.
Contoh deklarasi
Type
Point = ^RecPoint ;
RecPoint = Record
Nama : string[20] ;
Next : Point ;
End ;
Var
Head, Tail, Now : Point ;
Suatu list harus mempunyai ujung awal (head) dan ujung akhir (tail). Untuk menandai akhir dari suatu list maka diberikan kata cadang NIL pada pointer node terakhir, yang berarti pointer tidak menunjuk kemanapun.
Metode Pembuatan Single Linked List ada dua yaitu secara LIFO (Last In First Out) dan FIFO (First In First Out).
Dengan metode LIFO maka maka node yang pertama dimasukkan akan menjadi node yang terakhir dikeluarkan, atau dengan kata lain terjadi penambahan node diawal list. Adapun prosedur yang digunakan adalah sebagai berikut:
Procedure INSERT(elemen:TipeData) ;
Var Now : Point ;
Begin
New(Now) ;
Now^.Isi := elemen ;
If Head = Nil then
Now^.Next := Nil ;
Else
Now^.Next := Head ;
Head := Now ;
End ;
Double Linked list
Double Linked List adalah suatu linked list yang mempunyai 2 penunjuk yaitu penunjuk ke data sebelumnya dan berikutnya.
Beberapa operasi yang dapat dilakukan dalam double linked list adalah :
1. Pendeklarasian Struktur dan Variabel Double Linked List
Jika dilihat 1 elemen listnya, maka secara umum struktur dari elemen listnya
2. View data
Untuk view data, langkah yang dilakukan adalah dengan menelusuri semua elemen list sampai elemen terakhir. Setelah melakukan penelurusan posisi awal dan akhir elemen tidak boleh berubah sehingga untuk melakukan penelusuran dibutuhkan sebuah variabel bantu.
Kelebihan dari view data pada linked list adalah kita dapat menampilkan data dari data terakhir dengan lebih mudah.
Implementasi program view data dari awal sampai data terakhir yang menggunakan double linked list dengan bahasa C adalah :
void viewdata(pdata awal)
{
pdata p;
p=awal;
printf("Data : ");
while (p!=NULL)
{
printf("%5d",p->info);
p=p->kanan;
}
printf("\n");
}
Sedangkan jika view data dari data terakhir sampai data pertama adalah :
void viewdatareverse(pdata akhir)
{
pdata p;
p=akhir;
printf("Data Terbalik: ");
while (p!=NULL)
{
printf("%5d",p->info);
p=p->kiri;
}
printf("\n");
}
Cara pemanggilannya adalah :
viewdata(awal); // menampilkan data dari data
viewdata(akhir); // menampilkan data dari data terakhir
3. Tambah di awal
Operasi ini berguna untuk menambahkan elemen baru di posisi pertama. Langkah pertama untuk penambahan data adalah pembuatan elemen baru dan pengisian nilai infonya. Pointer yang menunjuk ke data tersebut dipanggil dengan nama baru. Kondisi di setelah ada pembuatan elemen baru tersebut adalah :
Perintah pembuatan elemen double linked list dalam bahasa C adalah :
pdata baru;
baru=(pdata)malloc(sizeof(tdata));
baru->kiri=NULL;
baru->kanan=NULL;
baru->info=data; // data berasal dari parameter fungsi
Ada 2 kondisi yang harus diperhatikan dalam penambahan data di awal yaitu :
a. Ketika linked list masih kosong
Kalau kondisi linked list masih kosong, maka elemen baru akan menjadi awal dan akhir linked list.
Perhatikan gambar di bawah ini :
Kondisi sebelum disisipkan
Kondisi setelah operasi penambahan
Operasi penambahan awal ketika linked list masih kosong adalah dengan mengisikan alamat pointer baru ke pointer awal dan pointer akhir. Lihat gambar di bawah ini.
4. Tambah di akhir
Operasi ini berguna untuk menambahkan elemen baru di posisi akhir. Langkah pertama untuk penambahan data adalah pembuatan elemen baru dan pengisian nilai infonya.
5. Sisip di tengah
Operasi penyisipan data di tengah linked list adalah suatu operasi menambah data di posisi tertentu di dalam linked list. Contohnya adalah jika ingin menyisipkan data di posisi ke-3 atau ke-4.
Untuk proses tersebut ada 2 hal yang harus diperhatikan yaitu :
a. Kondisi linked list masih kosong atau posisi penyisipan kurang dari atau sama dengan 1
Jika kondisi ini terjadi, maka langkah yang dilakukan adalah sangat mudah yaitu dengan memanggil proses penambahan data awal atau akhir. (untuk lebih jelas lihat penambahan data awal atau akhir ketika kondisi linked list masih kosong).
b. Kondisi linked list sudah mempunyai data
Langkah untuk penyisipan data ketika linked list sudah mempunyai data adalah :
Cari posisi pointer pada data ke-posisi sisip.
6. Hapus data awal
Operasi ini berguna untuk menghapus data pada posisi pertama. Ada 3 keadaan yang mungkin terjadi ketika akan melakukan proses hapus yaitu :
a. Kondisi linked list masih kosong
Jika kondisi ini terjadi, maka proses penghapusan data tidak bisa dilakukan karena linked list masih kosong.
b. Kondisi linked list hanya memiliki 1 data
Langkah yang perlu dilakukan ketika ingin melakukan proses penghapusan linked list yang memiliki hanya 1 data adalah dengan langsung menghapus data dari memori dan kemudian pointer awal dan akhir di-NULL-kan.
c. Kondisi linked list memiliki data lebih dari 1 buah
Untuk operasi penghapusan data di posisi pertama pada double linked list yang mempunyai data lebih dari 1 buah adalah :
Simpan pointer yang akan dihapus (awal) ke suatu pointer lain yang diberi nama pointer Bantu
- Pindahkan pointer awal ke data berikutnya (bantukanan atau awalkanan).
- Field kiri dari awal yang baru (awalkiri) di-NULL-kan.
- Langkah terakhir adalah hapus elemen yang ditunjuk pointer bantu.
7. Hapus data terakhir
Operasi ini berguna untuk menghapus data pada posisi terakhir. Ada 3 keadaan yang mungkin terjadi ketika akan melakukan proses hapus yaitu :
a. Kondisi linked list masih kosong
Jika kondisi ini terjadi, maka proses penghapusan data tidak bisa dilakukan karena linked list masih kosong.
b. Kondisi linked list hanya memiliki 1 data
Langkah yang perlu dilakukan ketika ingin melakukan proses penghapusan linked list yang memiliki hanya 1 data adalah dengan langsung menghapus data dari memori dan kemudian pointer awal dan akhir di-NULL-kan.
8. Hapus data di tengah
Untuk melakukan proses penghapusan di tengah linked list, ada 3 kondisi yang perlu diperhatikan yaitu :
a. Kondisi ketika linked list masih kosong atau ketika posisi hapus lebih kecil dari 1.
Ketika kondisi ini terjadi, maka proses penghapusan tidak bisa dilakukan karena data masih kosong atau karena posisi hapus diluar jangkauan linked list (posisi kurang dari 1).
b. Kondisi ketika posisi hapus sama dengan 1 (hapus data pertama)
Ketika kondisi ini terjadi, maka proses yang dilakukan adalah proses penghapusan di posisi awal (hapusawal).
