Anatomy of a Linked List

Suppose that you want to store an indefinite amount of CISItem objects. You’d most likely pick an ArrayList over an Array (unless you’re a mad lad), and use the .add() method. You never have to worry about filling up the ArrayList because it can handle as many objects as necessary. Linked Lists work exactly the same way as an ArrayList, from the user’s perspective, but internally they are completely different. In fact if your changed your current CIS App code from

ArrayList<> someList = new ArrayList<>();

to this:

LinkedList<> someList = new LinkedList<>();

the rest of your code would need no changes. .add(), .remove(), .get() et al would work exactly the same.

I can already hear the calls of “then why are we using a Linked List?” and to that I would say, read the previous section since I’ve already explained myself 🙂

A Simple Dissection

Let’s finally look at a linked list and start by looking at the Node class. It’s quite simple, it contains two variables, data and next.

 private static class Node<T>
 {
        private T data;
        private Node<T> next;

        //constructor
        public Node(T data, Node<T> next)
        {
            this.data = data;
            this.next = next;
        }
  }

The variable data can hold anything that you’d like to store in the linked list. Say you create a LinkedList<String> to store a bunch of names of people, then each Node will hold one String in its data variable. Each time a new string is added to the Linked List, a new Node is created. What does the next variable do? This is a variable of type Node and it will hold a reference to the next Node in the Linked List. If there is no Node after it, then it will made next = Null. If you fail to connect the nodes correctly, your linked list is useless 🙁

A Quick Video Overview

Notice how we have a head in the LinkedList. This can be found in our implementation as

private Node<T> head;

This way we can keep track of the head as necessary.