Linked List Implementation in Java

-
Hi All, for some time we can take a break from Android. Here , I am presenting the implementation of linked list in java, which is very useful in industries as well as helps in programming interview questions.

I am including few important methods of linked lists as well -
  • insert - To insert a node to linked list
  • display - to display all the nodes.
  • delete - to delete a node from linked list.
  • NthToLast - to print the nth to last node
  • deletenode - to delete a node from middle by giving the data.
  • deleteDups - to delete duplicate in linked list (using hashtable)
  • deleteDups1 - to delete duplicate in linked list without using additional memory space.
  • addList - to add to separate linked lists node by node
  • FindBeginning - This method will check whether a loop is present and returns the node where the loop starts, else return null.
I am publishing the code also in this blog, but I recommend you to use this only as a reference. Happy coding.

package com.linkedlist;
import java.util.Hashtable;
import java.util.LinkedList;


public class listlinked {
public static class ListElement 
{
ListElement next;
Object data;
public ListElement(Object data)
{
this.data=data;
}
}
public static void main(String args[])
{
new listlinked().run();
}
ListElement head=null;
ListElement tail =null;
public void run()
{
//head = new ListElement(10);
insert(head,10);
insert(head,11);
insert(head,12);
insert(head,13);
display(head);
delete(head,13);
insert(head,14);
insert(head,15);
display(head);
ListElement nthlast = NthToLast(head, 4);
if(nthlast!=null)
{
System.out.println(" Data corresponding to nth - to - last = " +nthlast.data);
}
else
{
System.out.println(" data is null");
}
deleteNode(12);
display(head);
insert(head,17);
insert(head,14);
insert(head,17);
insert(head,17);
display(head);
deleteDups1(head);
System.out.println(" After deleting duplicate elements.. cool.. ");
display(head);
//for adding two linked list
ListElement head1= new ListElement(3);
ListElement head2= new ListElement(5);
//insert(head1,3);
insert(head1,1);
insert(head1,5);
//insert(head2,5);
insert(head2,9);
insert(head2,2);
insert(head2,4);
System.out.println(" The first list elements are as follows...");
display(head1);
System.out.println(" The second list elements are as follows...");
display(head2);
ListElement sumlist =addlist(head1,head2,0);
System.out.println(" The sum of two lists is as follows .. ");
display(sumlist);
ListElement loop =null;
System.out.println(" Checking the beginning of loop in linked list");
loop = FindBeginning(head);
if(loop==null)
{
System.out.println(" There is no loops in the linked list..");
}
else
{
int loopdata= (Integer) loop.data;
System.out.println(" Beginning of loop = "+loopdata);
}
}
//code for inserting data
public void insert(ListElement node, Object data)
{
if(node==null)
{
head =new ListElement(data);
}
else
{
while(node.next!= null)
{
node=node.next;
}
ListElement node1 = new ListElement(data);
node.next=node1;
}
System.out.println(" Inserted " +data);
}
//end of code for inserting data
//code for displaying data
public void display(ListElement node)
{  
System.out.println();
System.out.println(" Displaying data...");
while(node.next!=null)
{
System.out.println (" Data - "+node.data);
node=node.next;
}
System.out.println (" Data - "+node.data);
}
//end of code for display
//code for deleting data
public void delete(ListElement node, Object data)
{
if(node.data == data)
{
head=head.next;
return;
}
else
{
while(node.next!=null)
{
if(node.next.data==data)
{
node.next=node.next.next;
}
else
{
node=node.next;
}
}
return;
}
}

//end of code for deleting
//code for nth to last

public ListElement NthToLast(ListElement node, int n)
{
if(head==null|| n<1)
{
return null;
}
ListElement p1 =head;
ListElement p2=head;
for(int j=0;j<n-1;j++)
{
if(p2==null)
{
return null;
}
p2=p2.next;
}
if(p2==null)
{
return null;
}
while(p2.next!= null)
{
p2=p2.next;
p1=p1.next;
}
return p1;
}

//end of code for nth to last
//code for deletenode

public void deleteNode(Object data)
{ 
ListElement node=head;
if(node.data==data)
{
head=node.next;
}
else
{
while(node.next!=null)
{
if(node.next.data==data)
{
node.next=node.next.next;
}
else
{
node=node.next;
}
}
return;
}
}

//end of code for deletenode

//for deleting duplicate elements

public static void deleteDups(ListElement node)
{
Hashtable<Object, Boolean> table =new Hashtable<Object, Boolean>();
ListElement previous =null;
while(node!=null)
{
if(table.containsKey(node.data))
{
previous.next=node.next;
}
else
{
table.put(node.data, true);
previous=node;
}
node=node.next;
}
}

//end of code for deleting dups..

//start of code for deleting dups without additional space 

public static void deleteDups1(ListElement node)
{
if(node == null)
{
return;
}
ListElement previous = node;
ListElement current = node.next;
while(current != null)
{
ListElement runner= node;
while(runner!= current)
{
if(runner.data==current.data)
{
  ListElement cool = current.next;
  previous.next=cool;
  current=cool;
  break;
}
runner=runner.next;
}
if(runner==current)
{
previous=current;
current =current.next;
}
}
}
//end of deleteDups1

//code for adding two linked lists

public ListElement addlist(ListElement node1, ListElement node2, int carry)
{
ListElement result = null;
int bal =0;
while((node1 != null) || (node2 != null))
{
int value = 0;
value = value+bal;
if(node1!=null)
{
value= value+ (Integer) (node1.data);
node1=node1.next;
}
if(node2!=null)
{
value= value+ (Integer) (node2.data);
node2 =node2.next;
}
if(value >= 10)
{
value =value%10;
bal=1;
}
else
{
bal=0;
}
if(result==null)
{
result=new ListElement(value);
}
else
{
insert(result,value);
}
}
return result;
}

//end of code for addlists

//function for finding the beginning of a loop

public ListElement FindBeginning(ListElement node)
{
ListElement node1=node;
ListElement node2 = node;
while(node2.next!=null)
{
node1=node1.next;
node2 =node2.next.next;
if(node1==node2)
{
break;
}
}//while
if(node2.next==null)
{
return null;
}
node1=head;
while(node1!=node2)
{
node1=node1.next;
node2=node2.next;
}
return node2;
}
//end of function for beginning of loop;
}

The output of the above code is as follows:

Inserted 10
 Inserted 11
 Inserted 12
 Inserted 13

 Displaying data...
 Data - 10
 Data - 11
 Data - 12
 Data - 13
 Inserted 14
 Inserted 15

 Displaying data...
 Data - 10
 Data - 11
 Data - 12
 Data - 14
 Data - 15
 Data corresponding to nth - to - last = 11

 Displaying data...
 Data - 10
 Data - 11
 Data - 14
 Data - 15
 Inserted 17
 Inserted 14
 Inserted 17
 Inserted 17

 Displaying data...
 Data - 10
 Data - 11
 Data - 14
 Data - 15
 Data - 17
 Data - 14
 Data - 17
 Data - 17
 After deleting duplicate elements.. cool.. 

 Displaying data...
 Data - 10
 Data - 11
 Data - 14
 Data - 15
 Data - 17
 Inserted 1
 Inserted 5
 Inserted 9
 Inserted 2
 Inserted 4
 The first list elements are as follows...

 Displaying data...
 Data - 3
 Data - 1
 Data - 5
 The second list elements are as follows...

 Displaying data...
 Data - 5
 Data - 9
 Data - 2
 Data - 4
 Inserted 0
 Inserted 8
 Inserted 4
 The sum of two lists is as follows .. 

 Displaying data...
 Data - 8
 Data - 0
 Data - 8
 Data - 4
 Checking the beginning of loop in linked list
 There is no loops in the linked list..

Good to Read

Comments

Post a Comment

Popular posts from this blog

Difference between "diff" and "sdiff" commands in Unix

-
Image
Hi everyone, in this blog post, I will be discussing about the difference between "diff" and "sdiff" commands in Unix. This is my first post about Unix. diff command diff command will compare two files and prints the difference between the 2 files. The format of diff command is diff file1 file2 . sdiff command sdiff command will compare two files side by side. The format of sdiff command is sdiff file1 file2. The contents of files are displayed side by side with a marker denoting the difference between each files. Some of the important markers used in sdiff are as follows: | - denotes the 2 files differ in the line completely. < - only the first file contains the line. > - only the second file contains the line. The better way to depict the difference is by showing examples. Here, I am comparing 2 files which are named as " ipl_teams_2008.txt " and " ipl_teams_2015.txt ". Let's see the contents of the files.
Read more

Anonymous classes in C++

-
Anonymous Classes in C++ Anonymous class is a class with no name. The main advantage of using an anonymous class is that it provides reusability of the class. Also anonymous class helps in encapsulation of data. Anonymous class is basically used when only one instance of the class is needed and it has only a short body. By defining an anonymous class, it does the same steps of defining a local class and instantiating it. The anonymous class is rightly used after it is defined. Following specifies an example of anonymous class in C++. class { int a; } c1; Here, c1 is an object of the anonymous class. Usually, anonymous classes in C++ are defined using "typedef" ( a keyword to assign alternative names to existing types). Typedef helps in giving another name to the class. It is shown as below: typedef class { int a; } newclass; newclass c2; Here newclass is the object of the anonymous class and c2 is its instance. Member variables can also be initialized in ano
Read more