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

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s