Linked List

Array merupakan variabel yang bersifat statis, karena ruang memori yang dipakai tidak dapat dihapus bila array tersebut sudah tidak  digunakan lagi saat program dijalankan.

Maka digunakan satu variabel pointer untuk menyimpan banyak data dengan metode yang disebut Linked List

Linked list  adalah sekumpulan elemen bertipe sama yang mempunyai keterurutan tertentu, yang setiap elemennya terdiri dari dua bagian

                    Kepala (first)

 NULL

                                                                                                             Ekor/tail

                                                                                                 

                                                             Node/simpul             Pointer

Bentuk Umum :

typedef struct elmtlist

                {

                                infotype info;

                                address next;

                } elmtlist;

infotype >> sebuah tipe terdefinisi yang menyimpan informasi sebuah elemen list

next >>  address dari elemen berikutnya

Tipe-tipe List :

1. List Kosong

List kosong hanya terdiri dari sebuah penunjuk elemen yang berisi NULL (kosong). Tidak memiliki satu buah elemen pun, sehingga hanya berupa penunjuk awal elemen yang berisi NULL (kosong)

                                                                  Kepala (first)

NULL

 2. Single Linked List

Sebuah data yang terletak pada sebuah lokasi memori area

                    00001000                   00001004                 00001008

                Field bertipe data            Field bertipe pointer

                tertentu untuk                  untuk menunjuk ke

                menampung sebuah        node berikutnya

                data/informasi

Single Linked List  adalah sebuah list yang elemennya hanya menyimpan informasi elemen setelahnya (next), sehingga pengaksesan list hanya dapat dilakukan secara maju.

Jenis-jenis Single List (List Tunggal) :

2.1 List Tunggal dengan kepala dan ekor

Kepala (first)                                                                                             ekor (tail)

List ini memiliki dua buah penunjuk elemen, yaitu penunjuk elemen pertama (first) dan penunjuk elemen akhir (tail) sehingga yang dapat diakses adalah elemen awal dan elemen akhir

2.2 List Tunggal dengan kepala

Kepala (First)

Pada awal pengaksesan hanya dapat diakses elemen pertamanya saja, karena penunjuk hanya berupa penunjuk elemen awal (first)

2.3 List Tunggal berputar

Kepala (First)

Pada list tunggal berputar, elemen terakhir ditandai dengan elemen setelahnya sama dengan elemen pertama sehingga penelusuran list akan berhenti jika penunjuk bantu telah sampai pada elemen setelahnya sama dengan elemen yang ditunjuk oleh penunjuk elemen awal.

3. Double Linked List (List Ganda)

List ganda adalah sebuah list yang elemennya menyimpan informasi elemen sebelum dan sesudahnya.

                Jenis-jenis Double Linked List :

                1. List Ganda dengan kepala dan Ekor

                2. List Ganda dengan kepala

                3. List ganda berputar

3.1 List ganda dengan kepala dan ekor

 Memiliki dua penunjuk awal yang dapat diakses pada awal penelusuran list yaitu penunjuk elemen awal (first) dan penunjuk elemen akhir (tail).

3.2  List Ganda dengan kepala

                                Hanya memiliki sebuah penunjuk elemen yaitu penunjuk pada elemen awal list (first)

3.3 List Ganda Berputar (Circular Double Linked List)

                Simpul terakhirnya menunjuk ke simpul awalnya dan simpul awalnya menunjuk ke simpul akhir sehingga membentuk sebuah lingkaran.

Operasi yang ada pada List :

1. Insert à menambah sebuah simpul baru ke dalam list
2. IsEmpty à menentukan apakah linked list kosong atau tidak
3. Find First à mencari elemen pertama dari linked list
4. Find Next à mencari elemen sesudah elemen yang ditunjuk now.
5. Retrieve à mengambil elemen yang ditunjuk oleh now, lalu dikembalikan oleh fungsi.
6. Update à mengubah elemen yang ditunjuk now dengan isi sesuatu
7. Delete now à menghapus elemen yang ditunjuk oleh now
8. Delete head à menghapus elemen yang ditunjuk head
9. Clear à menghapus linked list yang sudah ada