9.2. Linked Lists part I¶
9.2.1. Nodes¶
In this module we present one of the two traditional implementations for lists, usually called a linked list. The following diagram illustrates the linked list concept. Here there are three nodes that are “linked” together. Each node has two boxes. The box on the right holds a link to the next node in the list. Notice that the rightmost node has a diagonal slash through its link box, signifying that there is no link coming out of this box.
Because a list node is a distinct object (as opposed to simply a cell
in an array), it is good practice to make a separate list node class.
(We can also re-use the list node class to implement linked
implementations for the stack and
queue data structures.)
Here is an implementation for list nodes, called the Node class.
Objects in the Node class contain an data field to
store the element value, and a next field to store a pointer to
the next node on the list.
The list built from such nodes is called a singly linked list,
or a one-way list, because each list node
has a single pointer to the next node on the list.
class Node<E> {
private E value; // Value for this node
private Node<E> next; // Point to next node in list
// Constructor
public Node(E element) {
value = element;
next = null;
}
// Return the value held in Node
E getValue() {
return value;
}
// set value held in Node
void setValue(E newVal) {
value = newVal;
}
// Return next Node
Node<E> getNext() {
return next;
}
// Set next Node
void setNext(Node<E> nextNode) {
next = nextNode;
}
}
The Node class holds two pieces of information: the value of the node, and a pointer to the next node in the list.
Now, let’s take a conceptual look at a LinkedList. We’ll start with a simple LinkedList that doesn’t have a header or trailer node:
9.2.2. Linked List Partial Implementation¶
Now let’s look at a (partial) implementation for the linked list class,
named MHCLinkedList. This implementation only includes the methods for adding nodes to the list.
Note
We’ll discuss the rest of the implementation over the next few classes!
public class MHCLinkedList<E> implements MHCList<E> {
private Node<E> head = null;
private Node<E> tail = null;
private int numElements = 0;
// Adds to the beginning of the list.
private void addFirst(E value) {
// Create a new node with the value
Node<E> newHead = new Node<E>(value);
// Point the new node to the old head
newHead.setNext(head);
// Update the head to be the new node
head = newHead;
// If the list was empty,
// the new node is also the tail
if (tail == null) {
tail = head;
}
numElements++;
}
// Adds element after the specified Node.
private void addAfter(Node<E> targetNode, E value) {
// Create a new node with the value
Node<E> newNode = new Node<E>(value);
// Point the new node to the next node
newNode.setNext(targetNode.getNext());
// Point the current node to the new node
targetNode.setNext(newNode);
// If the current node is the tail,
// update the tail to be the new node
if (tail == targetNode) {
tail = newNode;
}
numElements++;
}
// Find and return the node at the specified index.
public Node<E> getNode(int index) {
if (index < 0 || index >= numElements) {
throw new IndexOutOfBoundsException(index);
}
Node<E> nextNode = head;
for (int i = 0; i < index; i++) {
nextNode = nextNode.getNext();
}
return nextNode;
}
// Inserts the specified element at the specified position in this list.
public void add(int index, E value) {
if (index < 0 || index >= numElements) {
throw new IndexOutOfBoundsException(index);
}
// adding at index 0 is addFirst()
if (index == 0) {
addFirst (value);
}
// otherwise call addAfter() on index-1 node
else {
Node<E> prevNode = getNode(index-1);
addAfter (prevNode, value);
}
}
}
9.2.3. Linked List Instance Variables¶
9.2.4. addFirst() and addAfter()¶
In order to get to implementing the add(int position, E element) method of the List interface, it is
useful to first think about how to add to the beginning of the list, and also how to add after a particular node:
9.2.5. Linked List Traversal and getNode()¶
Unlike ArrayLists, we don’t have direct access to elements at a specified index position. Instead, we have to traverse and walk down the Linked List to find the element at a position:
9.2.6. Linked List add(int position, E element)¶
Putting everything together, we can implement the List add(int position, E element) method:
// Inserts the specified element at the specified position in this list.
public void add(int index, E value) {
if (index < 0 || index >= numElements) {
throw new IndexOutOfBoundsException(index);
}
// adding at index 0 is addFirst()
if (index == 0) {
addFirst (value);
}
// otherwise call addAfter() on index-1 node
else {
Node<E> prevNode = getNode(index-1);
addAfter (prevNode, value);
}
}