Single Link List: One of the basic data structure which teach us how to store the data in the memory so that it can be picked with the minimum effort by the device.
Link list is a data establishment pattern which keep the data in such a manner that form one data node you can either reach to the end or go through the path. Link list creates a path and arrange data so that its easy to pick any data from any place in the memory. Link list is one of the idea to create a chain by arranging data in required manner.
One node keeps the address of another and this process goes on till either data is no more or memory is no more. Single Link List can have multiple method to serve the purpose. These methods can be ...
add(): Adds data node from the starting and it adds node at the end of the list.
insertAt(): Insert a data node at desired place.
deleteAt(): Delete a node with data from any place you wish.
length(): This method can help you finding the number of node in the list.
deleteAll(): This method can be created to make the list empty.
Above are some of the key methods which get used frequently. You can write your own method as per your requirement.
Implementation: We have got a class called Node which act as a memory box which contains value and address of the next node. Once a node is created for the first time that node is being referred as Head Node and this node will be node till it gets deleted by other method. when other node is being created and ready to add further and head node keeps address of its node. This process goes on till we want to stop add process. Similarly when we try to insert a node in between nodes we first need to reach at the node then we can create a node and play with the address part involved in the node. Please check the code. Same process need to be addressed for deletion from a specific place. Last but not the least length, to find the no of node in the list we need to iterate through the list till next node becomes null and counter variable will store the each iteration count.
/* Class that implements Link List concept in java */
package com.ds.linklist;
import com.ds.common.Node;
public class SingleLinkList
{
Node head;
public SingleLinkList()
{
head = null;
}
public SingleLinkList(int val)
{
head = new Node(val);
}
/**
* Adds value to the list and adding means obviously at the end of the list
*/
public void add(int val) throws Exception
{
head = LinkListUtil.getInstance().add(val, head);
}
/**
* Inserts value to the list at give position and if position is greater
* than current size of the list then add this node at the end of the list
*/
public void insertAt(int position, int val) throws Exception
{
// Check the length of existing list, if position is greater than the
// size then add value to the list at the end of the list
int len = length();
if (position > (len + 1)) {
position = len + 1;
}
if (position == 1) {
// If user wants to insert a value at first position then this block
// will be executed
Node insertedNode = new Node(val);
insertedNode.next = head;
head = insertedNode;
} else {
int i = 2;
boolean isNotAdded = true;
Node currentNode = head;
while (currentNode.next != null) {
if (i == position) {
Node insertedNode = new Node(val);
insertedNode.next = currentNode.next;
currentNode.next = insertedNode;
isNotAdded = false;
}
currentNode = currentNode.next;
i++;
}
// Below block will be executed when position is greater than the
// size
// This block of code adds the value at the end of the list
if (isNotAdded) {
Node insertedNode = new Node(val);
currentNode.next = insertedNode;
}
}
}
/**
* Deletes the value at the given position in the list
*/
public void deleteAt(int position) throws Exception
{
int len = length();
if (position > (len)) {
position = len;
}
if (position == 1) {
head = head.next;
} else {
int i = 1;
Node tmpNode = head;
while (head != null) {
if (i == position - 1) {
head.next = head.next.next;
head = tmpNode;
break;
}
head = head.next;
i++;
}
}
}
/**
* Gets the length of the list i.e. no of node in this list
*/
public int length() throws Exception
{
int len = LinkListUtil.getInstance().length(head);
return len;
}
/**
* Prints all the nodes value in the list
*/
public void print() throws Exception
{
Node tmpNode = head;
while (tmpNode != null) {
System.out.print(tmpNode.data + " -> ");
tmpNode = tmpNode.next;
}
System.out.println("");
}
/**
* Deletes all the nodes with give values from the list
*/
private void deleteAll(final int value)
{
Node tmpNode = head;
Node prevNode = null;
while (tmpNode != null) {
if (tmpNode.data == value) {
if (tmpNode == head) {
head = head.next;
} else {
prevNode.next = tmpNode.next;
}
} else {
prevNode = tmpNode;
}
tmpNode = tmpNode.next;
}
}
public static void main(String[] arg) throws Exception
{
SingleLinkList list = new SingleLinkList();
list.add(3);
list.add(2);
list.add(7);
list.insertAt(3, 5);
list.insertAt(4, 10);
list.insertAt(8, 15);
list.deleteAt(1);
list.deleteAt(3);
list.deleteAt(8);
list.insertAt(9, 9);
list.insertAt(9, 2);
list.print();
list.deleteAll(2);
list.print();
System.out.println("link list size issss " + list.length());
}
}
// Below class is used to carry node data ... may be used in same class file or in different class file
package com.ds.common;
public class Node
{
public Integer data;
public Node next;
public Node(int val)
{
data = val;
next = null;
}
}
