link list
DESCRIPTION
Link List. FARID WAJDI YUSUF. Sejarah. Dikembangkan tahun 1955-1956 oleh Allen Newell, Cliff Shaw dan Herbert Simon di RAND Corporation sebagai struktur data utama untuk bahasa Information Processing Language (IPL). IPL dibuat untuk mengembangkan program artificial intelligence. - PowerPoint PPT PresentationTRANSCRIPT
Link ListFARID WAJDI YUSUF
Sejarah
Dikembangkan tahun 1955-1956 oleh Allen Newell, Cliff Shaw dan Herbert Simon di RAND Corporation sebagai struktur data utama untuk bahasa Information Processing Language (IPL).
IPL dibuat untuk mengembangkan program artificial intelligence
Link List
List merupakan sebuah pemikiran/konsep struktur data yang sangat dasar pada pemrograman agar lebih fleksibel.
Setiap elemen akan ditambahkan saat dibutuhkan, tidak dialokasikan dengan tempat tertentu dari awal.
Ilustrasi :
Secara logika, kepala atau first adalah pengait atau penunjuk awal elemen pertama dari sebuah list.
null
kepala
Link List
Merupakan sekumpulan elemen list yang bertipe sama.
Elemen list mempunyai keterurutan tertentu, nilai satu elemen boleh muncul lebih dari satu kali.
Setiap elemen mempunyai 2 bagian:o Informasi elemeno Alamat suksesornya
Linked List adalah salah satu bentuk struktur data, berisi kumpulan data (node) yang tersusun secara sekuensial, saling sambung-menyambung dan dinamis.
Linked List saling terhubung dengan bantuan variabel pointer.
Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis.
Link List
Setiap node terdiri atas dua bagian. Bagian pertama berisi informasi data tersebut,
Bagian kedua merupakan field, link, atau nextpointer. Link inilah yang menghubungkan satu elemen data ke elemen data lainnya, sehingga urutan elemen data tersebut membentuk suatu linear list.
Field link ini berisi alamat dari simpul berikutnya dalam list.
Field link bernilai 0 bila link tersebut tidak menuding ke data (simpul) lainnya.
Penuding ini disebut penuding nol.
Link List
Ilustrasi Link List, sebagai berikut :
NEXT
ELEMENNODE
A
B
C
Link List
Misalnya kita ingin membuat sebuah elemen data nilai mahasiswa yang terdiri dari NRP, nama, dan nilai, maka representasinya adalah sebagai berikut:
021NIM
Serdi
Nama A
Nilai next
Penunjuk ke elemen berikutnya
Link List
Bila elemen seperti diatas dibuat dalam bahasa algoritma, seperti berikut:
type nilaiMatKul : < NRP : string, nama : string, nilai : string,>
Elemen ditambah dengan pengait/penunjuk:type elemen : < elmt : nilaiMatKul, next : elemen>
Link List
Deklarasi listnya sebagai berikut:type list : < first : elemen>
Link List
Penunjuk elemen di awal ini (first) digunakan untuk memegang elemen awal sebuah list agar dapat diakses satu per satu sampai elemen terakhir list.
Sebuah struktur data yang dianggap sebagai list memiliki aturan pengaksesan.
Pengaksesan dilakukan dari penunjuk elemen pertama (first) kemudian berjalan maju ke elemen kedua, ketiga dan seterusnya sampai elemen terakhir.
Keuntungan Link List
Penggunaan memori yang dinamik.o Kita dapat mengatur penggunaan memori
sehingga bisa lebih hemat.
Kesederhaan pada proses insert dan delete elemen.
Alamat elemen pertama dari suatu list, dapat diacu oleh First(L).
Nilai yang dibawanya dapat diacu dengan info(P)
Jenis List
Single Linked List
dapat juga ditulis NULL
Double Linked List
10 15 20
head
10 15 20
headprev next
PENGERTIAN• Single : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL
• Linked List : artinya node-node tersebut saling terhubung satu sama lain.
10
data pointer
10 15 20
NULL
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.
Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
15 20 10
data pointer NULL
JENIS SINGLE LINK LISTSingle Link List dengan Head
10 15 20
head
10 15 20
head tail
Single Link List dengan Head dan Tail
BEBERAPA OPERASI PADA LIST
MEMBUAT ELEMEN LINKED LISTMembuat suatu elemen linked list berarti memesan tempat di memori untuk menyimpan sebuah list.
Menghapus elemen list berarti menghilangkan atau menghancurkan alokasi memori sebuah list yang telah ada di memori.
Fungsi: agar data yang tidak diperlukan benar-benar terhapus di memori sehingga penggunaan memori dapat optimal karena data-data yang tidak diperlukan dihilangkan.
PENAMBAHAN ELEMEN DI POSISI AWAL
Penambahan elemen di posisi awal adalah menambahkan data baru pada posisi awal, sehingga data baru tersebut akan menjadi awal.
Ada 2 hal yang harus diperhatikan, yaitu : kondisi linked list sedang kosong, atau kondisi linked list sudah mempunyai
elemen.
Kondisi Linked List Sedang KosongKetika linked list masih
kosong, maka variable awal dan akhir akan diisi dengan variable baru.
NULL
head
1. List masih kosong (head=NULL)
2. Masukkan data baru, misal 10
10
head
Kondisi Linked List Sudah Mempunyai Elemen.
Proses penambahannya adalah dengan mengisikan field next milik elemen baru dengan posisi awal linked list, kemudian posisi awal berubah ke posisi baru.
15 10
headbaru
15 10
head
Masukkan data baru dari depan, misal 15
10
head
15
baru
Penambahan Elemen Di Posisi Terakhir Penambahan di posisi akhir adalah proses
penambahan data baru dimana data baru disimpan di posisi terakhir.
Setelah proses penambahan selesai, maka variable akhir akan menunjuk ke data baru tersebut.
Ada 2 hal yang harus diperhatikan yaitu : Kondisi penambahan akhir pada linked list yang
masih kosong dan Kondisi penambahan akhir pada linked list yang
sudah mempunyai elemen.
10 15
bantuhead
10 15
head
baru
Masukkan data baru dari belakang, misal 15
10
head
15
baru
15 21
bantu
10
15
head baru
Masukkan data baru dari belakang, misal 21
21
baru
10
head
10 15
head
21
MENAMPILKAN SINGLE LINKED LIST DENGAN HEAD
Penelusuran ini dilakukan dengan menggunakan suatu pointer bantu, karena pada prinsipnya pointer head yang menjadi tanda awal list tidak boleh berubah/berganti posisi.
Penelusuran dilakukan terus sampai node terakhir ditemukan menunjuk ke nilai NULL. Jika tidak NULL, maka node bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan menggunakan field next sehingga dapat saling berkait.
Jika head masih NULL berarti data masih kosong!.
Contoh:Langkah-langkah penelusuran adalah : Isi variable p dengan awal. � Selama p tidak NULL, maka tampilkan �
info yang ada di elemen yang ditunjuk variable p, kemudian p dipindahkan ke elemen berikutnya.
PENGHAPUSAN DATA AWAL Penghapusan data di awal adalah proses
menghapus elemen pertama (awal), sehingga variable awal akan berpindah ke elemen data berikutnya.
Ada 3 kondisi yang perlu diperhatikan yaitu: kondisi linked list masih kosong kondisi linked list hanya memiliki 1 data,
dan kondisi linked list yang memiliki data lebih
dari 1 elemen.
Kondisi linked list masih kosong Pada kondisi ini proses penghapusan
tidak bisa dilakukan. Kondisi linked list hanya memiliki 1
data Langkah yang dilakukan adalah
menghapus data yang ada di posisi awal kemudian akhir dan awal di-NULL-kan.
Kondisi linked list memiliki data lebih dari 1 data: Alamat data awal diisikan ke suatu
variabel pembantu (phapus). Setelah itu pindahkan awal ke data
berikutnya. Setelah itu hapus/hancurkan data
di posisi phapus.
10 15
head
21
15
head
21
Proses penghapusan data 10 dari depan
Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk oleh pointer.
Sebelum data terdepan dihapus, head harus ditunjukkan ke node sesudahnya terlebih dahulu agar list tidak putus, sehingga node setelah head lama akan menjadi head baru (data terdepan yang baru).
PENGHAPUSAN DATA AKHIRPenghapusan data akhir adalah proses
menghilangkan/menghapus data yang ada di posisi terakhir.
Ada 3 kondisi yang harus diperhatikan ketika akan melakukan proses penghapusan data akhir yaitu:Kondisi linked list masih kosong, Kondisi linked list hanya berisi 1 data,
dan Kondisi linked list berisi data lebih dari 1
buah.
10 15
head
21
Proses menghapus data 34 dari belakang
34
10 15
head
21 34bantu hapus
10 15
head
21bantu
bantu
MENGHAPUS DATA DARI BELAKANG Membutuhkan pointer bantu dan hapus. Pointer hapus digunakan untuk menunjuk node
yang akan dihapus, dan pointer bantu digunakan untuk menunjuk node sebelum node yang dihapus yang kemudian selanjutnya akan menjadi node terakhir.
Pointer bantu akan digunakan untuk menunjuk ke nilai NULL.
Pointer bantu akan selalu bergerak sampai sebelum node yang akan dihapus, baru kemudian pointer hapus diletakkan setelah pointer bantu. Setelah itu pointer hapus akan dihapus, pointe bantu akan menunjuk ke NULL.
• Dibutuhkan dua buah variabel pointer: head dan tail
• Head akan selalu menunjuk pada node pertama, sedangkan tail akan selalu menunjuk pada node terakhir.
10 15 20
head tail
IMPLEMENTASI LIST MENGGUNAKAN JAVA
Java tidak memiliki pointer namun memiliki reference.
Reference adalah penunjuk ke objek (fungsinya sama seperti pointer)
CONTOH:Contoh penggunaan reference:
Data a = new Data();Data b = a; /* b menunjuk ke a*/
Jika b di ubah, maka a juga akan berubah
ELEMEN LIST Pada java, elemen list didefinisikan
dengan kelas. Jadi elemen list adalah kelas.
Suatu kelas boleh merefer dirinya sendiri. Contoh:
class ListElement {
String info; ListElement next;}