Uncategorized

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

```} ```