Introduction to Linked List (Java implementation)

A linked list is a linear data structure that contains a sequence of elements such that each element has reference to the next element in the sequence.

Each element in the linked list is called “Node”. Each Node contains a data element and a Node next which points to the next node in the linked list.

In a linked list we can create as many nodes as we want according to our requirement.

Why do we need a Linked List?

Although you must have seen Arrays data structure earlier, they too are linear data structure but they pose certain limitations such as:

  • They are static in nature and hence their size cannot be changed.
  • They need contiguous memory to store their values.

To tackle these limitations Linked list offers the following features:

  1. DYNAMIC MEMORY ALLOCATION i.e. the memory allocation is done at the run time by the compiler.
  2. Each individual Node can have any block of memory and it is linked to other nodes by the address of the block, thus no contiguous memory blocks are required.

General Implementation of Linked List

Linked List

Linked List

  • The Linked list class contains a private class Node and an Object of Node class (called as Head) as one of its Properties.
  • The Node head points to the starting of the Linked List.
  • Every Node contains a data element and a Node next which points to the next node in the Linked List.
  • The last nodes point to null.
  • In newer variations, we also have a tail Node element which helps us to reduce the time complexity of operations to be performed easily.

Linked List Operations

A Linked List implementation must have following common purpose methods.

  1. getFirst: It returns the data (if any, else it throws an exception) present at the first Node. It simply returns the “this.head.data” provided “if(this. Size!=0)” i.e. if the size of the Linked list is not zero.
  2. getLast: It returns the data (if any, else it throws an exception) present at the last Node. It simply returns the “this.tail.data” provided “if(this. Size!=0)” i.e. if the size of the Linked list is not zero.
  3. getAt: It takes an Integer index as an argument and if the index is valid(i.e. if index>=0 and index <size of the Linked list) it returns the data of the element present at that index.
  4. getNodeAt: It takes an Integer index as an argument and if the index is valid(i.e. if index>=0 and index <size of the Linked list) it returns the Node at that index.
  5. addLast: It takes an input of type of which Linked list is, and then appends it at the last position of the Linked list, thereby increasing the size by ‘+1’ and pointing the “tail” at the newly added Node.
  6. addFirst: It takes an input of type of which Linked list is, and then appends it at the First position of the Linked list, thereby increasing the size by ‘+1’ and pointing the “head” at the newly added Node.
  7. addAt: It takes an input of type of which Linked list is and it also takes an Integer index (let it be equal to ‘k’) as arguments, and then appends it (data) at the kth position of the Linked list, thereby increasing the size by ‘+1’. In case the element to be added is “First” or “Last” then it calls “addFirst” or “addLast” respectively.
  8. removeFirst: It removes the first element of a Linked list (Provided the list is not an empty list, in which it throws an exception) and moves the “head” to point towards the 2nd element (if any ) and decreases the size by ‘1’. Also, it returns the removed data.
  9. removeLast: It removes the last element of the Linked list (Provided the list is not an empty list, in which it throws an exception) and moves the “tail” to point towards the 2nd last element (if any ) and decreases the size by ‘1’. Also, it returns the removed data.
  10. removeAt: It takes an Integer index (let’s say k) as an argument and if the index is valid(i.e. if index>=0 and index <size of Linked list) removes the ‘kth’ element of Linked list (Provided the list is not an empty list, in which it throws an exception)  and decreases the size by ‘1’. Also, it returns the removed data. In case the element to be removed is “First” or “Last” then it calls “removeFirst” or “removeLast” respectively.
  11. display: This method prints the whole Linked list by traversing it once starting from a pointer which points to “head” until it points to “null”.

Linked List Implementation in Java


package com.journaldev.ds;

public class LinkedList {

	private class Node {

		int data;

		Node next;

	}

	private Node head;

	private Node tail;

	private int size;

	public int size() {

		return this.size;

	}

	public int getFirst() throws Exception {

		if (this.size == 0) {

			throw new Exception("LL is Empty.");

		}

		return this.head.data;

	}

	public int getLast() throws Exception {

		if (this.size == 0) {

			throw new Exception("LL is Empty.");

		}

		return this.tail.data;

	}

	public int getAt(int idx) throws Exception {

		if (this.size == 0) {

			throw new Exception("LL is Empty.");

		}

		if (idx < 0 || idx >= this.size) {

			throw new Exception("Invalid Index.");

		}

		Node temp = this.head;

		for (int i = 1; i <= idx; i++) {

			temp = temp.next;

		}

		return temp.data;

	}

	private Node getNodeAt(int idx) throws Exception {

		if (this.size == 0) {

			throw new Exception("LL is Empty.");

		}

		if (idx < 0 || idx >= this.size) {

			throw new Exception("Invalid Index.");

		}

		Node temp = this.head;

		for (int i = 1; i <= idx; i++) {

			temp = temp.next;

		}

		return temp;

	}

	public void addLast(int item) {

		// create

		Node nn = new Node();

		nn.data = item;

		nn.next = null;

		// attach

		if (this.size > 0)

			this.tail.next = nn;

		// dm update

		if (this.size == 0) {

			this.head = nn;

			this.tail = nn;

			this.size += 1;

		} else {

			this.tail = nn;

			this.size += 1;

		}

	}

	public void addFirst(int item) {

		// create

		Node nn = new Node();

		nn.data = item;

		nn.next = null;

		// attach

		nn.next = this.head;

		// dm update

		if (this.size == 0) {

			this.head = nn;

			this.tail = nn;

			this.size++;

		} else {

			this.head = nn;

			this.size++;

		}

	}

	public void addAt(int item, int idx) throws Exception {

		if (idx < 0 || idx > this.size) {

			throw new Exception("Invalid Index.");

		}

		if (idx == 0) {

			addFirst(item);

		} else if (idx == this.size) {

			addLast(item);

		} else {

			// create

			Node nn = new Node();

			nn.data = item;

			nn.next = null;

			// attach

			Node nm1 = getNodeAt(idx - 1);

			Node np1 = nm1.next;

			nm1.next = nn;

			nn.next = np1;

			// dm

			this.size++;

		}

	}

	public int removeFirst() throws Exception {

		if (this.size == 0) {

			throw new Exception("LL is empty.");

		}

		Node temp = this.head;

		if (this.size == 1) {

			this.head = null;

			this.tail = null;

			this.size = 0;

		} else {

			this.head = this.head.next;

			this.size--;

		}

		return temp.data;

	}

	public int removeLast() throws Exception {

		if (this.size == 0) {

			throw new Exception("LL is empty.");

		}

		Node temp = this.tail;

		if (this.size == 1) {

			this.head = null;

			this.tail = null;

			this.size = 0;

		} else {

			Node sm2 = getNodeAt(this.size - 2);

			sm2.next = null;

			this.tail = sm2;

			this.size--;

		}

		return temp.data;

	}

	public int removeAt(int idx) throws Exception {

		if (this.size == 0) {

			throw new Exception("LL is empty.");

		}

		if (idx < 0 || idx >= this.size) {

			throw new Exception("Invalid Index.");

		}

		if (idx == 0) {

			return removeFirst();

		} else if (idx == this.size - 1) {

			return removeLast();

		} else {

			Node nm1 = getNodeAt(idx - 1);

			Node n = nm1.next;

			Node np1 = n.next;

			nm1.next = np1;

			this.size--;

			return n.data;

		}

	}

	public void display() {

		System.out.println("----------------------");

		Node temp = this.head;

		while (temp != null) {

			System.out.print(temp.data + " ");

			temp = temp.next;

		}

		System.out.println(".");

		System.out.println("----------------------");

	}

	public static void main(String[] args) throws Exception {

		LinkedList list = new LinkedList();

		list.addLast(10);

		list.addLast(20);

		list.addLast(30);

		list.addLast(40);

		// this will display the list

		list.display();

		// first element i.e.10 should be printed

		System.out.println(list.getFirst());

		// last element i.e.40 should be printed

		System.out.println(list.getLast());

		// element at 3rd index i.e.40 should be printed

		System.out.println(list.getAt(3));

		// a memory address of a node should be printed

		System.out.println(list.getNodeAt(3));

		// 10 should be removed and printed

		System.out.println(list.removeFirst());

		// 40 should be removed and printed

		System.out.println(list.removeLast());

		// list without 10 and 40 should be printed

		list.display();

		// 100 should be added at first

		list.addFirst(100);

		list.display();

		// 30 should be removed

		list.removeAt(2);

		// 300 should be added at 2nd index

		list.addAt(300, 2);

		list.display();

	}

}

Output

Implementation Of Linked List

LinkedLIst Implementation

NOTE: Java provides implementation of LinkedList. For actual programming, use the official implementation.

Java LinkedList – LinkedList In Java

Linked List Operations Time Complexity

Operations Time Complexity
getFirst O(1)
getLast O(1) {Note: It is because we have ‘tail’ pointer too , else it would have been O(n) }
getAt O(n)
getNodeAt O(n)
addLast O(1) {Note: It is because we have ‘tail’ pointer too , else it would have been O(n) }
addFirst O(1)
addAt O(n)
removeFirst O(1)
removeLast O(1) {Note: It is because we have ‘tail’ pointer too , else it would have been O(n) }
removeAt O(n)
Display O(n)

Conclusion

LinkedList is one of the most popular data structure. It’s used a lot in storing data sequentially. We have provided the basic implementation of Linked List. But it’s not optimized for production usage. Please use the language-specific implementation of the Linked List in actual programming.

Comments

  1. venkates says:

    Nice article about how to execute Java code within Java comments and easy to understand to java learners.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages