Singly-Linked List
Each item called Node in the Singly linked list is stored with an indication of where the next item is. To access the data in the middle of the list, head, which is the first node, is used to know where the first item is. Different with array, a linked list allows addition or deletion of items in the middle of collection with only a constant amount of data movement. To conclude, The list will be a chain of objects of type Node that contain the data and a reference to the next Node in the list.
The implementation of class Singly Linked List in Java Programming Language :
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;
}
}
}
0 comments:
Post a Comment