Linked List

Linked list is a linear data structure in programming like arrays but with a big difference, In linked list, the word “link” is an object with a reference to another link  here is an example:

The head holds the first link to the list and to access any link in the list you have to go through the head and the Null at the end of the linked list simply means that there is no link ahead. In an  array it is difficult to put data where you want them to be after you have already filled it with data, it has to come right after your previous entry your  or else to have to move all existing data to a different index to fit in and also,and also in an array you are stuck with a fixed size in memory and can be very difficult to resize but when it comes to a linked list you can add, delete, and even move data where you want without affecting the other links ,This is possible only because linked list are not index like arrays. This is how to write a linked list in java:




public class Node {

 Node next;
 int data;
 
 public Node(int data) {
 this.data = data;
  }
}

class LinkedList{
 Node head;
 
 public void append(int data){
 if(head == null){
 head = new Node(data);
 return;
   }
 Node current = head;
 while(current.next != null){
 current = current.next;
   }
 current.next = new Node(data);
 }
 
 public void prepend(int data){
 Node newHead = new Node(data);
 
 newHead.next = head;
 head = newHead;
 }
 
 public void deleteLink(int data){
 Node link = head;
 
 if(link.data == data){
 head = head.next;
   }
 while(link.next != null){
 if(link.next.data == data){
 link.next = link.next.next;
   }
 link = link.next;
   }
 
 }
 public void display(){
 Node list = head;
 
 while(list != null){
 System.out.println(list.data);
 list = list.next;
    }
  }
}

Now let’s try to run the class above:

public class Test {

 public static void main(String[] args) {
 
 LinkedList list = new LinkedList();

 list.append(4);
 list.append(6);
 list.prepend(9);
 list.append(2);
 list.prepend(21);
 
 list.display();
 
 System.out.println();

 System.out.println("remove the number 4 and you get \n");
 
 
 list.deleteLink(4);
 
 list.display();

  }
 

}

This is the output:

21
9
4
6
2

remove the number 4 and you get

21
9
6
2

The downside of a  linked list is that it is slow when it comes to random access because linked lists are not indexed like arrays. in an array, random access is  O(1)  because every data in an array is associated with an index but in a linked list you have to start from the head and loop through every link to get to the particular data you want which is in O(n) and that is not very efficient.

Depending on what type of data you have linked list can be really great for insertion/deletion in O(1)

 

 

Leave a Reply

Your email address will not be published.