Linked Lists In Java
--------------------
Linked lists are one of the classic data structures in computer science. A linked list consists of some number of nodes, where each node stores a value and a pointer (reference) to the subsequent node in the list. The last node in the list points to null. We maintain a reference to the beginning of the list (this is normally named "head" or "front" or "top"). From this single point of reference, we can walk along the list, moving from each node to the next. If the list does not contain any nodes at all, then head is equal to null.
Pictorially, we might represent a linked list of integers as follows:
head -> 1 -> 2 -> 3 -> 4 -> \ (null)
The first node in the list stores the integer value 1 (head is only a reference to that first node; it isn't a node itself). The second node stores 2, and so forth. The last node in the list stores the value 4, and points to null.
A typical representation of a list node might look like the following:
class ListNode
{
public int value; // Stores a value for this node
public ListNode next; // Stores a reference to the next node in the list
}
Using this definition, our head reference is of type ListNode:
ListNode head = null; // The list is empty to begin with
Typically, the definition of the ListNode class, along with head, would be defined in a class that would manage our linked list. We'll assume that all of the code in this document is contained in such a class. Thus, the insert() method that we're about to define is a method belonging to our ListManager class.
To insert a value into our linked list, we have to determine where to insert the new node. We can insert new nodes at the beginning or end of a list, or in the middle. We may also need to do different things if the list is empty to begin with.
Insertion at the beginning of a list:
public void insertAtFront(int val)
{
ListNode temp = new ListNode();
temp.value = val;
// Add the new node to the front of the list.
// The new node points to the old value of head,
// and head now points to the new node.
temp.next = head;
head = temp;
}
Pictorially:
head -> 1 -> 2 -> 3 -> ...
newNode
head -> 1 -> 2 -> 3 -> ...
newNode/
head -> newNode -> 1 -> 2 -> 3 -> ...
Note that order matters here! If we reassign head first, we will lose the rest of the list. We need to "splice" the new node into the existing chain before we reassign head. Put another way, we always work backward, working our way from the new node back toward the head of the list.
Insertion at the end of a list means that we need to traverse the list, using a temporary pointer, until we reach the last node in the list (the one whose next value is null). We need to check for the special case of an empty list.
public void insertAtEnd(int val)
{
ListNode temp = new ListNode();
temp.value = val;
if (head == null)
{
// The list is empty, so temp becomes the entire list
temp.next = null;
head = temp;
}
else
{
// Traverse the list until we find the last node
ListNode traveller = head;
while (traveller.next != null)
traveller = traveller.next; // Go to the next node
// Add the new node to the end of the list
traveller.next = temp;
temp.next = null;
}
}
Pictorially:
head -> 1 -> 2 -> 3 -> \
newNode
traveller\
head -> 1 -> 2 -> 3 -> \
newNode
traveller\
head -> 1 -> 2 -> 3 -> \
newNode/
head -> 1 -> 2 -> 3 -> newNode -> \
Insertion in the middle of a list is similar to insertion at the end. The difference is that your list-traversal loop will iterate only a few times instead of until you reach the end. At that point, you want to link the new node to the rest of the list BEFORE adding the new node to the list; otherwise, you'll lost the rest of the old list:
public void insertAtPosition(int val, int pos)
{
// We assume that the list has at least pos nodes
ListNode temp = new ListNode();
temp.value = val;
if (head == null)
{
// The list is empty, so temp becomes the entire list
temp.next = null;
head = temp;
}
else
{
// Traverse the list until we find the last node
ListNode traveller = head;
for (int i = 1; i < pos; i++)
traveller = traveller.next; // Go to the next node
// Add the new node to the end of the list
temp.next = traveller.next;
traveller.next = temp;
}
}
Pictorially:
head -> 1 -> 2 -> 3 -> ...
newNode
traveller\
head -> 1 -> 2 -> 3 -> ...
newNode
traveller\
head -> 1 -> 2 -> 3 -> ...
newNode/
head -> 1 -> 2 -> newNode -> 3 -> ...
When deleting a node from a linked list, we need to be careful. Otherwise, we could lose our only reference to the part of the list that follows the node we're deleting. In general, when we delete from a list, we want to stop at the node BEFORE the one we want to delete. This is because in a normal linked list, it's easy to go forward, but not to go backward (to the previous node). Basically, we want to connect the previous node to the following node, thus cutting the target node out of the linked list.
Deleting from the beginning of a linked list:
public void deleteFromBeginning()
{
if (head != null)
{
// Make sure the list has at least one node to delete
head = head.next;
}
}
Pictorially:
head -> 1 -> 2 -> 3 -> ...
-----\
head / 1 -> 2 -> 3 -> ...
head -> 2 -> 3 -> ...
Deleting from the end of a linked list:
public void deleteFromEnd()
{
// Make sure that the list has at least one node
if (head != null)
{
// Traverse a list until we find the node BEFORE the last one.
// This means that we need to deal with the special case of a list
// with only one node.
if (head.next == null)
{
// Special case: only one node in the list
head = head.next;
}
else
{
ListNode prev = head;
while ((prev.next).next != null)
prev = prev.next;
prev.next = null;
}
}
}
Pictorially:
head -> 1 -> 2 -> 3 -> \
traveller\
head -> 1 -> 2 -> 3 -> \
traveller\
head -> 1 -> 2 3 -> \
\-------/
head -> 1 -> 2 -> \
We'll do something similar for deleting in the middle of a linked list. As with inserting a node, make sure that you connect prev.next to the ListNode pointed to by the target node's next pointer:
prev.next = (prev.next).next;
Pictorially:
head -> 1 -> 2 -> 3 -> ...
traveller\
head -> 1 -> 2 -> 3 -> ...
traveller\
head -> 1 -> 2 -> 3 -> ...
\-------/
head -> 1 -> 3 -> newNode -> ...
Insertion and deletion are the most complicated operations that you'll need to perform on a linked list. Almost all of the remaining operations that you'll perform on a linked list involve traversal (moving from one node to the next). This is as simple as creating a ListNode reference, setting it equal to the head, and repeatedly setting it to its own next field:
ListNode traveller = head;
traveller = traveller.next; // set traveller to point to the next node
In this fashion, the traveller reference moves from one list node to the next. We illustrated this in class when we counted the number of nodes in a linked list:
int count = 0;
traveller = head;
while (traveller != null)
{
// Count another node
count++;
traveller = traveller.next;
}
Pictorially:
head -> 1 -> 2 -> 3 -> \
traveller\
head -> 1 -> 2 -> 3 -> \
traveller\
head -> 1 -> 2 -> 3 -> \
traveller\
head -> 1 -> 2 -> 3 -> \
traveller\
head -> 1 -> 2 -> 3 -> \
We can also do this recursively. Our base case is an empty (null) reference, which has 0 nodes:
public int countNodes (ListNode head)
{
if (head == null) // base case
return 0;
else // recursive case
return 1 + countNodes(head.next);
}
To print out the values of the nodes in a linked list, we can use a loop:
public void printList(ListNode head)
{
ListNode traveller = head;
while (traveller != null)
{
// Print out the next list node
System.out.println(traveller.value);
// Move to the next node
traveller = traveller.next;
}
}
We can also do it recursively:
public void recursivePrint(ListNode head)
{
if (head == null) // base case -- do nothing
return;
else // recursive case
{
System.out.println(head.value);
recursivePrint(head.next);
}
}
This was a quick summary, but it explains the three basic operations that you'll be called upon to perform when dealing with linked lists: insertion, deletion, and list traversal.