ISourceCode

Make the frequent cases fast and the rare case correct

Monthly Archives: August 2011

Algorithm to Reverse a Linked List

This is an implementation to reverse the elements of a linked list.

I have used the explanation and snippet from this course notes

In this method no new storage is required.

Please refer the notes for a clear understanding.

There are other approaches to solve this, for example recursion or by moving nodes. In this case reference to nodes are reassigned.

class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
} 
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("List items from first to last :");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	public void reverse() 
	{
		Node current = first;
    		first = null;
    		while (current != null) 
		{
		        Node save = current;
		        current = current.next;
		        save.next = first;
		        first = save;
		}
	}
	public Node search(int val)
	{
		Node current = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
				current = current.next;
		}
		return current;
	}
	public Node delete(int val)
	{
		Node current = first;
		Node previous = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
			{
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		return current;
	}

	
} 
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object = new LinkedList();
		object.insert(10);
		object.insert(20);
		object.insert(30);
		object.display();
	
		while( !object.isEmpty() )
		{
			Node member = object.delete();
			System.out.print("Deleted ");
			member.displayNode();
			System.out.println("");
		}
		object.display();
	
		object.insert(40);
		object.insert(50);
		object.insert(60);
		object.display();

		System.out.println("Reversing the Linked List");
		object.reverse();

		object.display();

		Node objecttosearch = object.search(50);

		if( objecttosearch != null)
			System.out.println("Found Node : " + objecttosearch.item);
		else
			System.out.println("Cannot locate the node");

		Node objecttodelete = object.delete(50);

		if( objecttodelete != null )
			System.out.println("Deleted node : " + objecttodelete.item);
		else
			System.out.println("Cannot delete the node");


		object.display();
		
	} 
}

OUTPUT:

labuser@ubuntu:~/linkedlist$ java LinkedListBlog
List items from first to last :
[30]
[20]
[10]

Deleted [30]

Deleted [20]

Deleted [10]

List items from first to last :

List items from first to last :
[60]
[50]
[40]

Reversing the Linked List
List items from first to last :
[40]
[50]
[60]

Found Node : 50
Deleted node : 50
List items from first to last :
[40]
[60]

labuser@ubuntu:~/linkedlist$

Implementation of Stack using Linked List

A stack is a First in Last out data structure. Hence we can use two methods of a linked list that is inserting node at beginning of a list and then deleting node at the beginning of a list to develop a stack ADT with push and pop operations.

As the elements get inserted they move further away from the first node of the list. So the element inserted first will end up being the last node if there is a sequence of push operations.

Class Stack abstracts the underlying functioning of a linked list. We need to just call methods of the Stack class.

import java.io.*;
class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
}
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("Elements from top to bottom");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	
}
class Stack
{
	private LinkedList listObj;
	public Stack()	
	{	
		listObj = new LinkedList();
	}
	public void push(int num)
	{
		listObj.insert(num);
	}
	public Node pop()
	{
		return listObj.delete();
	}
	public boolean isEmpty()
	{
		return listObj.isEmpty();
	}
	public void displayStack()
	{
		System.out.print("Stack : ");
		listObj.display();
	}
} 
class StackLinkedListBlog
{
	public static void main(String[] args) throws IOException
	{
		Stack demo = new Stack(); 
		demo.push(10); 
		demo.push(20); 
		demo.displayStack(); 
		demo.push(30); 
		demo.push(40); 
		demo.displayStack(); 
		demo.pop(); 
		demo.pop(); 
		System.out.println("Two elements are popped");
		demo.displayStack(); 
	} 
}

OUTPUT:

labuser@ubuntu:~/Stack$ java StackLinkedListBlog
Stack : Elements from top to bottom
[20]
[10]

Stack : Elements from top to bottom
[40]
[30]
[20]
[10]

Two elements are popped
Stack : Elements from top to bottom
[20]
[10]

labuser@ubuntu:~/Stack$

Linked List Implementation – Inserting at Front, Deleting from Front and Search/delete- Java

The linked list implemented here
1. Inserts a node at beginning of the list
2. Deletes a node from the beginning of the list.
3. Search a specific node in the list
4. Search and Deletes a node from the list

Please note delete() method has been overloaded , in the second use of delete a parameter is passed to be searched and deleted

class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
} 
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public Node delete()//deletes at beginning of list
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
	public void display()
	{
		System.out.println("List items from first to last :");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next; 
		}
		System.out.println("");
	}
	public Node search(int val)
	{
		Node current = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
				current = current.next;
		}
		return current;
	}
	public Node delete(int val)
	{
		Node current = first;
		Node previous = first;
		while(current.item != val)
		{
			if(current.next == null)
				return null;
			else
			{
				previous = current;
				current = current.next;
			}
		}
		if(current == first)
			first = first.next;
		else
			previous.next = current.next;
		return current;
	}

	
} 
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object = new LinkedList();
		object.insert(10);
		object.insert(20);
		object.insert(30);
		object.display();
	
		while( !object.isEmpty() )
		{
			Node member = object.delete();
			System.out.print("Deleted ");
			member.displayNode();
			System.out.println("");
		}
		object.display();
	
		object.insert(40);
		object.insert(50);
		object.insert(60);
		object.display();

		Node objecttosearch = object.search(50);

		if( objecttosearch != null)
			System.out.println("Found Node : " + objecttosearch.item);
		else
			System.out.println("Cannot locate the node");

		Node objecttodelete = object.delete(50);

		if( objecttodelete != null )
			System.out.println("Deleted node : " + objecttodelete.item);
		else
			System.out.println("Cannot delete the node");


		object.display();
		
	} 
}

OUTPUT:
labuser@ubuntu:~/linkedlist$ java LinkedListBlog
List items from first to last :
[30]
[20]
[10]

Deleted [30]

Deleted [20]

Deleted [10]

List items from first to last :

List items from first to last :
[60]
[50]
[40]

Found Node with val 50
Deleted node with val 50
List items from first to last :
[60]
[40]

labuser@ubuntu:~/linkedlist$

Follow

Get every new post delivered to your Inbox.