3.4: Linked Data Structures

Last updated
Save as PDF

Page ID: 12739

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

For the next exercise I provide a partial implementation of the List interface that uses a linked list to store the elements. If you are not familiar with linked lists, you can read about them at thinkdast.com/linkedlist, but this section provides a brief introduction.

A data structure is “linked” if it is made up of objects, often called “nodes”, that contain references to other nodes. In a linked list, each node contains a reference to the next node in the list. Other linked structures include trees and graphs, in which nodes can contain references to more than one other node.

Here’s a class definition for a simple node:

public class ListNode {
    public Object data;
    public ListNode next;

    public ListNode() {
        this.data = null;
        this.next = null;
    }
    
    public ListNode(Object data) {
        this.data = data;
        this.next = null;
    }
    
    public ListNode(Object data, ListNode next) {
        this.data = data;
        this.next = next;
    }
    
    public String toString() {
        return "ListNode(" + data.toString() + ")";
    }
}

The ListNode object has two instance variables: data is a reference to some kind of Object, and next is a reference to the next node in the list. In the last node in the list, by convention, next is null.

ListNode provides several constructors, allowing you to provide values for data and next, or initialize them to the default value, null.

Object diagram of a linked list.

Figure \(\PageIndex{1}\): Object diagram of a linked list.

You can think of each ListNode as a list with a single element, but more generally, a list can contain any number of nodes. There are several ways to make a new list. A simple option is to create a set of ListNode objects, like this:

ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);

And then link them up, like this:

node1.next = node2;
node2.next = node3;
node3.next = null;

Alternatively, you can create a node and link it at the same time. For example, if you want to add a new node at the beginning of a list, you can do it like this:

ListNode node0 = new ListNode(0, node1);

After this sequence of instructions, we have four nodes containing the Integers 0, 1, 2, and 3 as data, linked up in increasing order. In the last node, the next field is null.

Figure \(\PageIndex{1}\) is an object diagram that shows these variables and the objects they refer to. In an object diagram, variables appear as names inside boxes, with arrows that show what they refer to. Objects appear as boxes with their type on the outside (like ListNode and Integer) and their instance variables on the inside.