Monday 28 March 2011

Diposkan oleh sandy

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
Single Linked List

Linked list dapat dianalogikan sebagai rantai yang terdiri dari beberapa node yang saling terkait. Dengan memegang node terdepan, maka node-node yang saling terkait lainnya dapat kita telesuri.

Dengan hanya mencatat atau memegang alamat dari alokasi data bertipe struct root pada sebuah variabel LL maka keberadaan node-node dalam linked list tersebut dapat diketahui. Bila data-data dalam node berupa bilangan bulat, maka struct yang diperlukan untuk membentuk linked list adalah sebagai berikut:

typedef struct node * NodePtr;
typedef struct node {
int data;
NodePtr next;
}Node;

typedef struct root {
NodePtr head;
unsigned size;
}Root;
Root LL;

Penambahan Node Linked List

Bila setiap penambahan simpul pada linked list dilakukan pada bagian depan (paling dekat dengan head) maka kompleksitas yang diperlukan untuk menambah node baru dalam linked list konstan atau O(1). Penambahan sebuah node dengan nilai 3 pada linked list di atas dapat divisualisasikan sebagai berikut:

Penelusuran Node Linked List

Kompleksitas penelusuran (pencarian) node dalam linked list adalah linier atau O(n). Hal ini disebabkan karena node-node dalam linked list disusun secara acak (tidak berurut). Seandainya pun simpul-simpul dalam linked list disusun secara berurut, metode pencarian biner (binary search) tetap tidak dapat dipergunakan. Ada 2 alasan mengapa pencarian biner tidak dapat digunakan:

1. Linked list tidak memiliki indeks seperti array, sehingga akses langsung ke node tertentu tidak dapat dilakukan. Untuk menuju ke node tertentu, proses pemeriksaan tetap dimulai dari node head (node terdepan). Oleh karena itu proses pencarian selalu berjalan secara linier.

2. Tidak dapat membagi linked list menjadi 2 bagian yang sama besar seperti saat membagi array menjadi 2 bagian bila metode pencarian biner diaplikasikan pada array terurut.


Penghapusan Node Linked List

Sebelum proses penghapusan dilakukan, pencarian node yang ingin dihapus harus terlebih dahulu dilakukan. Bila node yang ingin dihapus ditemukan, suatu hal yang selalu harus diperhatikan adalah bagaimana mengeluarkan node tersebut dari linked list dan kemudian menyambung kembali linked list kembali. Kompleksitas menghapus sebuah node dalam linked list adalah O(n)

Sumber : http://id.wikipedia.org/wiki/Linked_list




edit post

0 komentar:

Post a Comment