Find and delete specified ‘Link’ from ‘Linked List’

This java program provides functions to search for a data item from Linked List with a specified key value, and to delete an item from Linked List with a specified key value.

Find and Delete Specified Link: Linked List Example

package com.sneppets.dsalgo;

class Link 
{
	public int intData;
	
	public double doubleData;
	
	public Link next;
	
	//constructor 
	//initialize data and no need to initilaize the next field, since it's automatically set to null.
	public Link(int iData, double dData)
	{
		intData = iData;
		doubleData = dData;
	}
	
	public void displayLink()
	{
		System.out.print("{" + intData + "," + doubleData + "} ");
	}	
}

class LinkedList 
{	
	//reference to first link on list
	private Link first;
	
	public LinkedList()
	{
		//no elements in the list yet
		first = null;
	}
	
	//return true if list is empty
	public boolean isEmpty()
	{
		return (first==null);
	}
	
	//insert at the begining of the list
	public void insertFirst(int iData, double dData)
	{
		//create a new link
		Link newLink = new Link(iData, dData);
		//new link --> old first
		newLink.next = first;
		//first --> new link
		first = newLink;		
	}
	
	//method to find a link with a given key
	public Link find(int key)	
	{
		//start from the beginning
		Link current = first;
		//when key don't match
		while (current.intData != key)
		{
			//check if end of the list is reached
			if(current.next == null)
			{
				return null;
			}
			else //if not end of the list then go to next link
			{
				current = current.next;
			}
		}
		//once match if found return link
		return current;		
	}
	
	//method to delete a link with a given key
	public Link delete(int key)
	{
		Link current = first;
		Link previous = first;
		//when key don't match
		while(current.intData != key)
		{
			//check if end of the list is reached
			if(current.next == null)
			{
				return null;
			}
			else
			{
				//go to the next link
				previous = current;
				current = current.next;
			}
		}//found 		
		
		//if the current one is first link
		if(current == first)
		{
			//delete first --> old.next
			first = first.next;			
		}
		else //otherwise just bypass the current
		{
			previous.next = current.next;
		}
		return current;		
	}
	
	public void displayList()
	{
		System.out.println("List from first to last :");
		//start from beginning of the list
		Link current = first;
		//until end of list is reached
		while (current != null)
		{
			//print link details
			current.displayLink();
			//move to next link
			current = current.next;
		}
		System.out.println(" ");
	}
}

/**
 * 
 * @author sneppets.com
 *
 */
public class LinkedListFindDeleteSpecifiedLink {

	public static void main (String[] args)
	{
		
		LinkedList linkedList = new LinkedList();
		
		linkedList.insertFirst(11, 1.05);
		linkedList.insertFirst(33, 3.05);
		linkedList.insertFirst(55, 5.05);
		linkedList.insertFirst(77, 7.05);
		
		linkedList.displayList();
		
		Link link = linkedList.find(55);
		if(link != null)
		{
			System.out.println("Found link with key " + link.intData);
		}
		else
		{
			System.out.println("Could not find the link !");
		}
		
		Link deletedLink = linkedList.delete(33);
		if(deletedLink != null)
		{
			System.out.println("Deleted link with key " + deletedLink.intData);
		}
		else
		{
			System.out.println("Could not delete the link !");
		}
		
		linkedList.displayList();
	}
}

Output

List from first to last :
{77,7.05} {55,5.05} {33,3.05} {11,1.05}  
Found link with key 55
Deleted link with key 33
List from first to last :
{77,7.05} {55,5.05} {11,1.05}

Recommended Posts

• Priority Queue: Array Based Example
• Linked Lists : Simple Linked List Example
• Queue No-count approach and Implementation
• Deque: Double-ended queue is a versatile data structure
• Circular Queue Array Based Implementation
• Queue introduction and implementation in Java
• Reverse a string or word using Stack
• Delimiter Matching using Stack
• Stack Introduction and Implementation in Java

References

Oracle API Documentation