9.2. Linked Lists¶
9.2.1. Nodes¶
In this module we present one of the two traditional implementations for lists, usually called a linked list. The linked list uses dynamic memory allocation, that is, it allocates memory for new list elements as needed. 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 data; // Value for this node
private Node<E> next; // Point to next node in list
// Constructors
public Node(E element, Node<E> nextNode) {
data = element;
next = nextNode;
}
public Node(E element) {
data = element;
next = null;
}
// Return the value held in Node
E getValue() {
return data;
}
// set value held in Node
void setValue(E newData) {
data = newData;
}
// Return next Node
Node<E> getNext() {
return next;
}
// Set next Node
void setNext(Node<E> nextNode) {
next = nextNode;
}
}
The Node class is quite simple.
There are two forms for its constructor, one with
an initial element value and one without.
Methods allow the Node user to get or set the data
and next fields.
Now, let’s take a conceptual look at a LinkedList:
9.2.2. Linked List Partial Implementation¶
Now let’s look at a (partial) implementation for the linked list class,
named MHCLinkedList.
Note
We’ll go over the rest of the implementation in lecture and in Lab 5!
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) {
head = new Node<E>(value, head);
if (tail == null) {
tail = head;
}
numElements++;
}
// Adds element after the specified Node.
private void addAfter(Node<E> node, E value) {
Node<E> newNode = new Node<E>(value, node.getNext());
node.setNext(newNode);
if (tail == node) {
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);
}
}