Linked List with O(1) Insertion Complexity
A simple linked list program where insertion complexity is O(1) order of one i.e independent of data size.
Here is the code for the same
Here is the Node/Element/Data object of linked list
Note: This program has been written with minimum code so that users can copy and experiment with it. This is not a full fledged program, hence not recommended for production use.
public class Node {
Node previous;
T element;
Node next;
public Node(Node previous, T element, Node next) {
this.previous=previous;
this.element=element;
this.next=next;
}
@Override
public String toString() {
return “Node [element=” + element + “]”;
}
}
And here is the linked list implementation,
package java8pract.linkedlist_custom;
/**
* An implementation of linked list. Entire linked list is dependent on first element in the list.
*/
import java.util.ArrayList;
import java.util.List;
public class CustomLinkedList {
Node firstNode;
Node tempNode;
Node lastNode;
/**
* Add an element to the linked list
* +/—————————————-
* + 1. if first node is null, create a node and assign it to first node.
* + 2. and assign the newly created node to a temp Node;
* + 3. for consecutive additions, get the temp node into a middle methods level node
* + 4. Create new node and assign previous node as middle node.
* + 5.update the last node.
* + 6. middle node.next to newly created node
* + 7. and update temp node with newly created node.
* @param element
*/
public void add(T element) {
Node node = null;
if (null == firstNode) {
node = new Node(null, element, null);
firstNode = node;
} else {
Node middleNode = tempNode;
node = new Node(middleNode, element, null);
lastNode = node;
middleNode.next = node;
}
tempNode = node;
}
/**
* Get all the elements in linked list
*
* @return
*/
public List getAll() {
List list = new ArrayList();
Node temp = firstNode;
while (temp != null) {
list.add(temp);
System.out.println(temp.element);
temp = temp.next;
}
return list;
}
/**
* Get all the elements in the linked list in reverse order.
*
* @return
*/
public List getAllReverse() {
List list = new ArrayList();
Node temp = lastNode;
while (temp != null) {
list.add(temp);
System.out.println(temp.element);
temp = temp.previous;
}
return list;
}
public Node get(T t) {
Node temp = firstNode;
while (temp != null) {
if (temp.element !=null && temp.element.compareTo(t)==0) {
break;
} else {
temp = temp.next;
}
}
return temp;
}
/**
* Get the first node (HEAD) in the linked list
* @return
*/
public Node getFirstNode(){
return firstNode;
}
/**
* Get the last node in the linked list.
* @return
*/
public Node getLastNode(){
return lastNode;
}
}
Techno Java 