Linked List Insertion

June 23, 2019

Inserting a node in the linked list have following cases:

• Insertion at Beginning
• Insertion at End
• Insertion at any position

Code

[code language=”java”]
import java.util.*;

public class test {

public static void main(String[] args) throws Exception {
LinkedList ll = new LinkedList();
ll.addFirst(60);
ll.addFirst(50);
ll.addFirst(40);
ll.addFirst(30);
ll.addFirst(20);
ll.addFirst(10);
ll.addLast(70);
ll.addLast(80);
ll.addAt(90, 8);
ll.addAt(1000, 4);
ll.addAt(0, 0);

ll.display();

}

}

class LinkedList {
private class Node {
int data;
Node next;

// Node constructor
// There are two fields in the node- data and address of next node
public Node(int data, Node next) {
this.data = data;
this.next = next;
}
}

private Node head;
private Node tail;
private int size;

// Linked list constructor
public LinkedList() {
this.head = null;
this.tail = null;
this.size = 0;

}

// Function to find the size of linked list
public int size() {
return this.size;
}

// Function to check whether linked list is empty or not
public boolean isEmpty() {
return this.size() == 0;
}

// Function to traverse and print the linked list
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + "–>");
// Set temp to point to the next node
temp = temp.next;
}
System.out.println("END");
}

// Function to add a node in beginning of linked list
public void addFirst(int item) {
// Create a temp node which points to head
Node temp = new Node(item, head);

// If linked list is empty, temp is the head and tail node both
if (this.size == 0) {
this.head = this.tail = temp;
}

// else set the head such that it now points to temp node
else {
this.head = temp;

}

this.size++;
}

// Function to add a node at last of linked list
public void addLast(int item) {

// Create a temp node which does not point to any node
Node temp = new Node(item, null);

// If linked list is empty, temp is the head and tail node both
if (this.size() == 0) {
this.head = this.tail = temp;
}

// else change next of tail such that it points to temp
// and now the new tail is temp
else {
this.tail.next = temp;
this.tail = temp;

}

this.size++;
}

// Function to add a node at any position in linked list
public void addAt(int item, int index) throws Exception {

// Invalid cases
if (index < 0 || index > this.size) {
throw new Exception("Index out of bound");
}

// If index is 0 then it is addFirst
if (index == 0) {
addFirst(item);
}

// Else If index is equal to size of linked list then it is addLast
else if (index == size) {
addLast(item);
}

// Else find the node at (index-1) and change the next pointer
else {

// Create a node n pointing to null initially
Node n = new Node(item, null);

// Getting node at (index-1)
int i = 0;
Node nm1 = head;
while (i < (index – 1)) {
nm1 = nm1.next;
i++;
}

// Now nm1 is the node at (index-1)

// Node np1 is the node at (index)
Node np1 = nm1.next;
nm1.next = n;
n.next = np1;
this.size++;

}
}
}
[/code]

Complexity

• addFirst: O(1)
• addLast: O(1) as here we have taken last node (tail) in the constructor. If we don’t have tail node, then it would be O(n) because tail finding complexity is O(n)
• addAt: O(n)