Problem Statement

Implement a single linked list in Java

Solution Explanation

Linked List is one of the heavily used data structure in computer programming. It is basically a linear collection of data elements and is represented by a group of nodes each pointing to the next using a pointer.

1 -> 2 -> 3 -> 4 -> 5 -> null
|                   |                    
head                tail 

The above sequence is an abstract representation of a single linked list, where each node has a 'value' and a pointer to another node. The first node of the linked list is identified as 'head' and the last node whose pointer stores a null reference is referred to as 'tail'.

There are typically 3 operations which you can perform on a linked list,

• Addition
• Search
• Deletion

There are different types of addition again, like you can add a node at the start, or at the end or at a given index. The same goes with the deletion.

Search is a straightforward operation which takes O(n) time since you have to start with the head, check if each value at every node is the target we are looking for.

Node Structure

Represeting the node in your give n programming language is the starting point before you implement a complete linked list. Below is a typical node structure in Java.

class Node{
    T val;
    Node next;
 }

As you can see, the value can be of any type and the pointer is a self reference to the next node.

To implement addition, search and deletion, you should understand how to nagivate to the next node, changing the link of a node to a different one etc.

Below is the complete java implementation code with annotated method comments,

/*
 * Author : Venkatesh, Thallam
 * Date : 10/09/2017
 * Single Linked List Java Implementation
 */
public class LinkedListImpl {
	
	class Node{
		int val;
		Node next;
		public Node(int val){
			this.val = val;
		}
	}
	
	Node head = null, tail = null;
	
	public static void main(String[] args) {
		LinkedListImpl listImpl = new LinkedListImpl();
		listImpl.addNode(10);
		listImpl.addNode(20);
		listImpl.addNode(30);
		listImpl.addNode(40);
		listImpl.printLinkedList();
		listImpl.addNodeAtStart(50);
		listImpl.printLinkedList();
		listImpl.removeNode();
		listImpl.printLinkedList();
		listImpl.removeNodeAtCertainIndex(3);
		listImpl.printLinkedList();
		
	}
	
	/*
	 * Adds node at the end of the current list
	 */
	public void addNode(int val){
		if(head==null){
			Node temp = new Node(val);
			head = temp;
			tail = temp;
		}else{
			tail.next = new Node(val);
			tail = tail.next;
		}
	}
	
	/*
	 * Adds node at the start of the current list
	 */
	public void addNodeAtStart(int val){
		if(head==null){
			Node temp = new Node(val);
			head = temp;
			tail = temp;
		}else{
			Node temp = new Node(val);
			temp.next = head;
			head = temp;
		}
	}
	
	/*
	 * Adds node at the certain index.
	 */
	public void addNodeAtCertainIndex(int val, int index){
			Node temp = head;
			int count = 0;
			while(temp!=null && ++count!=index)
				temp = temp.next;
			Node node  = new Node(val);
			node.next = temp.next;
			temp.next = node;
	}
	
	/*
	 * Removes the last node in the given list and updates tail node
	 */
	public void removeNode(){
		 Node temp = head;
		 while(temp.next!=null && temp.next.next!=null){
			 temp = temp.next;
		 }
		 temp.next = null;
		 tail = temp;
	}
	
	/*
	 * Removes the first node in the given list and updates head node
	 * 
	 */
	public void removeNodeAtStart(){
		//The first node would become zombie and should be garbage collected after the below operation
		 head = head.next;
	}
	
	/*
	 * Removes the node at the given index in the given list and updates head node
	 * 
	 */
	public void removeNodeAtCertainIndex(int index){
		Node temp = head;
		int count = 0;
		while(temp!=null && ++count!=index)
			temp = temp.next;
		temp.val = temp.next.val;
		temp.next = temp.next.next;
	}
	
	/*
	 * Checks if a node with the given value exist in the list, returns true or false.
	 * Alternatively you can return the index too.
	 */
	public boolean search(int target){
		Node temp = head;
		while(temp!=null){
			if(temp.val == target)
				return true;
		}
		return false;
		
	}
	
	/*
	 * Checks if a node with the given value exist in the list, returns the index of the given value in the list.
	 */
	public int searchAndReturnIndex(int target){
		Node temp = head;
		int count = 0;
		while(temp!=null){
			count++;
			if(temp.val==target) return count;
		}
		return -1;
	}
	
	/*
	 * Prints the current list
	 */
	
	public void printLinkedList(){
		System.out.println();
		Node temp = head;
		while(temp!=null){
			System.out.print(" "+temp.val);
			temp = temp.next;
		}
	}
	

}

Time Complexity

The time complexity for each of the operations is,

• Addition - O(1)
• Addition at Index - O(n) where n is the number of elements.
• Removal - O(1)
• Removal at Index - O(n) where is the number of elements.
• Search - O(n) where n is the number of elements.

Look at more problems involving linked lists.