ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to delete duplicate elements in a Linked List

Algorithm uses two iterating pointers called current and runner.
Current does a normal iteration of the list while the runner iterates the previous node of current. runner checks for a match with the current as they iterate through the list. At any point of time the runner encounters only one duplicate.

This method uses no additional buffer/list except for a temp node for changing references.

The delete duplicate function is : deleteDup()

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;
	}
	public void deleteDup()
	{
		if(first == null)
			return;
		Node previous = first;
		Node current = previous.next;
		while(current != null)
		{
			Node runner = first;
			while(runner != current)
			{
				if(runner.item == current.item)
				{
					Node temp = current.next;
					previous.next = temp;
					current = temp;
					break;
				}
				runner = runner.next;
			}
			if(runner == current)
			{
				previous = current;
				current = current.next;
			}
		}
	}

	
} 
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object = new LinkedList();
		object.insert(10);
		object.insert(20);
		object.insert(30);
		object.display();
	
		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.insert(50);
		object.insert(40);
		object.display();

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

		object.display();
		System.out.println("Deleting duplicating elements in the list");
		object.deleteDup();
		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]

List items from first to last :
[20]
[10]

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

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

Deleting duplicating elements in the list
List items from first to last :
[10]
[20]
[40]
[50]
[60]

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

labuser@ubuntu:~/linkedlist$

One response to “Algorithm to delete duplicate elements in a Linked List

  1. sunil August 28, 2012 at 9:18 am

    A nice explanation of removing duplicates from a list is at

    http://www.ritambhara.in/remove-duplicates-from-a-linked-list/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: