Blog Image

Link List Data Structure  

Linked list is a linear data structure that contains sequence of elements such that each element links to its next element in the sequence. Each element in a linked list is called as "Node". Here node is a logical name.

So we can say it is a collection of nodes.

 It is a sequence of elements linked with each other, means every element has link to its next element in the sequence.

 In linked list data structure, node plays a very important roles.

Types of Linked List

First node of every link list knows as head and last node knows as tail.

1) Singly linked list: In a single linked list, each node contains two things, data and the address of the next node.

Class Node{

  int data;

  Node link;

}

Node Structure:


 Here Link refers next node address.

2) Double linked list: In a double linked list, each node contains three parts. Each node will contains the two pointers as prev or next i.e shown below.

Class Node{

  int data;

  Node next;

  Node prev;

}

Node Structure:


3) Circular linked list: Last node will point to the first node i.e head.

        Node Structure:

 

 Where do we can use linked list?

 a) when we need constant-time( insertions/deletions)  from the list of data

b) When we don't know how many items will be in the list.

c) when we don't need random access to any elements or items

d) When we want to insertion or deletion at middle of list

If we see history section of web browser, where it creates the linked list of visited page.

In Hash table, linked list is used to create chaining to resolve hash collision. In all Map collection linked list is implementable in the form of Entry.

Some important operations on Linked list

 1) Insertion(at first, middle, last position)

2) Deletions(from first element, last element,middle element)

3) Finding middle element

4) Addition of two linked list

5) Reverse of linked list with one iteration

6) Merge two sorted list

                  And many more?????.

//create node in java



public class Node {
 private int element;
 private Node next;
public Node(int element, Node next) {
                                  this.element = element;
                                  this.next = next;
                       }
 
                       public int getElement() {
                              return element;
                       }
 
                        public void setElement(int element) {
                              this.element = element;
                        }
 
                         public Node getNext() {
                         return next;
                          }
 
                          public void setNext(Node next) {
                          this.next = next;
                           }
 
}//Node class closed here
 
//Single Link List
 
public class SLinkedList {
 private Node head;
 private Node tail;
 
 public void addFirst(Node node) {
 
  if (head == null) {
   head = node;
   tail = node;
  } else {
 
   node.setNext(head);
   head = node;
 
  }
 }
 
 public void addLast(Node node) {
 
  if (head == null) {
   addFirst(node);
 
  } else {
 
   tail.setNext(node);
   tail = node;
  }
 }

//it will take the position and delete the node from start(head)
 
 public void deleteNodeFromStart(int position) {
  Node temp = null;
  Node prev = null;
  temp = head;
  boolean flag = false;
  int count = 1;
  while (temp != null) {
   prev = temp;
   temp = temp.getNext();
   count++;
   if (count == position) {
    flag = true;
    break;
   }
  }
  if (temp != null) {
   if (flag == true)
    prev.setNext(temp.getNext());
 
  } else
   System.out.println("Position not found");
 
 }
 
 // Reverse of Link List
 /*
  * input = 1---->2----->3----->4 head tail
  * ==================================== Output =4----->3------>2----->1 tail
  * head
  *
  * solution) 1<----2<-----3<-----4 just we need to reverse the pointer from
  * start to end
  *
  * Taking one new node as newhead. currently head is on first position
  * 1---->2----->3----->4 head we have to move the head to end one by one by
  * reversing the link head.setNext(newhead) now it becomes link
  * newhead<-----head before this keep head next node into one temp variable
  * of node type
  *
  * then newhead=head and head will move to next position.
  *
  * newhead<----1<----2 head continue, till head is not null
  */
 
 public void reverse() {
  Node newhead = null;
  Node temp = null;
  while (head != null) {
   temp = head.getNext();
   head.setNext(newhead);
   newhead = head;
   head = temp;
 
  }
  head = newhead;
 
 }
 
 public void display() {
  Node temp = null;
  temp = head;
  System.out.print(temp.getElement());
  while (temp.getNext() != null) {
   System.out.print("---->" + temp.getNext().getElement());
   temp = temp.getNext();
  }
 
 }
 
 public static void main(String[] args) {
 
  Node node1 = new Node(1, null);
  Node node2 = new Node(2, null);
  Node node3 = new Node(3, null);
  SLinkedList link = new SLinkedList();
  link.addFirst(node1);
  link.addLast(node2);
  //link.addLast(node3);
  // link.deleteNodeFromStart(2);
  //link.reverse();
  link.display();
 
 }
}

  Questions For Practise:

1)How to merge two Sorted Lists

http://srimanjavagroup.com/thread/java-se-faq-8217-s-and-interview-questions-java-se/5007/how-to-mer...

2)Old Even Linked List

http://srimanjavagroup.com/thread/java-se-faq-8217-s-and-interview-questions-java-se/5009/old-even-l...

3)Addition of list data

http://srimanjavagroup.com/thread/java-se-faq-8217-s-and-interview-questions-java-se/4987/we-have-tw...


About author

User Image
Amritk

Learning java is my passion. I am a Java developer in one of product based company located in Hyderabad and very passionate about Java technology and always an explorer and learner in new technologies in Java.

0

-Comments

Be the first person to write a comment for this Blog
Load More

No More Comments

Leave a Comment

Your comment has been posted and will appear soon.