# Complete Link List Implementation

### Website

#### arpit tak

I like JAVA . I code. I chill. I blog.I eat. I sleep. I dream.

View Full Profile →

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 {

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

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)
{
{
insert(data);
}

else{
}
}

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

&nbsp;

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

public void removeFirst()
{

}

public int getLast()
{
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[])
{

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)
{
}

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

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

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 : ");
System.out.println();

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

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

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 : ");
System.out.println();

System.out.println();

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

/*System.out.print("After appending 2 lists becomes 1 as : " );
System.out.println();*/

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

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

// 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 : " );

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

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

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

*/

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 : ");