java linked list

Java #1 – Singly Linked List Tutorial w/ Implementation & Problem Solving – Reversing & Element Find

Knowing how to implement a Java Linking List is fundamental to any software engineer. Although my primary focus is on hardware, I’ve always pushed myself to expand my knowledge when it comes to software. In this tutorial, I will be going over the implementation of a Singly Linked List in Java. I will be also implementing some additional functionality which often comes up as a question during software engineering interviews.

Java Linked List Overview

My goal is to never bore you with details in my videos, but this post will contain a bit more info! Those of you who aren’t familiar with programming & data structures, should take the time and understand what a linked list really is and what purpose it serves.

Linked List Definition & Theory

A linked list is an ordered set of data elements, each containing a link to its successor (Reference: Wiki). A doubly linked list (which we won’t be covering) also contains a link to its predecessor. Simply put, a linked list is a set of nodes where each node contains some data and a reference to the next node.

Here’s an example of a linked list with 3 nodes. Each node has an integer value stored in it: 12, 99 and 37. The node containing 12 points to the node which contains 99, the 99 points to the node with the value 37.
java linked list

Java Linked List Implementation

As mentioned before, I will be going over a full implementation of a linked list which allows the user to initialize the data structure, add elements and remove them. Keep in mind that there are many variations and additions to the “basic” data structure, so code may differ.

Software / Hardware Used

Eclipse – Version: Neon Release (4.6.0) Build id: 20160613-1800
Java – Version: JavaSE-1.8
Computer – MacBook Pro (Retina, 15-inch, Mid 2015)

public class SinglyLinkedList {
//Implement a Node
private static class Node {
private T element;
private Node next;
public Node(T e, Node n) {
element = e;
next = n;
}
public T getElement() {
return element;
}
public Node getNext() {
return next;
}
public void setNext(Node n) {
next = n;
}
}

We begin by implementing the node of our linked list. The fundamental structure of this node is that it should hold data and reference to the next node. We also add utility functions which allow the structure to retrieve and set data within the node.

private Node head = null;
private Node tail = null;
private int size = 0;
public SinglyLinkedList() {};
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}

The linked list has several pointers. The first two will be pointing to the head & tail of our list. They will keep the reference of the start & the end of our structure for easy access. We also initialize a “size” integer which will keep track of the length of the list. It will allow us to check for the number of elements we have, verify if the list is empty and other functionality.

public T first() {
if(isEmpty()) {
return null;
}
return head.getElement();
}
public T last() {
if(isEmpty()) {
return null;
}
return tail.getElement();
}
public void addFirst(T e) {
head = new Node<>(e, head);
if(size == 0) {
tail = head;
}
size++;
System.out.println("Added head node with '" + head.getElement() + "' element.");
}
public void addLast(T e) {
Node newNode = new Node<>(e, null);
if(isEmpty()) {
head = newNode;
}else{
tail.setNext(newNode);
}
tail = newNode;
size++;
System.out.println("Added tail node with '" + tail.getElement() + "' element.");
}

The first() and last() functions are used to “peek” at the elements stored inside of the first & last node. The addFirst() and addLast() functions are used to create a node at the beginning or the end of our list. Each function verifies the status of the list and takes care of updating the variables as needed. We also have println() calls which prints out the diagnostics of our functions.

public T removeFirst() {
if(isEmpty()) {
return null;
}
T answer = head.getElement();
head = head.getNext();
size--;
if(size == 0) {
tail = null;
}
System.out.println("Removed head node with '" + answer + "' element.");
return answer;
}
}

The final function of our list removes the first node and returns the element inside of it. There is extra logic which takes care of how we increment & decrement the size of the java linked list.

Reversing a Java Linked List using Pointers

One of the most common questions during software engineering interviews is a linked list reversal. Although it may seem trivial at first, reversing a list who’s nodes only point to the next one is not that simple. The following function is an addition to the linked list structure and allows a full reversal of a linked list of any length.

public void reverseList() {
if(size <= 1) { }else if(size == 2) { tail.setNext(head); head = tail; tail = head.getNext(); tail.setNext(null); }else { Node current = head;
Node currentNext = head.getNext();
Node currentNextNext = currentNext.getNext();
tail = head;
while(currentNext != null) {
currentNext.setNext(current);
current = currentNext;
currentNext = currentNextNext;
if(currentNextNext != null) {
currentNextNext = currentNextNext.getNext();
}
}
tail.setNext(null);
head = current;
}

}
Reversing a list with 0 or 1 nodes is simple. There’s nothing for us to do. If we have a list of 2 nodes, all we need to do is swap the references for our head & tail pointers. The case of 3 and more nodes becomes somewhat more complex. We need to walk through the list with 3 references and shift the pointers from the current element to the previous one. For obvious reasons, in a java linked list this needs to continue until we are at the end. At the end of our “walkthrough”, we swap the references for the head and tail of the list.

Finding & Removing a Linked List Node

Finding a node and retrieving the information stored in it is important. This problem was also seen many times on software engineering interviews. Tje following function implements just that.

public T removeElement(T e) {
Node current = head;
Node previous = head;
int position = 0;
while(current !=null && current.getElement() != e) {
previous = current;
current = current.getNext();
position++;
}
if(current == null) {
return null;
}else {
if(head == current) {
head = current.getNext();
}else if(tail == current) {
tail = previous;
tail.setNext(null);
}else {
previous.setNext(current.getNext());
}
System.out.println("Found & removed node at position " + position);
size--;
return current.getElement();
}
}

We begin by initializing two pointers which start at the head. As we walk through our list, we keep checking if the node has the same element we’re looking for. If so, we stop and remove this element from the list. If not, we continue until the end and return a “null”.

Conclusion

Knowing how to work with a Java Linked List is extremely important for a software engineer. You can implement many crucial data structures with a linked list such as a stack or queue. We will be seeing those in a separate tutorial, but I hope you’ve learned the basics of how to build a linked list in java today.

We also covered two important problems which you may encounters during your interviews. The first one is how to reverse a list and the second one is being able to find an element and remove it if found.

Link to FULL SOFTWARE: Click Here

Thank you for reading & watching,
– EEEnthusiast

Leave a Reply

Your email address will not be published.

CommentLuv badge