double linked list struktur data

c. Array Dinamis

Hallo gan setia bocah ngoding, pada pelajaran kali ini kita akan belajar tentang double linked list yang dimana sebelumnya kita telah belajar tentang single linked list yaitu list yang memiliki 1 arah saja yaitu next. oke pada tulisan kali ini admin akan menulis tentang double linked list struktur data dimana dengan double linked list kita dapat menggunakan 2 arah penyambung yaitu next (ke arah selanjutnya ) dan prev (ke arah sebelumnya).

okey mungkin sekian dulu penjelasan singkatnya dari admin dan untuk lebih jelasnya admin tuliskan dalam tulisan ini SELAMAT MEMBACA..^_^

1. Double Linked List
pengertian double linked list
c. Array Dinamis

Double linked list adalah linked list biasa, hanya saja setiap elemen list -nya memuat dua macam pointer, yang satu menunjuk ke elemen sebelumnya dan yang lainya menunjuk ke elemen sesudahnya atau selanjutnya.^[2]

Gambar 2.1 ilustrasi inisialisasi double linked list

macam-macam double linked list
Ada dua macam double linked list, yaitu :

a. Double Linked List Cilcular

Circular artinya pointer next dan prev-nya menunjuk ke dirinya sendiri. Jadi, double linked list circular (DLLC) adalah linked list dengan menggunakan pointer, dimana setiap node memiliki 3field, yaitu 1 field pointer yang menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya (prev), serta 1 field yang berisi data dengan pointer next dan prev nya menunjuk ke dirinya sendiri secara circular. ^[3]

Gambar 2.2 Double linked list cilcular

Deklarasi node :

class Node{int data;
Node next;
Node prev;
}

b. Double Linked List Non Cilcular

Non circular artinya pointer preview dan next-nya akan menunjuk padanull. Jadi double linked list non circular (DLLNC) adalah double linked linked list yang memiliki 2 buah pointer yaitu pointer next dan prev. Pointer next menunjuk pada node setelahnya dan pointer preview menunjuk pada node sebelumnya. ^[3]

Gambar 2.3 Double linked list non cilcular

Deklarasi node :

class Node {int data;
Node next;
Node prev;
}

2. Sorting

Sorting adalah suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut aturan tertentu. Ada dua teknik pengurutan data, yaitu ascending (pengurutan naik) dandescending (pengurutan turun).^[9]

Jenis – jenis sorting:

a. Bubble Sort

Bubble sort merupakan cara pengurutan yang paling mudah diantara cara pengurutan data yang lainnya. Cara kerja dari bubble sort ini adalah dengan membandingkan elemen yang satu dengan elemen berikut. Berikut algoritma penyusunan bubble sort:

1. Tentukan data-data yang akan diurutkan dan ditampung di dalam array (jika menggunakan array).
2. Lakukan pemeriksaan kondisi:
3. Untuk pengurutan secara ascending, apabila data yang dibandingkan lebih besar dari data berikutnya, maka data akan diurutkan posisinya.
4. Untuk pengurutan secara descending, apabila data yang dibandingkan lebih kecil dari data berikutnya, maka posisi datanya ditukar.
5. Ulangi langkah kedua sebanyak jumlah data yang ada.
6. Ulangi langkah kedua sebagai perulangan bersarang dengan data yang dibandingkan merupakan data berikutnya, dan data yang dibandingkan adalah data terakhir.
7. Tampilkan data yang telah terurut.

b. Straight Selection Sort

Straight selection sort adalah metode atau cara pengurutan dengan membandingkan data yang satu dengan data-data berikutnya sampai dengan data terakhir. Jika ada ditemukan data yang lebih kecil, maka akan dicatat posisinya. Berikut algoritma penyusunan straight selection sort:

1. Tentukan data-data yang akan diurutkan.
2. Lakukan pemeriksaan kondisi:
3. Untuk pengurutan ascending, apabila ada ditemukan data yang lebih kecil dari data yang dibandingkan pada data-data setelahnya, maka posisi data yang lebih kecil tersebut dicatat dan ditukar posisinya.
4. Untuk pengurutan descending, apabila ada ditemukan data yang lebih besar dari data yang dibandingkan pada data-data setelahnya, maka posisi data yang lebih besar tersebut dicatat dan ditukar posisinya.
5. Ulangi langkah kedua sampai semua data telah dibandingkan.
6. Tampilkan data yang sudah diurutkan.

c. Insertion sort

Insertion sort merupakan suatu metode pengurutan yang membandingkan suatu elemen dengan elemen-elemen yang lain dan menyusunnya sedemikian rupa hingga elemen tersebut berada pada posisi yang seharusnya. Berikut algoritma penyusunan insertion sort:

1. Tentukan data-data yang aka diurutkan dan disimpan dalam array (jika menggunakan array).
2. Bandingkan data dengan data disebelah kirinya satu per satu.
3. Lakukan pemeriksaan kondisi:
4. Untuk pengurutan secara ascending, apabila data yang dibandingkan lebih kecil dari data sebelah kirinya, maka sisipkan data yang dibandingkan disebelah kiri data yang lebih besar.
5. Untuk pengurutan secara descending, apabila data yang dibandingkan lebih besar dari data sebelah kirinya, maka sisipkan data yang dibandingkan disebelah kiri data yang lebih kecil.
6. Ulangi langkah kedua hingga data yang dibandingkan dengan data yang paling kiri.
7. Ulangi langkah kedua sebagai perulangan bersarang hingga semua data telah dibandingkan.

3. operasi - operasi pada double linked list

a. Membangun Double Linked list

Membangun double linked list adalah memberikan nilai null terhadap variabel pointer awal dan variabel pointer akhir.^[3]

b. Penyisipan

1) Penyisipan di depan / di awal

Operasi ini berguna untuk menambahkan simpul baru di posisi pertama. ^[2] Ada 2 kondisi yang harus diperhatikan dalam penambahan data di awal yaitu :

1. Ketika linked list masing kosong, Jika kondisi linked list masih kosong, maka simpul baru akan menjadi simpul awal dan sekaligus simpul akhir dari double linked list
2. Ketika linked list tidak kosong, Jika kondisi linked list tidak kosong, maka simpul baru akan menjadi simpul awal.^[2]

2) Penyisipan di tengah

      Operasi penyisipan data di tengah linked list adalah suatu operasi menambahkan data di posisi tertentu di dalam linked list. Adapun algoritma untuk menambahkan node baru di tengah sebagai berikut:

1. Mendeklarasikan penunjuk bantu yang menunjuk ke node baru dan mendeklarasikan list yang pada kasus ini diasumsikan berisi dua buah node adalah node_before dan node_next. 
2. Mengarahkan penunjuk next node baru ke node_next dan penunjuk before node baru ke node_before.
3. Mengarahkan penunjuk node_before->next ke node baru.
4. Mengarahkan penunjuk node_next->before ke node baru.

3) Penyisipan di akhir

     Operasi ini berguna untuk menambahkan simpul baru di posisi akhir. ^[9] Adapun algoritma untuk menambahkan node baru di akhir adalah sebagai berikut:

1. Mendeklarasikan penunjuk bantu yang menunjuk ke node baru, penunjuk node akhir list dan mendeklarasikan list yang pada kasus ini diasumsikan berisi dua buah node .
2. Mengarahkan penunjuk next node akhir ke node baru dan mengisi informasi node setelahnya node baru menjadi null.
3. Mengarahkan penunjuk before node baru ke node akhir list.

c. Penghapusan

1) Penghapusan di awal

Operasi ini berguna untuk menghapus data pada posisi pertama. Adapun algoritma untuk menghapus node di awal adalah sebagai berikut:

1. Mendeklarasikan penunjuk bantu yang menunjuk ke node yang akan dihapus dan mendeklarasikan list yang pada kasus ini diasumsikan berisi tiga buah node.
2. Mengarahkan penunjuk node awal list ke node setelah node pertama yang dihapus.
3. Mengisi penunjuk next node “hapus” sama dengan null.

2) Penghapusan di tengah

Operasi ini berguna untuk menghapus data pada simpul tertentu. Adapun algoritma yang dilakukan untuk menghapus node ditengah adalah sebagai berikut:

1. Mendeklarasikan penunjuk bantu yang menunjuk ke node yang akan dihapus, penunjuk untuk node sebelum node yang akan dihapus.
2. Mengarahkan penunjuk next node_before ke node setelah node yang akan dihapus.
3. Mengarahkan penunjuk before node setelah node yang akan dihapus ke node_before.
4. Mengisi penunjuk next dan before node yang dihapus dengan null.

3) Penghapusan di akhir

Operasi ini berguna untuk menghapus data pada posisi terakhir.^[3] Adapun algoritma yang dilakukan untuk menghapus node di akhir adalah sebagai berikut:

1. Mendeklarasikan penunjuk bantu yang menunjuk ke node yang akan dihapus, penunjuk untuk node sebelum node yang akan dihapus.
2. Mengisi penunjuk next node_ before dengan null.
3. Mengisi penunjuk before node_“hapus” dengan null

Baca juga: contoh program double linked list java penjelasannya

algoritma & struktur dataMateri ITsemua

Share This :