Implementasi Linked List pada Java & Ruby

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;
    }
  }
}