Linked List Insert Delete Methods

Linked List Insert Methods

Addition In Linked List

Linked List Insert

Linked List insert methods allow us to insert a Node at a specific place. There are three insert methods based on the position where the new node is inserted.

  1. addLast
  2. addFirst
  3. addAt

1. addLast

As the name suggests, the new node is appended at the last position of the Linked list. The Linked List size is increased by 1. The “tail” points to the newly added Node. Since we have tail Node, the time complexity is O(1) else it would have been O(n).

2. addFirst

The new node is added at the first position of the Linked list. The Linked List size is increased by 1. The “head” points at the newly added Node. The time complexity is O(1) as there is no traversal of List is involved.

3. addAt

This method has two arguments – the Node to insert and an integer index (say ‘k’). The node is added at the kth position of the Linked list. The linked list size is increased by 1.

In case the element to be added is “First” or “Last” then it calls “addFirst” or “addLast” respectively.

In this operation, we also use another function “getNodeAt” which is a private member of Our Linked List class. This function 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.

Thus in this function traversal of the linked list is required. The time complexity of addAt() function is O(n).

Linked List Delete Methods

Deletion In Linked List

Linked List Delete

Linked List supports three methods to delete nodes.

  1. removeLast
  2. removeFirst
  3. removeAt

1. removeLast

This method removes the last element of the Linked list (Provided the list is not an empty list, in which it throws an exception). It moves the “tail” to point towards the 2nd last element (if any ) and decreases the size by ‘1’. Also, it returns the removed data. Since we have tail Node, therefore, the time complexity is O(1) else it would have been O(n).

2. removeFirst

It removes the first element of the Linked list (Provided the list is not an empty list, in which it throws an exception). This method moves the “head” to point towards the 2nd element (if any ) and decreases the size by ‘1’. Also, it returns the removed data. The time complexity is of O(1) as there is no traversal of List is involved.

3. removeAt

It takes an Integer index (let’s say k) as an argument and if the index is valid it removes the ‘kth’ element of the Linked list 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.

In this operation, we also use another function “getNodeAt” which is a private member of the Linked List class. This function 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.

Thus in this function traversal of the list is required, therefore, it is of O(n) which makes the time complexity of operation “removeAt” to be O(n).

Linked List Insert Delete Methods Implementation in Java


package com.journaldev.ds;

public class LinkedList1 {

	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 {
		LinkedList1 list = new LinkedList1();
		list.addLast(10);
		list.addLast(20);
		list.addLast(30);
		list.addLast(40);
		// this will display the list
		list.display();
		// 10 should be removed and printed
		System.out.println(list.removeFirst());
		list.display();
		// 40 should be removed and printed
		System.out.println(list.removeLast());
		list.display();
		// 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);
		list.display();
		// 300 should be added at 2nd index
		list.addAt(300, 2);
		list.display();

	}

}

Output

Insertion Deletion In Java

Linked List Insert Delete Implementation in Java

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