Delete linked list Java

Linked List Insert Methods

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

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

Linked List Delete Methods

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 (lets 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

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