Linked List in Java
A linked list is a data structure that consists of a group of nodes representing a sequence together. Each node includes a piece of data, in this example we’ll use numbers, and they contain a reference to the next node in the list. For example, let’s look at the difference between an array of numbers, and a linked list with nodes containing the same number data.
In an array each element has no relation to the other, and in Java the size of an array is not dynamic. For a linked list, we can solve both of those problems. By writing a Node class, we can store a given value and a reference to a following Node. This would allow us the ability to dynamically add elements and traverse through them. To write the Node class, we can create two constructors, one where we don’t know the next Node and the other where we do. It will also be helpful down the road to create getter and setter methods:
public class Node {
int value;
Node next; public Node(int value){
this.value = value;
next = null;
} public Node(int value, Node next){
this.value = value;
next = next;
} public static int getValue(){
return this.value;
} public static Node getNext(){
return this.next;
} public static void setValue(int value){
this.value = value;
} public static void setNext(Node next){
this.next = next;
}
}
The second class we need to create is the Linked List class. One thing I have learned from the HackerRank 30 Days of Code challenge is to always think about three basic goals when writing a new class:
- What are the properties of this class?
- How to write the constructor(s)?
- What methods do I need to write?
Each linked list has a node at the head(or a null node at the head) so we’re going to want that, and then it’s going to be helpful to keep track of the length of the linked list, creating an integer “count”. For our constructors, we want to be able to create a linked list with a node and without one. In terms of the methods that we will need, the goal is to be able to implement the following:
- Ability to add nodes
- Ability to remove nodes
- How many nodes in this sequence?
- Is the sequence empty?
- Get data from a specified node
With that, here is a the basic skeleton of a linked list class:
public class LinkedList {
// properties
Node head;
int count;
// constructors
public LinkedList() {
this.head = null;
this.count = 0;
}
public LinkedList (Node head){
this.head = head;
this.count = 1;
}
// methods
public void addNode(int value) {}
public void removeNode() {}
public int getCount() {}
public Boolean isEmpty() {}
public int get(int nodeNum) {}
}This is how I implemented each method:
addNode(int value)
In order to add a node to the linked list, we have to iterate through the linked list until we reach a node that has a null next value. Our getters and setters we wrote earlier are extremely useful here. When we first start the method, we begin at the head, assigning the variable current to head. We then create a new node called temp, with addNode’s parameter “value” as the parameter for temp. From there we check first if the head is null and we have an empty linked list. If this is the case, the head becomes assigned to temp and we return out of the method. In case that head is not null, we want to reach the end of the linked list and change the final node’s next value from null to temp.
public void addNode(int value) {
Node current = head;
Node temp = new Node(value);
if(current == null){
this.head = temp;
count+=1;
return;
}
while(current.getNext() != null){
current = current.getNext();
}
current.setNext(temp);
count += 1;
}removeNode()
Removing a node takes big O(N), as we have to traverse through the end of the Linked List, deleting the final item from the chain. Once the last item is deleted by eliminating the current node’s reference point, you would decrement the count of the linked list.
public void removeNode() {
Node current = head;
if(current == null) {
System.out.println("no Nodes to remove, empty Linked List");
return;
}
else if(getCount() == 1) {
System.out.println("only one Node in Linked List, deleting Node");
this.head = null;
count--;
return;
}
while(current.getNext().getNext() != null) {
current = current.getNext();
}
current.setNext(null);
count--;
}getCount() and isEmpty()
These are both pretty straightforward. getCount() acts as a getter method for the count property, and isEmpty checks if count is zero.
public int getCount() {
return this.count;
}
public Boolean isEmpty() {
return getCount() == 0;
}get(int nodeNum)
Our final method is to retrieve the value of a given node. The one tricky part about this one is we’re not counting from 0 in the for loop, being that we’re not saying there’s a 0th node. If a node less than or equal to 0 gets inputted, we’re returning -1. If we have a valid node, then with a for loop we’re going to traverse the Linked List, assigning a Node current to the Node we are looking for.
public int get(int nodeNum) {
if (nodeNum <= 0) {
return -1;
}
Node current = head;
for(int i = 1; i < nodeNum; i++) {
current = current.getNext();
}
return current.getValue();
}With our methods written, we can put together some driver code to test it.
public static void main(String[] args) {
// create a node
Node fiveNode = new Node(5);
// create a linked list with fiveNode at the head
LinkedList myLinkedList = new LinkedList(fiveNode);
// add a node with the value 4
myLinkedList.addNode(4);
System.out.println(fiveNode.getNext().getValue());
// get count of linked list, should be 2
System.out.println(myLinkedList.getCount());
// remove node, print count of linked list should be 1 and nextnode for fiveNode should be null
myLinkedList.removeNode();
System.out.println(myLinkedList.getCount());
System.out.println(fiveNode.getNext());
// add a node of value 8, get the second element from linked list--should be 8
myLinkedList.addNode(8);
System.out.println(myLinkedList.get(2));
}Output:
4
2
1
null
8While we could have easily called the built in LinkedList class from Java, now we know what’s going on underneath the hood. Thanks for reading, keep on Linking and Listing!
