Table of Contents
Linked List Insert Methods
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.
- addLast
- addFirst
- 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
Linked List Delete
Linked List supports three methods to delete nodes.
- removeLast
- removeFirst
- 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
Linked List Insert Delete Implementation in Java
