How to Add and Remove nodes in an unsorted Linked List

Class Diagram: LinkedListNode and LinkedListOperation

If you add any new nodes to the tail of the current linked list, the list will become unsorted, because it does not care what values you are passing, it will simply keep appending the new node at the end of the list. Thus any add operation is O(n) because you will have to sequentially navigate to the end of the list before adding the new node.

Time complexity of remove operation, however varies. If you are removing the head node, the operation takes O(1) time and if you are removing the tail, it takes O(n) time. It really depends on where the node to be deleted is located.

The following source code show you:

  • How to represent unsorted linked list
  • How to add a node
  • How to remove a node

package com.icodejava.blog;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 9, 2014
 * Last Modified On - Mar 9, 2014
 */
public class LinkedListOperation {
	public static void main(String args[]) {

		LinkedListNode linkedList = new LinkedListNode(4).addNode(5).addNode(2).addNode(-5);

		System.out.println("Final List: " + linkedList +"\n");

		// Deleting nodes in an order different from how they were added.
		linkedList = linkedList.removeNode(5).removeNode(-5).removeNode(2).removeNode(4);

		System.out.println("After Removal, the list is: " + linkedList);

	}
}

@SuppressWarnings({"rawtypes", "unchecked"})
class LinkedListNode {
	private LinkedListNode next;
	private Comparable value = null;

	public LinkedListNode(Comparable value) {
		// create first node
		next = null;
		this.value = value;

		System.out.println("Adding Node: " + value);
	}

	/**
	 * This method removes a node from a linked list.
	 */
	public LinkedListNode removeNode(Comparable nodeValue) {

		System.out.println("Removing Node: " + nodeValue);

		if (this.value.compareTo(nodeValue) == 0) { // head
			return this.next;
		} else { // non head

			LinkedListNode current = this;
			LinkedListNode previous = null;

			while (current.next != null) {
				if (current.value.compareTo(nodeValue) == 0) {
					previous.next = current.next;
					return this;
				}

				previous = current;
				current = current.next;
			}

			if (current.value.compareTo(nodeValue) == 0) { // tail
				previous.next = null;
			}

		}

		return this;

	}

	@Override
	public String toString() {

		String data = "";
		LinkedListNode current = this;
		do {
			data += current.value + ",";
			current = current.next;
		} while (current != null);

		return data;
	}

	/**
	 * Adds the node at the tail, making it an unsorted linked list. This method
	 * returns a head node.
	 */
	public LinkedListNode addNode(Comparable value) {

		// if first node
		if (this.next == null) {
			LinkedListNode node = new LinkedListNode(value);
			this.next = node;
			this.next.next = null;
		} else {
			LinkedListNode current = this.next;
			while (current.next != null) {
				current = current.next;
			}

			LinkedListNode node = new LinkedListNode(value);
			current.next = node;
			current.next.next = null;
		}

		return this; // return head
	}

}

Here is the output of running the above program:

Adding Node: 4
Adding Node: 5
Adding Node: 2
Adding Node: -5
Final List: 4,5,2,-5,

Removing Node: 5
Removing Node: -5
Removing Node: 2
Removing Node: 4
After Removal, the list is: null

  1. Implementing a Simple LIFO Stack in Java using LinkedList
  2. Implementing a Simple FIFO Queue in Java Using Linked List
  3. In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – Java Implementation
  4. Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation
  5. Array Max Integer Finder (With Big O Analysis)
  6. A Basic Implementation of Binary Tree in Java
  7. A Basic Implementation of Generic Tree in Java
  8. Basic example of implementing Singly Linked List in Java
  9. How to Add and Remove nodes in an unsorted Linked List
  10. Rotating a two dimensional integer array In-Place and using extra memory
  11. How to reverse a Singly Linked List iteratively and recursively
  12. Sorted Circular Linked List Implementation And Insert Operation
  13. Finding Mean Value Of An Integer Array In Java
  14. How to intersect two sets in Java using java.util.Set data structure.
  15. Bubble Sorting An Integer Array In Ascending and Descending Order
  16. How to split strings and separate the words with spaces
  17. How to easily sort characters in a String?
Tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *