linked_lists.md

Linked Lists

Overview

One way to represent a sequence of items is an array. Another is a linked list, which is a chain of Node objects, each of which contains one item and a reference to the next Node.

If you have defined the Node class as

class Node {
    int item;
    Node next;
}

then the list in the diagram above could be created by the following code:

Node a = new Node();
a.item = 5;
Node b = new Node();
b.item = 2;
Node c = new Node();
c.item = 3;
a.next = b;
b.next = c;
Node list = a;

(The temporary variables a, b, and c are not shown in the diagram.) Note that c's next instance variable is left at its default value of null. The value null is also used to represent an empty linked list (one containing no items).

A linked list is a recursive data structure, in that a linked list is either:

• empty (represented as null), or
• an item and a reference to another linked list.

Methods operating on lists tend to either be recursive, taking advantage of this structure, or iterative, walking down the chain of next references. For example, here are two ways to find the sum of the numbers in a list:

static int recursiveSum(Node list) {
    if (list == null) {
        return 0;
    }
    return list.item + recursiveSum(list.next);
}

static int iterativeSum(Node list) {
    int sum = 0;
    for (Node n = list; n != null; n = n.next) {
        sum += n.item;
    }
    return sum;
}

Resources

Note: many sources, including other parts of the Drakepedia, discuss linked lists in the context of more complex objects.

• Sedgewick and Wayne, Introduction to Programming in Java, Section 4.3
• Horstmann, Core Java, Volume I: Fundamentals, 11th Edition, Section 9.3.1
• Cormen et al., Introduction to Algorithms, 3rd Edition, Section 10.2

Questions

1. ⭐ Write a Node class for building linked lists of doubles.
2. ⭐ Name an advantage linked lists have over arrays.
3. ⭐ What is the value of the next instance variable in the last Node in a linked list?
4. ⭐⭐ The method below is supposed to determine the length of a linked list, but it contains an off-by-one error. How should it be fixed?

   static int length(Node list) {
       int result = 0;
       for (Node n = list.next; n != null; n = n.next) {
           result++;
       }
       return result;
   }

Answers

1. class Node {
       double item;
       Node next;
   }

2. A linked list can grow longer or shorter. An array must have its length specified when it is created.
3. null.
4. n should start at list, not list.next.