java 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.

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

import java.util.Random;

public class IntLinkedList {
	// Linked List Node Object
	class Node {
		Node prev;
		Node next;
		int value;
		public Node(int val) {
			this.value = val;
		}
	}
	
	// public and private Fields
	public Node head;
	public Node tail;
	private int size = 0;
	
	// If the list is null, make the new value to be the head
	// Else insert the new value at the end of the linked list
	public void insert(int val) {
		Node newNode = new Node(val);
		if (this.head == null) {
			this.head = newNode;
			this.head.next = this.tail;
		} else {
			if (this.head.next == null) {
				newNode.prev = this.head;
				this.head.next = newNode;
				this.tail = newNode;
			} else {
				this.tail.next = newNode;
				newNode.prev = this.tail;
				this.tail = newNode;
			}
		}
		this.size++;
	}
	
	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[]) {
		IntLinkedList ll = new IntLinkedList();
		Random rand = new Random();
		int testSize = 10, maxNum = 100;
		
		for(int i=0; i<testSize; i++) {
			ll.insert(rand.nextInt(maxNum));
		}
		ll.print();
		ll.reversePrint();
		System.out.println("Linked list size: " + ll.getSize());
	}
}

Steps to build the above doubly linked list.
1. Create the file IntLinkedList.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 IntLinkedList {
	// 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 insert the new value at the end of the linked list. It increments the size by one after a new node is added to the linked list.

public void insert(int val) {
	Node newNode = new Node(val);
	if (this.head == null) {
		this.head = newNode;
		this.head.next = this.tail;
	} else {
		if (this.head.next == null) {
			newNode.prev = this.head;
			this.head.next = newNode;
			this.tail = newNode;
		} else {
			this.tail.next = newNode;
			newNode.prev = this.tail;
			this.tail = newNode;
		}
	}
	this.size++;
}

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[]) {
	IntLinkedList ll = new IntLinkedList();
	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