The first data structure we’ll look at is the List. List is an interface in Java, so there are many implementations. We will focus on the two most commonly used, the ArrayList and the LinkedList.
An ArrayList can be thought of, essentially, as a self-resizing array. Regular
arrays are declared with the type of thing they’ll hold and how many they can
hold. ArrayList declarations look a little different:
List<Integer> myList = new ArrayList();
Remember from our discussion of inheritance a few posts ago
how this works, even if the class names aren’t the same. Every ArrayList is a
List, so this declaration is fine. (We would run into trouble if List and
ArrayList were reversed, since not every List is an ArrayList.) The use of “Integer”
here is both a generic and a wrapper class. For now, I’ll be handwavy about
this and say that, to create a list of integers, you use these and not the int
primitive type, but I promise I’ll address this very soon and link back to the
explanation as soon as it is posted.
Imagine a real list you’re making when you go shopping. There are certain
things you might want to do:
- Add or remove an item from the beginning
- Add or remove an item from somewhere in the middle
- Add or remove an item from the end
- Figure out how many items you have
- Figure out if you have any items at all
- Find out what the item at some position is
These are all things you can do thanks to the way List is
implemented.
There are methods to add(), remove(), and get(). Now, contrary to arrays—of the
int[] myArray = new int[20]; variety—the way to access the number of things in
a List is not with length (which is a property, so it really is length, and not
length()), is actually with the method call to size(). This, again, unlike
arrays, is an actual method call, so don’t forget the parentheses! Lists start
counting from index 0, just like arrays.
ArrayLists essentially hide from you the process of copying
arrays and adding in items whenever you exceed the maximum allocated space.
LinkedLists, however, are a little different. Whereas arrays took some fixed
chunk of memory (let’s say, 80 bytes to store 20 integers at 4 bytes each) and
found a chunk of unused memory of that size, all in sequence, LinkedLists don’t
care about that consecutive memory constraint.
There are generally two types of LinkedLists: singly-linked, and doubly-linked.
Your browser is probably implementing a doubly-linked list, since you can go
backward in a tab and you can go forward: there are links to the previous
thing, and to the next thing, as opposed to links in only one direction.
Typically, you’ll probably see LinkedLists made of Nodes (again, with those
angle-brackets we’ll discuss very shortly), looking something like this:
// Node class
class Node<T> {
T data;
Node<T>
next;
Node(T data) {
this.data =
data;
this.next =
null;
}
}
// LinkedList class
class LinkedList<T> {
Node<T>
head;
// Add a new node
at the end
void add(T data) {
Node<T>
newNode = new Node<>(data);
if (head ==
null) {
head =
newNode;
} else {
Node<T> current = head;
while
(current.next != null) {
current = current.next;
}
current.next = newNode;
}
}
// Print all nodes
void printList() {
Node<T>
current = head;
while (current
!= null) {
System.out.print(current.data + " ");
current =
current.next;
}
System.out.println();
}
}
// Example usage
public class Main {
public static void
main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.printList(); // Output: 1 2 3
}
}
A “Node” object has two things in it: a piece of data of type T, and a pointer
to the next node in the list. It does not matter where in memory that is, and,
say, the item at index 3 need not be earlier in memory than the item at index
327. As long as there’s a pointer from 3 to 4 to 5 to 6… to 325 to 326 to 327—as
long as you can follow the trail of breadcrumbs left by those “next” Node objects—you
can find your way around a list. (If the list were doubly-linked, you would
have your payload, plus links to both “next” and “prev” Nodes.)
