Lists
Table of Contents
1. Lists
When we work with arrays, we are stuck with the amount of space we get on initialization. If we want to extend it to fit more variables, we must use a list. Specifically, we would like our list to have the following features:
| Feature | IntList |
SLList |
DLList |
AList |
|---|---|---|---|---|
| Dynamic | ✅ | ✅ | ✅ | ✅ |
| Bureaucratic | ❌ | ✅ | ✅ | ✅ |
| Access-controlled | ❌ | ✅ | ✅ | ✅ |
| Fast size access | ❌ | ✅ | ✅ | ✅ |
| No null pointers | ❌ | ✅ | ✅ | ✅ |
| Generic types | ❌ | ✅ | ✅ | ✅ |
| Fast start access | ✅ | ✅ | ✅ | ✅ |
| Fast middle access | ❌ | ❌ | ❌ | ✅ |
| Fast end access | ❌ | ❌ | ✅ | ✅ |
| Fast insert everywhere | ❌ | ❌ | ✅ | ❌ |
1.1. IntList
We can construct a very basic linked list of integers:
public class IntList {
int first;
IntList rest;
public IntList(int first, IntList rest) {
this.first = first;
this.rest = rest;
}
/** Return the number of ints in this list. */
public int size() {
if (rest == null) {
return 1;
}
return rest.size() + 1;
}
/** Returns the int at index i. */
public int get(int i) {
if (i == 0) {
return this.first;
}
return rest.get(i - 1);
}
public static void main() {
IntList myList = new IntList(67, null);
myList.rest = new IntList(6, null);
myList.rest = new IntList(7, null);
}
}
The implementation of an IntList is simple, but apart from being dynamically sized, it doesn’t really have any of the features we want in our dynamic list. Let’s solve some of these problems in SLList, a more advanced version of this linked list.
1.2. SLList
1.2.1. Generics
A glaring problem of IntList is that it only stores integers. To solve this, we can use generics:
public class SLList<T> {
// -- snip --
public SLList(T first) {
// -- snip --
}
// -- snip --
}
1.2.2. Access Control
The next problem of IntList is that it exposes too much of its own interface to the user, which may cause problems. For example, IntList allows the user to manually go in and edit pointers to nodes of the linked list. To prevent this, we use the private access control and a nested class to hide this logic from the user:
public class SLList<T> {
private class Node {
T item;
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
// -- snip --
public SLList(T first) {
// -- snip --
}
// -- snip --
}
1.2.3. Sentinel Node
In IntList, we had to deal with the edge case that the first node might be null. This is very annoying, and we can solve this by introducing a sentinel node. We don’t care what value the sentinel node holds (it is technically not “part” of our list), but it allows the first node to never be null. The sentinel node would then point to the first node in our list:
public class SLList<T> {
private class Node {
T item;
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
private Node sentinel;
public SLList() {
sentinel = new Node(null, null);
}
public SLList(T first) {
sentinel = new Node(null, null);
sentinel.next = new Node(first, null);
}
// -- snip --
}
1.2.4. Bureaucracy and Caching Size
IntList also depends on the user to extend the list by modifying the pointers. We can use bureaucracy to make this easier by defining some convenient methods. Additionally, we can cache the value of size so we don’t have to recompute it every time:
public class SLList<T> {
// -- snip --
private Node sentinel;
private int size;
// -- snip --
/** Adds x to the front of this list. */
public void addFirst(T x) {
size += 1;
sentinel.next = new Node(x, sentinel.next);
}
/** Adds x to the end of this list. */
public void addLast(T x) {
size += 1;
Node current = sentinel;
while (current.next != null) {
current = current.next;
}
current.next = new Node(x, null);
}
private T get(Node node, int i) {
if (i == 0) {
return node.item;
}
return get(node.next, i - 1);
}
/** Return the int at index i in the list. */
public T get(int i) {
return get(sentinel.next, i);
}
/** Returns the number of items in the list. */
public int size() {
return size;
}
}
1.2.5. Implementation
The final implementation puts together all of our improvements above:
public class SLList<T> {
private class Node {
T item;
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
private Node sentinel;
private int size;
public SLList() {
sentinel = new Node(null, null);
size = 0;
}
public SLList(T first) {
sentinel = new Node(null, null);
sentinel.next = new Node(first, null);
size = 1;
}
/** Adds x to the front of this list. */
public void addFirst(T x) {
size += 1;
sentinel.next = new Node(x, sentinel.next);
}
/** Adds x to the end of this list. */
public void addLast(T x) {
size += 1;
Node current = sentinel;
while (current.next != null) {
current = current.next;
}
current.next = new Node(x, null);
}
private T get(Node node, int i) {
if (i == 0) {
return node.item;
}
return get(node.next, i - 1);
}
/** Return the int at index i in the list. */
public T get(int i) {
return get(sentinel.next, i);
}
/** Returns the number of items in the list. */
public int size() {
return size;
}
}
And these are our features:
| Feature | Solution |
|---|---|
| Dynamic | Linked list |
| Bureaucratic | Helper methods |
| Access-controlled | private and Node |
| Fast size access | Caching size |
| No null pointers | Sentinel nodes |
| Generic types | Generics |
| Fast start access | Forward links |
| Fast middle access | ❌ |
| Fast end access | ❌ |
| Fast insert everywhere | ❌ |
1.3. DLList
A doubly-linked list solves some of these problems. To solve the problem of reading or adding the end of the list, we can save a pointer last to the end of our list. However, removing from the end of the list is still a pain, because there is no way to retrieve the previous node. Therefore, a doubly-linked list also adds backwards links.
However, this approach also has a slightly annoying edge case, which is that last sometimes points at the sentinel node, and sometimes points at a “real” node. We can have two sentinels, one at the front and one at the back, and have last point to the back one, but that feels a bit too complex.
Instead, a better topology would be for the sentinel node to point to both the front and end of the list. sentinel.next would be the first “real” node of the list, whereas sentinel.prev would have the last node:
1.3.1. Implementation
public class DLList<T> {
private class Node {
public T value;
public Node prev;
public Node next;
public Node() {
this.value = null;
this.next = this;
this.prev = this;
}
public Node(T value) {
this.value = value;
this.next = this;
this.prev = this;
}
public void putBefore(Node next) {
this.next = next;
next.prev = this;
}
public void putAfter(Node prev) {
this.prev = prev;
prev.next = this;
}
}
private int size;
private final Node sentinel;
public DLList() {
this.size = 0;
this.sentinel = new Node();
}
public void addFirst(T x) {
Node add = new Node(x);
add.putBefore(sentinel.next);
add.putAfter(sentinel);
size++;
}
public void addLast(T x) {
Node add = new Node(x);
add.putAfter(sentinel.prev);
add.putBefore(sentinel);
size++;
}
public int size() {
return size;
}
public T getFirst() {
return sentinel.next.value;
}
public T getLast() {
return sentinel.prev.value;
}
public T get(int index) {
// guard for OOB get
if (index >= size || index < 0) {
return null;
}
Node ptr = sentinel.next;
while (index-- > 0) {
ptr = ptr.next;
}
return ptr.value;
}
}
And these are our features:
| Feature | Solution |
|---|---|
| Dynamic | Linked list |
| Bureaucratic | Helper methods |
| Access-controlled | private and Node |
| Fast size access | Caching size |
| No null pointers | Sentinel nodes |
| Generic types | Generics |
| Fast start access | Forward links |
| Fast middle access | ❌ |
| Fast end access | Reverse links |
| Fast insert everywhere | Reverse links |
1.4. AList
The final problem that remains to be solved is that it is still time consuming to do anything near the middle of the array, since we have to traverse the array from either end.
We can take advantage of the fact that retrieval from any position of an array is very fast (this is because memory boxes are the same size). Perhaps we can implement a list based on an array, called an array list or AList.
To do this, we can initialize a really large array, and bind each element in our list to that array. When we get to the end of the array, we can resize the array by creating a new array that is even bigger (double the size), and then copying over the elements from the first array to the new one.
But then we also want our array to be space efficient: when we remove a lot of the items, we would also like our array to shrink in size. We can set objects to null when they are removed, so that Java’s garbage collector can reduce memory for us.
public class AList<T> {
private T[] items;
private int size;
public AList() {
items = (T[]) new Object[999];
size = 0;
}
private void resize(int capacity) {
T[] resized = (T[]) new Object[capacity];
for (int i = 0; i < size; i++) {
resized[i] = items[i];
}
items = resized;
}
public void addLast(T x) {
if (size == items.length) {
resize(size * 2);
}
items[size] = x;
size += 1;
}
public T get(int i) {
return items[i];
}
public int size() {
return size;
}
public T removeLast() {
T returnItem = getLast();
items[size - 1] = null;
size -= 1;
return returnItem;
}
}
Linked lists are still better than array lists for operations at the beginning of the array. Theoretically, if we wish to insert at the start, we would have to shift all of the elements back in the array.