Complete Link List Implementation

A linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.

Lot of questions on linked lists appears in the interviews. Interviewers in these types of questions will be more interested on how we handle pointers, how we use linked list properties etc. In this series I discuss some of the questions that appear in interviews for the linked lists.

import java.util.NoSuchElementException;
class Node{

int data;
Node next;

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

public String toString()
{
 return ""+data;
}

}

public class LinkList {

private Node head;

public void insert(int data)
{
if(head==null)
{
head = new Node(data,null);
}
else
head= new Node(data,head);
}

public void print(Node head)
{
 for(Node node = head;node!=null;node=node.next)
 {
 System.out.print(node.data+" ");
 }
}

public void sum(Node head)
{
 int evensum = 0;
 int oddsum = 0;
 for(Node node = head;node!=null;node=node.next)
 {

 if(node.data%2==0)
 {
 evensum = evensum + node.data;
 }
 else
 {
 oddsum = oddsum + node.data;
 }

}
 System.out.println(" Sum of Link List 1 even numbers : "+evensum );
 System.out.println(" Sum of Link List 1 odd numbers : "+oddsum );

}

public void addLast(int data)
{
 if(head==null)
 {
 insert(data);
 }

 else{
 addLast(head,data);
 }
}

public void addLast(Node node,int data)
{
 if(node.next!=null)
 {
 addLast(node.next,data);
 }
 else
 node.next = new Node(data,null);
}

 

public int getFirst()
{
Node tmp =head;
return tmp.data;
}

public void removeFirst()
{
 head = head.next;

}

public int getLast()
{
Node tmp =head;
while(tmp.next!=null)
{
tmp = tmp.next;
}

return tmp.data;
}

public void delete(int key)
{
Node prev = null;
Node curr = head;

while(curr.next!=null && curr.data!=key)
{
 prev = curr;
 curr = curr.next;
}

prev.next = curr.next;

}

public void reverse( Node node ) {
 if( node != null ) {
 reverse(node.next);
 System.out.print( node.data + " " );
 }
 }


 public int len()
 {
 int count=0;
 for(Node cur = head; cur.next!=null;cur = cur.next)
 {
 count++;
 }
 return count;
 }

// recursion way
 public Node search (Node l, int value)
 {
 if (l == null || l.data == value)
 return l;
 else
 return search(l.next, value);
 }

 // iteration way..
 public Node lookup(Node h, int n) {
 for(Node p = h.next; p != null; p = p.next )
 if( p.data == n )
 return p;
 return null; // return null if item not found
 }


 public static Node append( Node p, Node q )
 {
 if ( p == null)
 return q;
 else {
 p.next = append( p.next, q );
 return p;
 }
 }


 public static Node zip( Node p, Node q ) {
 if ( p == null)
 return q;
 else if ( q == null)
 return p;
 else {
 p.next = zip( q, p.next ); // Note how we exchange p and q here
 return p;
 }
 }


 public static Node merge( Node p, Node q )
 {
 if ( p == null)
 return q;
 else if ( q == null)
 return p;
 else if (p.data < q.data) {
 p.next = merge( p.next, q );
 return p;
 }
 else {
 q.next = merge( p, q.next );
 return q;
 }
 }


 public static Node copy( Node p ) {
 if( p == null )
 return null;
 else
 return new Node(p.data, copy( p.next )); // recursion always uses function name so copy( p.next ), instead of p.next
 }

 public static Node insertInOrder( int k, Node p ) {
 if( p == null || p.data >= k )
 return new Node( k, p );

 if(p.next!=null && p.data < k)
 p=p.next;

 else {
 p.next= insertInOrder( k, p.next );
 }
 return p;

 }
 // iterative way...
 public void insertSorted( Node h, int n ) {
 Node p = h.next; // p points to first real node in list
 Node q = h; // q trails p
 while( p != null ) {
 if(p.data >= n) { // found insertion point, between p and q
 q.next = new Node(n, p);
 return;
 }
 q = p;
 p = p.next;
 }
 q.next = new Node(n, null); // Node must be added at end of list
 }


 public static Node deleteItem( int k, Node p ) {
 if( p == null ) // if the list is ordered use: ( p == null || p.data > k )
 return p;
 else if ( p.data == k )
 return p.next; // if you want to delete all instances, use: return deleteItem( k, p.next );
 else {
 p.next = deleteItem( k, p.next );
 return p;
 }
 }

public static void main(String arg[])
{
LinkList list = new LinkList();
LinkList list2 = new LinkList();

int[] first = new int[] {2,5,9,10,33,20,55};

int[] second = new int[] {1,7,17,21,39,65,19};

for(int i : first)
{
 list.insert(i);
}

for(int i : second)
{
 list2.addLast(i);
}

System.out.print("Link List Traversal 1 : ");
list.print(list.head);
System.out.println();

System.out.print("Link List Traversal 2 : ");
list2.print(list2.head);

System.out.println();

System.out.println("First element : "+list2.getFirst());
System.out.println("Last element : "+list2.getLast());

list2.delete(21);
System.out.print("Link List Traversal 2 : ");
list2.print(list2.head);
System.out.println();

System.out.print("Link List reverse Traversal 2 : ");
list2.reverse(list2.head);

System.out.println();
list2.removeFirst();
list2.print(list2.head);

System.out.println();
System.out.print("Length of link list : "+list2.len());
System.out.println();

System.out.print("item present in link list : "+list2.lookup(list2.head,65) );
System.out.println();
System.out.print("item present in link list : "+list2.search(list2.head,65) );
System.out.println();

System.out.print("Link List Traversal 1 : ");
list.print(list.head);
System.out.println();

list.sum(list.head);
 System.out.println();

System.out.print("Link List Traversal 2 : ");
list2.print(list2.head);

/*System.out.print("After appending 2 lists becomes 1 as : " );
list2.head = append(list2.head, list.head);
list2.print(list2.head);
System.out.println();*/

System.out.println();
System.out.println();
System.out.print("Link List Traversal 1 : ");
list.print(list.head);
System.out.println();

System.out.print("Link List Traversal 2 : ");
list2.print(list2.head);

// i have commented these as they merge/ zip lists so below functions cant be excuted , unlink 1 by one to use them
 System.out.println();
System.out.print("After zipping 2 lists becomes 1 as : " );
list2.head = zip(list2.head, list.head);
list2.print(list2.head);

// for this function 2 lists must be in sorted order...
/*System.out.println();
System.out.print("After merging 2 lists becomes 1 as : " );
list2.head = merge(list2.head, list.head);
list2.print(list2.head); */

System.out.println();
/*
System.out.print("New Link List Traversal copy of 2 list in newlist : ");

LinkList newList = new LinkList();
 newList.head = copy( list2.head ); // newList.head required bec.. we need refernece of 1 node..
 list2.print(newList.head);

*/

LinkList sort = new LinkList();

int[] sorted = new int[] {1,3,5,11,15,19};

for(int i : sorted)
{
 sort.insert(i);
}

System.out.println();
System.out.println();

System.out.print("Link List Sorted Traversal : ");
sort.reverse(sort.head);
System.out.println();


 sort.head = deleteItem( 5 ,sort.head);
sort.reverse(sort.head);

}
}