Linked List

Download Persentasi disini

Dalam suatu linier list kita dapat melakukan operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang posisi.

Misalkan ada 1500 item yang merupakan elemen dari suatu linier list. Jika elemen ke-56 akan kita keluarkan, maka elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linier list tersebut. Tetapi elemen ke-57 akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke 57 dst.

Selanjutnya jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-42 s/d elemen ke-1500 akan berubah posisinya.

Untuk menyatakan keadaan diatas diperlukan suatu konsep yang berbeda dengan konsep sekuensial sebelumnya.

Linked list merupakan suatu cara non-sekuensial yang digunakan untuk merepresentasikan suatu data

DEFINISI

Linked List (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh pointer.

Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :

·         INFO          : berisi informasi tentang elmen data yang bersangkutan.

·         NEXT          : berisi alamat dari elemen (node) selanjutnya yang dituju.

Berikut ini sebuah contoh linked list yang terdiri atas 4 node :

Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. Adalah node terakhir.

Node-node dalan linked list tidak selalu harus digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini :

 

Catatan:

Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini yaitu :

1.       Diperlukan ruang tambahan untuk menyatakan/tempat field pointer.

2.       Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.

Sedangkan keuntungannya adalah :

1.       Jenis data yang berbeda dapat dilink.

2.       Operasi REMOVE atau INSERT hanya dapat dilakukan dengan mengubah pointernya saja.

OPERASI DASAR PADA LINKED LIST

Ada beberapa aturan yang didefinisikan pada operasi di dalam linked list, yaitu :

·         Jika P adalah suatu variabel pointer, maka nilainya adlah alamat atau lokasi dari variabel lain yang dituju.

·         Operasi yang didefinisikan pada suatu variabel pointer adalah :

1. Test apakah sama dengan NULL
2. Test untuk kesamaan dengan variabel pointer lain
3. Menetapkan sama dengan NULL
4. Menetapkan menuju ke node lain

Notasi yang didefinisikan sehubungan dengan operasi diatas adalah :

1.       NODE(P), artinya node yang ditunjuk oleh pointer P.

2.       INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P

3.       NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P

Sebagai contoh, perhatikan linked list dibawah ini :

NODE(P) = node yang ditunjuk oleh P yaitu node pertama.

INFO(P)   =  A

NEXT(P)  = node ke-dua

INFO(NEXT(NEXT(P))) = C

 

PENYAJIAN LINKED LIST DALAM MEMORI

Contoh : 

Keterangan :

·         START  = 9 INFO(9) = N, elemen pertama = N

·         LINK(9) = 3 INFO(3) = O, elemen kedua = O

·         LINK(3) = 6 INFO(6) = blank, elemen ketiga = blank

·         LINK(6) = 12           INFO(12) = E, elemen keempat = E

·         LINK(12) = 8           INFO(8) = X, elemen kelima = X

·         LINK(8) = 11           INFO(11) = I, elemen keenam = I

·         LINK(11) = 4           INFO(4) = T, elemen ketujuh = T

·         LINK(4) = 0 Null, list berakhir.

PENYISIPAN SIMPUL KE DALAM LINKED LIST

1.       Ilustrasi menyisipkan simpul di awal /depan linked list

Baru                          Awal                                                                           Akhir

       Baru                      Awal                                                                            Akhir

       Baru          Awal                                                                                        Akhir

2.       Ilustrasi menyisipkan simpul di belakang linked list

3.       Ilustrasi menyisipkan simpul di antara linked list

Awal          Awal                                                                                             Akhir

 

 

 

 

 

LOGIKA LINKED LIST PADA ARRAY

(a)              Jika tidak menggunakan logika linked list                                                        (pada umumnya dalam menginput data digunakan cara sequential)

(b)              Jika menggunakan logika linked list

Mendefinisikan Linked List dalam Pascal :

Type    nodeptr = ^ nodetype

            nametype = packed array [1..10] of char;

            nodetype = record

                                    info : nametype;

                                    next : nodeptr;

                               end;

Var      p : nodeptr;

            Node : nodetype;

Catatan :

P ^.Info           : Info dari node yang ditunjuk oleh pointer P

P ^.Next          : Next dari node yang ditunjuk oleh pointer P

P := nil            : pointer P berisi nilai Null

New(P)            : fungsi Getnode dalam Pascal

Dispose(P)       : Procedure Freenode dalam Pascal

Menghapus sebuah node dalam Pascal

procedure removaf(p:nodeptr, var out : nametype);

var q : nodeptr;

begin

            if (p^.Next = nil)

            then UNDERFLOW-CONDITION

            else      begin

                        q := p^.Next;

                        p^.Next := q^.Next;

                        out := q^.Info;

                        dispose(q);

                        end;

end;

Menyisipkan sebuah node dalam Pascal

procedure insereaf(p:nodeptr, in : nametype);

var q : nodeptr;

begin

            New(q);

            q^.Info := in;

            q^.Next := p^.Next;

            p^.Next := q;

end;

Penyisipan pada akhir dari suatu Linked List (Linked List Antrian) dalam Pascal

procedure inserend(first:nodeptr, in : nametype);

var newnode, q : nodeptr;

begin

            New(newnode);

            newnode^.Info := in;

            newnode^.Next := nil;

            q:= first;

            do while (q^.next <> nil)

                        q := q^.Next;

            q^.Next := newnode;

end;

Jika sebuah Linked List digunakan untuk menggambarkan suatu antrean, dalam hal ini pointer dapat langsung menunjuk ke rear/akhir dari antrean untuk menghindari pengulangan melalui semua nide untuk menemukan node terakhir.

procedure inserend(in : nametype, var rear:nodeptr,);

var newnode : nodeptr;

begin

            New(newnode);

            newnode^.Info := in;

            newnode^.Next := nil;

            rear^.Next := newnode;

            rear := newnode;

end;