LinkedLists and ArrayLists

 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.)