Doubly Linked-List, Circular List, etc

Kuliah hari ini membahas varian-varian linked list yaitu terutama doubly linked-list. Doubly linked list adalah linked-list dengan dua pointer: satu menunjuk ke elemen berikutnya, dan satu menunjuk ke elemen sebelumnya. Masih ingat, dalam linked-list terdapat masalah penelusuran O(n) yang harus dilakukan saat merefer ke elemen list pada posisi sebelah kiri (sebelumnya) seperti pada masalah insert-before (penyisipan elemen baru sebelum elemen current). Hal ini dalam doubly linked-list tidak lagi terjadi karena adanya pointer kedua tersebut. Kecuali pencarian (searching) yang masih memerlukan operasi linear  O(n), semua operas manipulasi struktur pada doubly linked-list dapat dilakukan secara O(1). Namun, struktur ini membutuhkan lebih banyak memory untuk menyimpan dua memory address (pointer) tersebut dan dalam coding harus lebih berhati-hati karena penggunaan struktur data demikian cenderung menciptakan bug yang lebih sulit ditelusuri.

Circular linked-list adalah versi doubly linked-list dengan pointer next elemen terakhir menunjuk ke elemen pertama dan pointer prev elemen pertama menunjuk ke elemen terakhir. Secara lojik struktur itu membentuk lingkaran. Contoh aplikasi yang memerlukan struktur ini adalah beberapa perangkat lunak GUI (Grapahics User Interface) mendaftarkan komponen-komponen grafis (seperti icon, window, dll) dengan cara circular.

Sayang sekali, ada masalah koneksi di awal dan di akhir kuliah sehingga peserta kuliah melalui inherent sudah pasti tidak sepenuhnya bisa mengikuti.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s