Pertemuan 2 : Introduction and Implementation Linked List I - 2101632225 - Hendy
Introduction to Linked List
Struktur data Linked List sering digunakan untuk mengimplementasikan struktur data lainnya. Sebuah Linked List adalah urutan node dimana masing-masing node menyimpan data sendiri dan sebuah pointer (alamat) ke lokasi node berikutnya. Satu node terhubung pada node yang lain dan membentuk seperti rantai terikat.
Item terakhir dalam list mempunyai pointer atau link ke NULL, yang menunjukkan akhir rantai. Linked List hampir sama dengan Array, itu tidak terbatas pada sejumlah elemen yang dinyatakan. Selain itu, tidak seperti Array yang menyimpan data secara berkelanjutan dalam memori atau disk, Linked List dapat dengan mudah insert atau remove elemen tanpa realokasi secara keseluruhan struktur karena item pada data tidak perlu disimpan secara bersamaan.
Pada bagian paling depan Linked List dinamakan Head yang berarti kepala yang merupakan pointer yang menunjukkan kepada elemen pertama dan pada bagian terakhir disebut Tail yang berarti ekor yang merupakan pointer yang menunjuk pada elemen terakhir pada Linked List.
Implementation Linked List I
Berikut berbagai macam Linked List :
- Single Linked List
- Polynomial Representation
- Circular Single Linked List
- Doubly Linked List
- Circular Doubly Linked List
- Header Linked List
Single Linked List
Single Linked List adalah sekumpulan dari node yang saling terhubung membentuk rantai dengan node lain melalui sebuah pointer yaitu hanya menggunakan sebuah pointer dan biasanya mempunyai tipe data yang sama semua.
 |
| Single Linked List |
Single Linked List : Insert (Push)
node -> value = 31; Berarti pada node kita setting nilai 31
node -> next = head; Berarti setelah node kita tunjuk sebagai head
Ada 2 jenis insert yaitu pushDepan dan pushBelakang
1. pushDepan = data yang paling baru dimasukkan akan berada di depan data lainnya
2. pushBelakang = data yang paling baru akan berada dibelakang data lainnya
pushDepan : 5,3,7,9 maka hasilnya adalah : 9 -> 7 -> 3 -> 5 -> NULL
pushBelakang : 5,3,7,9 maka hasilnya adalah : 5 -> 3 -> 7 -> 9 -> NULL
Single Linked List : Delete (Pop)
struct tnode *curr = head; Berarti pada curr kita jadikan head
head = head -> next; Berarti head kita pindahkan ke setelahnya dan ditunjuk sebagai head
free(curr); Berarti membuang curr sehingga setelahnya menjadi head
Circular Single Linked List
Pada Circular Single Linked List yaitu pada akhir node mempunyai pointer yang akan menunjuk pada node pertama yaitu selalu akan kembali ke head dan tidak ada nilai NULL pada list.
Doubly Linked List
Doubly Linked List yaitu Linked List data yang mempunyai 2 link yaitu untuk next dan previous dan juga pada next dan previous mempunyai NULL yaitu pada setiap ujung kiri dan kanan. Pada Doubly Linked List juga mempunyai operasi insert dan delete sama seperti Single Linked List hanya saja mempunyai algoritma yang berbeda.
Circular Doubly Linked List
Hampir sama seperti Circular Single Linked List, tetapi memiliki total pointer sebanyak 2 pada setiap node yaitu pada head bisa saling berhubungan dengan tail dan juga masing-masing node bisa saling berhubungan timbal balik dengan node yang bersebelahan.
Polynomial Representation
Sebagai contoh 3x^2 + 5x + 7 dapat dituliskan seperti dibawah ini :
Jadi berurutan dari kiri ke kanan yaitu nilai eksponen yang pertama 3 dan kemudian disampingnya merupakan koefisien dari pangkatnya x dan kemudian pada sampingnya merupakan pointer yang menunjuk node selanjutnya hingga pada akhirnya berakhir NULL.
Header Linked List
Seperti pada contoh diatas, Header Linked List berarti mengandung header node pada awal list. L merupakan START yaitu merupakan awal perjalanan dan mengandung atau menunjuk pada alamat dari header node bukan menunjuk pada node pertama.
Terima kasih sudah membaca post ini yang merupakan rangkuman pembelajaran saya pada pertemuan kedua belajar mengenai Data Structure. Semoga informasi ini bermanfaat bagi kalian semua. Terima Kasih.
Komentar
Posting Komentar