# 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;

}

`}`