Linked List

Singly Linked List :

~ 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.

Singly Linked List Non Circular

Doubly Linked List :

~ 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.

Doubly Linked List

Implementasi Class Single Linked List beserta Methodnya (pada java) :


class Node{
 int data;
  Node next;
}

class LinkedList{
  Node head; //posisi awal dari linked list
  Node tail; //posisi akhir dari linked list
  /**
   * Fungsi untuk mengecek apakah linked list masih kosong
   */
  boolean isEmpty(){
    return (head==null);
  }

  void addFirst(Node input){
    if (isEmpty()){ //Jika linked list masih kosong,
      head = input; //maka head dan tail sama dengan node input
      tail = input;
    }
    else {
      input.next = head; //Jika linked list sudah berisi,
      head = input; //maka input akan di depan dan menjadi head
    }
  }

 void addLast(Node input){
  if (isEmpty()){ //Jika linked list masih kosong,
   head = input; //maka head dan tail sama dengan node input
   tail = input;
  }
  else {
   tail.next = input; //Jika linked list sudah berisi,
   tail = input; //maka input akan di belakang dan menjadi tail
  }
 }

 void insertAfter(int key,Node input){
    Node temp = head;
    do {
      if (temp.data == key){ //Jika data sama dengan key, maka input
       input.next = temp.next; //disambung diantara temp dan temp.next
       temp.next = input;
       System.out.println("Insert data is succeed.");
       break; //dari temp --> temp.next menjadi :
      }   //temp --> input --> temp.next
      temp = temp.next;
    }
    while (temp!=null);
  }

  void insertBefore(int key,Node input){
   Node temp = head;
   while (temp != null){
    if ((temp.data == key)&&(temp == head)){
     this.addFirst(input); /* jika insert pada awal linked list
        maka call method addFirst */
     System.out.println("Insert data is succeed.");
     break;
    }
    else if (temp.next.data == key){
     input.next = temp.next; //dari temp --> temp.next menjadi
     temp.next = input;   //temp --> input --> temp.next
     System.out.println("Insert data is succeed.");
     break;
    }
    temp = temp.next;
   }
  }

  void removeFirst(){
    Node temp = head;
    if (!isEmpty()){
      if (head == tail){  //jika element linked list hanya 1,
       head = tail = null;  //maka head dan tail menjadi null
      }    //sehingga linked list kosong
      else {
       temp = temp.next;  //memajukan temp ke temp.next
       head = temp;  //kemudian head dipindah ke temp
       temp = null;  //kemudian temp di-null (optional)
      }
    }
    else System.out.println("Data is empty!");
  }

  void removeLast(){
    Node temp = head;
    if (!isEmpty()){
      if (tail == head){  //jika element linked list hanya 1
       head = tail = null;  //maka head dan tail menjadi null
      }    //sehingga linked list kosong
      else {
       while (temp.next != tail){
        temp = temp.next; //memajukan temp hingga satu elemen
       }      //sebelum tail.
       temp.next = null;  //temp.next di-null,dan jadi akhir LL
       tail = temp;  //tail dipindah ke temp
       temp = null;
      }
    }
    else System.out.println("Data is empty!");
  }

  void remove(int key){
   Node temp = head;
   if (!isEmpty()){
    while (temp != null){
     if (temp.next.data == key){ //mengganti temp.next dengan
      temp.next = temp.next.next; //temp.next.next
      break; //dari temp --> temp.next -->temp.next.next
     }   //menjadi temp --> temp.next.next
     else if ((temp.data == key)&&(temp == head)){
      this.removeFirst();//jika key berada pada awal linked list,
      break;  //maka call method removeFirst
     }
     temp = temp.next;
    }
   } else System.out.println("Data is empty!");
  }

  void find (int key){
    int i = 0;
    boolean found = false;
    Node temp = head;
    while (temp != null){
      if (temp.data == key){
       found = true;
       break;
      }
      i++;
      temp = temp.next;
    }
    if (found){
      System.out.println(key+" is found at index "+i);
    }
    else System.out.println("Data isn't found");
  }

  void printNode(){
    Node temp;
    temp = head;
    while (temp != null){
      System.out.println(temp.data);
      temp = temp.next;
    }
  }
}

Implementasi Linked List pada Ruby

Buat class Elemen/Node

class ini digunakan untuk membuat objek/instance setiap node. Setiap node minimal terdiri dari 1 variabel penyimpan data dan 1 variabel penunjuk node berikutnya :

class Node

attr_accessor :data, :pnext

def initialize(nilai)

@data=nilai

@pnext=nil

end

Class LinkedList

class SingleLinkedList

attr_accessor :head, :tail

class Node

attr_accessor :data, :pnext

def initialize(nilai)

@data=nilai

@pnext=nil

end

def initialize

@head=nil

@tail=nil

end

Pengecekan LinkedList kosong

def isEmpty

if @tail==nil and @head==nil

return true

else

return false

end

Menambahkan Node

def append(data) # method untuk menambah Node

baru=Node.new(nilai) # membuat objek node BARU

if isEmpty # cek apakah Linked List kosong

@head=baru # node BARU sebagai HEAD

@tail=baru # node BARU sebagai TAIL

else # jika Linked List tidak kosong

@tail.pnext=baru # sambungkan TAIL dengan BARU

@tail=baru # jadikan node BARU sebagai TAIL

end

Menampilkan View LinkedList

def view

temp=@head

while temp!=nil

puts temp.data

temp=temp.pnext

end

Algoritma & Struktur Data II

Implementasi Linked List pada Java & Ruby

Linked List

1 komentar:

Arsip Blog