java sorted linked list implementation

Linked list is a data structure that stores individual data in an object/node, then each node is connected to each other with a pointer, and only the first node and the last node has direct reference to it.

If each node only has one pointer that points to the next node, it is called singly linked list. If each node has two pointers, one points to the previous node and one points to the next node, it is called doubly linked list.

For example in a doubly linked list in Java, a node is an object that has two pointers and one value that holds the data. The pointers and the value of the node are all properties of the node. The type of the pointers is the node itself so it can be used to point to the previous node or the next node in order to link all the nodes together to form a linked list. The type of the value that the node holds can be anything, it could be as simple as an integer value or an object that represents a person. Every node will have two pointer with one pointer to the previous node and one points to the next node, except the head and tail nodes. The head and tail nodes are the special nodes we keep references to point to them. The head node will have the pointer to point to the next node but its previous pointer will be null. Likewise, the tail node will have the pointer to point to the previous node but it’s next pointer will be null.

In an unsorted linked list, each new node is added to the tail and the new node becomes the new tail. In a sorted linked list implementation, each new node is added to the list in the correct position according to the values. The the value in the new node is already in the list, it will be ignored.

Here is a sorted doubly linked list implementatation in Java with each node holding an integer value. IntSortedLinkedList.java

import java.util.Random;
public class IntSortedLinkedList {
	// Linked List Node Object
	class Node {
		public Node prev;
		public Node next;
		public int value;
		public Node(int val) {
			this.value = val;
		}
	}
	
	// public and private Fields
	public Node head;
	public Node tail;
	private int size = 0;
	
	// Insert the new node
	// If nodeToInsertAfter is null, make the newNode to be the head node
	// Else If nodeToInsertAfter.next is null, make the newNode to be the tail node
	// Else Insert the newNode after the node nodeToInsertAfter
	private void insertNode(Node nodeToInsertAfter, Node newNode) {
		Node tmpNode;
		if (nodeToInsertAfter == null) {
			this.head.prev = newNode;
			tmpNode  = this.head;
			this.head = newNode;
			this.head.next = tmpNode;
			if (this.size <= 1) {
				this.tail = tmpNode;
				this.tail.next = null;
			}
		} else if (nodeToInsertAfter.next == null) {
			newNode.prev = nodeToInsertAfter;
			nodeToInsertAfter.next = newNode;
			this.tail = newNode;
		} else {
			Node prevNode, nextNode;
			prevNode = nodeToInsertAfter;
			nextNode = nodeToInsertAfter.next;
			prevNode.next = newNode;
			newNode.prev = prevNode;
			newNode.next = nextNode;
			nextNode.prev = newNode;
		}
		this.size++;
	}
	
	// Find the node that the new node will be inserted after it
	private Node findNodeToInsertAfter(Node newNode) {
		Node curNode = this.head;
		if (newNode.value < curNode.value) {
			return null;
		}
		while(curNode.next != null) {
			if (newNode.value == curNode.value) {
				return curNode;
			}
			else if (newNode.value > curNode.value && newNode.value < curNode.next.value) {
				return curNode;
			}
			curNode = curNode.next;
		}
		return curNode;
	}
	
	// Get the value and create the new node to be inserted.
	// If the current list is null, set the new node to be the head.
	// Else find nodeToInsertAfter and then insertNode accordingly. 
	public void insert(int value) {
		System.out.println("value: " + value);
		Node newNode = new Node(value);
		Node nodeToInsertAfter;
		if (this.head == null) {
			this.head = newNode;
			this.head.next = this.tail;
			this.size++;
		} else {
			nodeToInsertAfter = findNodeToInsertAfter(newNode);
			if (nodeToInsertAfter == null || nodeToInsertAfter.value != newNode.value) {
				insertNode(nodeToInsertAfter, newNode);
			}

			if (this.tail == null)System.out.println("tail is null when value is : " + value);
		}
	}

	public int getSize() {
		return this.size;
	}
	
	public void print() {
		Node curNode = this.head;
		while(curNode != null) {
			System.out.println(curNode.value);
			curNode = curNode.next;
		}
	}

	public void reversePrint() {
		Node curNode = this.tail;
		while(curNode != null) {
			System.out.println(curNode.value);
			curNode = curNode.prev;
		}
	}
	
	public static void main(String args[]) {
		IntSortedLinkedList ll = new IntSortedLinkedList();
		Random rand = new Random();
		int testSize = 5;
		int maxNum = 100;
		for(int i=0; i<testSize; i++) {
			ll.insert(rand.nextInt(maxNum)+1);
		}
		ll.print();
		System.out.println("..........................");
		ll.reversePrint();
		System.out.println("list size: " + ll.getSize());
	}
}

Steps to build the above sorted doubly linked list.
1. Create the file IntSortedLinkedList.java with the following code. The subclass Node will be the class we will use to create a new node in a linked list. As you can see, there are two pointers, prev and next with type Node itself, and a value of int type. Also there is a constructor that just takes an integer value and assign it to the value properity of the node. All the codes following this will be added after the class definition class Node.

public class IntSortedLinkedList {
	// Linked List Node Object
	class Node {
		Node prev;
		Node next;
		int value;
		public Node(int val) {
			this.value = val;
		}
	}
}

2. Declare the head and tail node of the linked list as well as a integer property that we will use to keep track the size of the node.

// public and private Fields
public Node head;
public Node tail;
private int size = 0;

3. Define the insert method to add a new node to the linked list. If the list is null, make the new value to be the head, else find the correct position in the existing linked list for the new node and insert it. The insert method is public so it can be used to get the value to be inserted into the linked list. The findNodeToInsertAfter and insertNode methods are private methods, they are helper methods for the insert method. The findNodeToInsertAfter method finds the correct position for the new node to be inserted and the insertNode method does the actual insert operation.

// Insert the new node
// If nodeToInsertAfter is null, make the newNode to be the head node
// Else If nodeToInsertAfter.next is null, make the newNode to be the tail node
// Else Insert the newNode after the node nodeToInsertAfter
private void insertNode(Node nodeToInsertAfter, Node newNode) {
	Node tmpNode;
	if (nodeToInsertAfter == null) {
		this.head.prev = newNode;
		tmpNode  = this.head;
		this.head = newNode;
		this.head.next = tmpNode;
		if (this.size <= 1) {
			this.tail = tmpNode;
			this.tail.next = null;
		}
	} else if (nodeToInsertAfter.next == null) {
		newNode.prev = nodeToInsertAfter;
		nodeToInsertAfter.next = newNode;
		this.tail = newNode;
	} else {
		Node prevNode, nextNode;
		prevNode = nodeToInsertAfter;
		nextNode = nodeToInsertAfter.next;
		prevNode.next = newNode;
		newNode.prev = prevNode;
		newNode.next = nextNode;
		nextNode.prev = newNode;
	}
	this.size++;
}

// Find the node that the new node will be inserted after it
private Node findNodeToInsertAfter(Node newNode) {
	Node curNode = this.head;
	if (newNode.value < curNode.value) {
		return null;
	}
	while(curNode.next != null) {
		if (newNode.value == curNode.value) {
			return curNode;
		}
		else if (newNode.value > curNode.value && newNode.value < curNode.next.value) {
			return curNode;
		}
		curNode = curNode.next;
	}
	return curNode;
}

// Get the value and create the new node to be inserted.
// If the current list is null, set the new node to be the head.
// Else find nodeToInsertAfter and then insertNode accordingly. 
public void insert(int value) {
	System.out.println("value: " + value);
	Node newNode = new Node(value);
	Node nodeToInsertAfter;
	if (this.head == null) {
		this.head = newNode;
		this.head.next = this.tail;
		this.size++;
	} else {
		nodeToInsertAfter = findNodeToInsertAfter(newNode);
		if (nodeToInsertAfter == null || nodeToInsertAfter.value != newNode.value) {
			insertNode(nodeToInsertAfter, newNode);
		}

		if (this.tail == null)System.out.println("tail is null when value is : " + value);
	}
}

4. A public mehtod to get the size of the linked list.

public int getSize() {
	return this.size;
}

5. A public method to print the value of all nodes in the linked list from head to tail. It assigns the head node to the temp node curNode which is used as an iterator in the while loop. Each loop prints the value of the curNode and then overwrite the curNode with the next node. When it reached to the tail node, the tail node has no next pointer and the loop ends, and we have printed the values of all the nodes in the linked list.

public void print() {
	Node curNode = this.head;
	while (curNode != null) {
		System.out.println(curNode.value);
		curNode = curNode.next;
	}
}

6. A public method to print the value of all nodes in the linked list from tail to head. Same logic as the above, the only differences is we start from the tail and uses the prev pointer in each node.

public void reversePrint() {
	Node curNode = this.tail;
	while (curNode != null) {
		System.out.println(curNode.value);
		curNode = curNode.prev;
	}
}

7. The main method to test the linked list implementation.

public static void main(String args[]) {
	IntSortedLinkedList ll = new IntSortedLinkedList();
	Random rand = new Random();
	int testSize = 10, maxNum = 100;
	
	for(int i=0; i<testSize; i++) {
		ll.insert(rand.nextInt(maxNum));
	}
	ll.print();
        System.out.println("..........................");
	ll.reversePrint();
	System.out.println("Linked list size: " + ll.getSize());
}

Search within Codexpedia

Custom Search

Search the entire web

Custom Search