Linked Lists : Simple Linked List Example

Linked lists are second most commonly used data structure after arrays. In this tutorial we will see how to create a simple linked list.

Simple Linked List Operations

insertFirst(): Inserting item at the beginning of the list
deleteFirst(): Deleting item at the begining of the list
displayList(): Iterating through linkedlist and display items.

Linked Lists Introduction:

Linked lists are among simplest and most common data structures. They are suitable for use in many kinds of general-purpose databases.

It can be used to implement common abstract data types such as lists, stacks, queues etc.,

In linked list each data item is embedded in a link. A link is an object of a class called Link. Each Link object contains reference (next) to the next link in the list.

Because there are many similar links in the list, it makes sense to use a separate class for them and differentiate from linked list itself. A field in the linked list or list itself contains a reference to the first link.

In this tutorial you will see how to implement a Simple Linked List. Other concepts that you might need to know are: Double-Ended Lists, Sorted Lists, Doubly Linked Lists and Lists with Iterators (an approach to access list elements randomly)

Application of Linked Lists:

You can use linked list in many cases where you are using arrays, if you don’t need frequent random access to individual items using an index.

Simple 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;		
	}
	
	//delete first item
	//assume list is not empty
	public Link deleteFirst()
	{
		//save reference to link
		Link temp = first;
		//delete first --> old next
		first = first.next;
		//return deleted link
		return temp;
	}
	
	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 SimpleLinkedListExample {
	
	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();
		
		while ( !linkedList.isEmpty())
		{
			//deleting link
			Link link = linkedList.deleteFirst();
			System.out.print("Deleted link: ");
			//display deleted link details
			link.displayLink();
			System.out.println(" ");
			
		}		
		//display linkedlist list elements
		linkedList.displayList();		
	}

}

Note:

In the constructor of Link class we had initialized only the data and not the next field since it’s automatically set to null when it is created.
If you want, you can set null explicitly if you want for clarity. The null value means it does not refer to anything and the link is not connected to any other links.
Reference manipulations are the heart of linked-list algorithms.
deleteFirst() is the reverse of insertFirst() method.

Output

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

Linked Lists : Simple Linked List Example

Simple Linked List Operations

Linked Lists Introduction:

Application of Linked Lists:

Simple Linked List Example

Recommended Posts

References