8.1. Introduction to Linked Lists

Up until this point, you’ve likely stored collections of data of the same datatype in an array. Arrays allow you to use a single name to refer to multiple values along with a way to quickly and easily access the items in the array. In this section, we will introduce you to an important alternative to arrays called linked lists. Software developers often find themselves faced with the decision of whether to use an array or a linked list to store the data required for their application. Ultimately, the decision comes down to which one will perform better (run faster, use less memory). Neither data structure is universally better. It always depends on the application at hand.

A linked list is a sequence of objects where one object in the list references the next object in the list. The objects are not laid out in contiguous memory and, therefore, it takes more time to access the items in the list than it does in an array-based implementation. However, they can easily grow without the need to copy all existing items. We will elaborate on these ideas soon, but for now understand that there is a performance trade-off.

Important

Linked Lists are alternatives to arrays. Some applications will work more efficiently if a linked list is used and others will perform better with an array.

The objects in a linked list are commonly referred to as nodes. Each node contains the value to be stored along with a reference to the next node in the list. An abbreviated Java implementation of a Node class containing a String reference can be seen below:

public class Node {

   private String value;
   private Node next;

   // constructors, getters and setters omitted for brevity

} // Node

Wait, the Node class has an instance variable of type Node?!? Yes, it seems strange at first. However, the next instance variable (of type Node) is just a reference (or link) to the next Node object in the linked list. Executing the code below would generate two Node objects and connect them with a reference.

The next reference contained within the first node, n, references the second Node object.
Node n = new Node("Hello");
n.setNext(new Node("World"));

Test Yourself

Draw the memory map for the two lines above. Note how many objects are created. Draw those along with the instance variables contained in each. Then, write the values for each instance variable along with the local variable, n.

Test Yourself Solution (Open after answering the question above)

The memory map would look something like this:

Two connected nodes

Thought Exercise

Take a moment to think about the sequence of nodes above. There are two objects connected by a reference from the first to the second object. Draw a String array called n with two elements. Then, write Hello in the first index and World in the second index.

How is this similar to the linked list above? Both contain two string values and they are referenced by a variable called n. Since they both store the same information and provide the same functionality, we say that a linked list is an alternative to an array with its own benefits and drawbacks.

Now, imagine you are writing an application that allows users to add items to a grocery list. At this point in your studies, you would likely choose an array (first image below) to store the data. However, you could also choose a linked list (second image below).

../../_images/IntroArray.png

If we use an array to hold our items, we may need to allocate more space than we need in order to avoid creating new arrays each time we add a new item.
../../_images/IntroLinkedList.png

If we use a linked list to hold our items, we can connect new objects to existing objects without having to recreate the entire list since each object refers to the next object in the list.

Important

A linked list is not a Node. Instead, it is a sequence of connected nodes - each of which is a separate object. Typically, a linked list object contains a Node reference to the head (front) of the list along with a size variable indicating how many items are in the list. Linking together Node objects is an alternative way to store related data items.

In the following sections, we will show how both arrays and linked lists can be used to implement the methods in the List ADT. We will also discuss the benefits and drawbacks of each approach.

Rapid Fire Review

  1. What is a linked list?

    1. A collection of data stored in contiguous memory locations.

    2. A sequence of objects where each object references the next.

    3. A type of array where elements are accessed randomly.

    4. A data structure that performs better in all situations than an array.

  2. What does the next instance variable in a Node object do?

    1. Stores the value of the Node.

    2. Links to the previous Node in the sequence.

    3. Links to the next Node in the linked list.

    4. Stores the index of the Node in an array.

  3. Which of the following statements best describes a primary advantage of using a linked list over an array?

    1. Linked lists are stored in contiguous memory, making access to elements faster.

    2. Linked lists are easier to search than arrays.

    3. Linked lists can grow dynamically without the need to reallocate memory.

    4. Linked lists can only store string data types.

  4. Why is a linked list considered an alternative to an array?

    1. Linked lists and arrays have identical performance characteristics.

    2. Both store collections of data but handle memory allocation and access differently.

    3. Linked lists are always faster than arrays.

    4. Arrays can only hold integer values while linked lists can hold any data type.