What is Link List?

                                                                       Link List in Java 

Click here for home  page       

When we want to work with unknown number of data values, we use a linked list data structure to organize that data. 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".

Simply a list is a sequence of data, and linked list is a sequence of data linked with each other. 

The formal definition of a single linked list is as follows...

Single linked list is a sequence of elements in which every element has link to its next element in the sequence.

In any single linked list, the individual element is called as "Node". Every "Node" contains two fields, data and next. The data field is used to store actual value of that node and next field is used to store the address of the next node in the sequence.

The graphical representation of a node in a single linked list is as follows...

In a single linked list, the address of the first node is always stored in a reference node known as "head " (Some times it is also known as "front").


Always next part (reference part) of the last node must be NULL.

In a single linked list we perform the following operations...

1. Insertion
2. Deletion
3. Reverse
4. Display

Before we implement actual operations, first we need to setup empty list. First perform the following steps before implementing actual operations.

Single Link List

Below java program to create Node. In one node, data and reference of next node will be there. 

//Node 

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();

}

}


 clear here for Home page