Struktur Data – Linked List

Soal Pendahuluan

  1. Jelaskan perbedaan Linked List dengan Array dan sertai gambar permodelannya! Sebutkan keuntungan dan kerugiannya masin-masing struktur data tersebut!
  2. Berikan contoh kasus kapan sebuah Linked List lebih baik digunakan dan kapan sebuah Array lebih baik digunakan serta alasannya!
  3. Jelaskan dan pahami definisi Node, Single Linked List, Double Linked List, Single Circular Linked List dan Double Circular Linked List beserta gambar permodelannya!
  4. Jelaskan operasi dasar yang dimiliki oleh Linked List berikut :   (Data bertipe int dan dianggap unik setiap menambah node, key yang digunakan adalah nilai integer dari data itu sendiri)–          Node find(key)

    –          Node removeLast()

    –          void addFirst(data)

    –          Node remove(key)

    –          void addLast(data)

    –          boolean insertAfter(key,data)

    –          Node removeFirst()

    –          boolean insertBefore(key,data)
    dan sertai gambar permodelannya untuk setiap fungsi tersebut !

Pembahasan

Linked List

    Merupakan suatu struktur data pengembangan dari konsep ADT (Abstrak Data Type) yang bersifat dinamis. Linked List dapat dimanfaatkan secara effektif sesuai dengan keperluan. Linked List juga dapat benar – benar dihapus / dibersihkan dari memory.Linked List sebenarnya merupakan suatu typedata tersendiri. Di bahasa Java, Linked List bisa berupa suatu Class ataupun Record. Ciri – ciri utama dari Linked List adalah, dia mempunyai minimal dua elemen utama. Elemen – elemen itu adalah data dan pointer untuk menunjukkan ke list berikutnya.-

Array

    Array berbeda dengan Linked List. Array merupakan suatu struktur data yang bersifat statis. Array harus dialokasikan terlebih dahulu di dalam memory sebelum kita memakainya.

Perbedaan mendetail antara Array dan Linked List adalah sebagai berikut :

Linked List Array
–          Pengaksesan Dinamis-          Pengalokasian random pada alamat memory-          Dapat dibebaskan dari memory-          Tidak menggunakan konsep indexing-          Pengaksesan untuk searching /sorting lambat –          Pengaksesan Statis-          Pengalokasian berurut pada alamat memory-          Tidak dapat dibebaskan dari memory-          Menggunakan konsep indexing-          Pengaksesan untuk searching atau sorting cepat

5.

–    Linked List

linkedlist1

Kita akan lebih efektif jika kita menggunakan konsep Linked List jika kita memerlukan suatu pengaksesan pada struktur data yang lebih dinamis. Konsep yang lebih cocok menggunakan linked list adalah : Stack, Queue, Tree, dan Graph.

Hal ini dikarenakan oleh sifat dinamis dari Linked List. Kita tidak perlu untuk mengetahui berapa block memory yang akan kita akses. Jadi, jika kita butuh block baru pada memory, tinggal menyisipkan pada kanan atau kiri list yang telah ada.

–    Array

array

Kita dapat memanfaatkan secara efektif konsep array dengan mengenal metode indexing pada array. Array merupakan struktur data statis yang mempunyai index penomoran alamat variable array yang dimaksud. Jadi, secara umum, kita dapat mengaksesnya dengan lebih cepat.

Konsep – konsep yang dapat memanfaatkan konsep indexing untuk mempercepat pengaksesannya adalah Sorting dan Searching.

Hal ini dikarenakan oleh penomoran alamat variable pada memory yang telah diketahui terlebih dahulu. Jadi, semisal kita menginginkan mencari variable dengan indeks tengah, kita bisa langsung menujuk ke indeksnya.

6.    –    Singly Linked List :

single ll

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang berisi data.

Akhir linked list ditandai dengan node terakhir akan menunjuk ke null yang akan digunakan sebagai kondisi berhenti saat pembacaan linked list.

–    Double Linked List :

doouble ll

Linked list dengan menggunakan pointer, dimana setiap node memiliki 3 field, yaitu: 1 field pointer yang menunjuk ke pointer berikutnya, 1 field pointer yang menunjuk ke pointer sebelumnya dan field yang berisi data dari node tersebut. Pointer next dan prev-nya menunjuk ke null.

–    Single Circular Linked List :

single cir ll

Single Linked List yang pointer next-nya menunjuk ke dirinya sendiri, jika terdiri dari beberapa node maka pointer terakhirnya akan menunjuk ke pointer terdepannya.

–           Double Circular Linked List :

double cir ll

Double Linked List yang pointer next dan prev-nya menunjuk ke dirinya sendiri secara circular.

6.    a.  Node find(int key)

Suatu method java untuk mencari sebuah nilai pada linkedlist. Algoritma dari Operasi dasar adalah sebagai berikut :

Node find(int key){ if(now.data==key)return now;else{ now=now.next;

return (find(key));

}

}

b. Void addFirst(int data)

Method untuk membuat Node untuk pertama kali. Algoritma dari Operasi dasar adalah sebagai berikut :

void addFirst(Node input){   if (isEmpty()){head = input;tail = input;

}

else

{

input.next = head;

head = input;

}

}

c.    Void addFirst(int data)

Method untuk menambahkan list pada awal linked list. Algoritma dari Operasi dasar adalah sebagai berikut :

void addLast(Node input){     if (isEmpty()){head = input;tail = input;

}

else

{

tail.next = input;

tail = input;

}

}

d.    Void romoveFirst()

Method untuk menghapus list pertama. Algoritma dari Operasi dasar adalah sebagai berikut :

void removeFirst(){   Node temp = head;if (!isEmpty()){ if (head == tail)head = tail = null;

else

{

temp = temp.next;

head = temp;

temp = null;

}

}

else

System.out.println(“Data is empty!”);

}

e.    Void romoveLast()

Method untuk menghapus list terakhir. Algoritma dari Operasi dasar adalah sebagai berikut :

void removeLast(){Node temp = head;if (!isEmpty()){if (tail == head){head = tail = null;

}

else {

while (temp.next != tail){

temp = temp.next;

}

temp.next = null;

tail = temp;

temp = null;

}

}

else System.out.println(“Data is empty!”);

}

e.    Void romove(int key)

Method untuk menghapus list yang bersesuaian dengan kata kunci. Algoritma dari Operasi dasar adalah sebagai berikut :

void remove(int key){ Node temp = head;if (!isEmpty()){while (temp != null){

if (temp.next.data == key){

temp.next = temp.next.next;

break;}

else if ((temp.data == key)&&(temp == head)){

this.removeFirst();

break;}

temp = temp.next;}

}

else

System.out.println(“Data is empty!”);

}

f.     void insertAfter(int key,int data)

Method untuk menyisipkan list yang serada setelah list yang dimaksud oleh parameter kata kunci. Algoritma dari Operasi dasar adalah sebagai berikut :

void insertAfter(int key,Node input){ Node temp = head;do{if (temp.data == key){input.next = temp.next;

temp.next = input;

System.out.println(“Insert data is succeed.”);

break;

}

temp = temp.next;

}while (temp!=null);

}

g.    void insertBefore(int key,int data)

Method untuk menyisipkan list yang serada setelah list yang dimaksud oleh parameter kata kunci. Algoritma dari Operasi dasar adalah sebagai berikut :

void insertBefore(int key,Node input){ Node temp = head;while (temp != null){ if ((temp.data == key)&&(temp == head)){ this.addFirst(input);

System.out.println(“Insert data is succeed.”);

break;

}

else if (temp.next.data == key)

{ input.next = temp.next;

temp.next = input;

System.out.println(“Insert data is succeed.”);

break;

}

temp = temp.next;

}

}

15 thoughts on “Struktur Data – Linked List

  1. … sebuah pengetahuan yang bermanfaat bagi pembelajaran….
    Nice…

    Thanks

  2. mas dewa. .. ada ebooknya strukdat gag??

  3. pak…. ajarin donk

  4. dewa,,,,,,,ajarin gue donk,gue koq g pinter-pinter struktur data ci,,,,,,,,

  5. nice info boz, mungkin ini bisa jadi tambahan : http://mohsodq1608.wordpress.com/2010/07/03/perbedaan-array-dengan-linked-list

    silahkan mampir boz, makasih

  6. maksih bgt smoga bs jd teman baik

  7. makach banyak tas informasinya.

  8. nice post kak dewa,,,
    thanks for sharing knowledge,,,

    keep contributing for others yaaaaaaaa

  9. asik infonya (y), terus berkarya ya

  10. tau ngak menentukan jumlah kata pada kalimat menggunakan operasi list ??? kasih tau dong……..

  11. Thanks Buat Postingan Yang Bermanfaat,,,
    Visit My Blog : lautanilmumahasiswasttpln.blogspot.com
    :-) :-) :-)

  12. thank’s agan . bermamfaat sekali . visit : mefra01.wordpress.com

  13. Terima kasih banyak buat ilmunya

Tinggalkan Jejak

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