Linked List Insertion
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)
Login/Signup to comment