1. Overview
Data structures are important parts of any programming language. Java provides most of them under the Collection<T> interface. Maps are also considered part of Java collections, but they don’t implement this interface.
In this tutorial, we’ll concentrate on a linked list data structure. In particular, we’ll discuss removing the last element in a singly-linked list.
2. Singly-Linked vs Doubly-Linked Lists
First, let’s define the differences between singly-linked and doubly-linked lists. Luckily, their names are quite descriptive. Each node in a doubly-linked list has a reference to the next and the previous one, except, obviously, for the head and tail:
A singly-linked list has a simpler structure and contains only the information about the next node:
Based on the differences, we have a trade-off between these data structures. Singly-linked lists consume less space, as each node contains only one additional reference. At the same time, doubly-linked lists are more convenient for traversing nodes in reverse order. This might create problems not only when we iterate through the list but also for search, insert, and removal operations.
3. Removing the Last Element From Doubly-Linked Lists
Because a doubly-linked list contains information about its previous neighbor, the operation itself is trivial. We’ll take an example from Java standard LinkedList<T>. Let’s check the LinkedList.Node<E> first:
class Node<E> {
E item;
LinkedList.Node<E> next;
LinkedList.Node<E> prev;
Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
It’s quite simple, but as we can see, there are two references: next and prev. They simplify our work significantly:
The entire process takes only several lines of code and is done in constant time:
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
E element = l.item;
Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null) {
first = null;
} else {
prev.next = null;
}
size--;
modCount++;
return element;
}
4. Removing the Last Element From Singly-Linked Lists
The main challenge for removing the last element from a singly linked list is that we have to update the node that’s second to last. However, our nodes don’t have the references that go back:
public static class Node<T> {
private T element;
private Node<T> next;
public Node(T element) {
this.element = element;
}
}
Thus, we have to iterate all the way from the beginning just to identify the second to last node:
Linked lists singly linked list second to last
The code also would be a little bit more complex than for a doubly-linked list:
public void removeLast() {
if (isEmpty()) {
return;
} else if (size() == 1) {
tail = null;
head = null;
} else {
Node<S> secondToLast = null;
Node<S> last = head;
while (last.next != null) {
secondToLast = last;
last = last.next;
}
secondToLast.next = null;
}
--size;
}
As we have to iterate over the entire list, the operation takes linear time, which isn’t good if we plan to use our list as a queue. One of the optimization strategies is to store the secondToLast node alongside the head and tail:
public class SinglyLinkedList<S> {
private int size;
private Node<S> head = null;
private Node<S> tail = null;
// other methods
}
This won’t provide us with easy iteration, but it at least improves the removeLast() method, making it similar to the one we’ve seen for a doubly-linked list.
5. Conclusion
It’s not possible to divide data structures into good and bad. They’re just tools. Thus, each task requires a specific data structure to accomplish its goals.
Singly-linked lists have some performance issues with removing the last element and aren’t flexible on other operations, but at the same time, they consume less memory. Doubly-linked lists have no constraints, but we’re paying for this with more memory.
Understanding the underlying implementation of data structures is crucial and allows us to pick the best tool for our needs. As usual, all the code from this tutorial is available over on GitHub.
