Making a sublist

A sublist is a second list built out of part of a first one. Before you write a line, answer one question, because it decides everything else: does the original keep those values?

If the original keeps them, you are copying values, so you build new nodes and the original is untouched at the end. If the original gives them up, you are moving nodes, so you build nothing and you rewrite a small number of arrows. Getting this backward is not a small bug. Copy when you were meant to move and the values are in both lists at once, so a later change to one shows up in the other. Move when you were meant to copy and the original is short values it was supposed to keep.

Moving nodes: the cut

Cutting a list at a position means the front part stays where it is and the back part becomes a new list. No node is created and no node is destroyed. Two arrows change, and 2 counts.

before:  head -> [a] -> [b] -> [c] -> [d] -> null      size 4

splitAfter("b"):

after:   head -> [a] -> [b] -> null                    size 2
         other.head -> [c] -> [d] -> null              size 2

Work backward from the after picture. The node holding b used to point at c and now points at null. Something in the new list now points at c. Both sizes changed. That is 4 named changes and 4 lines of code.

The method below finds the cut point by value. splitAfter(Object target) finds the first node whose data equals target. Every node after that one moves into a new list, which the method returns. When no node holds target, or target is in the last node, it returns an empty list. In both of those cases this list keeps its size, and the returned list has size 0.

public LinkedList splitAfter(Object target)
{
    LinkedList other = new LinkedList();
    Node cur = this.head;
    int kept = 1;                        // nodes this list keeps, cur included
    while (cur != null && !cur.data.equals(target))
    {
        cur = cur.next;
        kept++;
    }
    if (cur == null)
    {
        return other;                    // no match, so nothing moves
    }
    other.head = cur.next;               // copy the pointer first
    cur.next = null;                     // then sever
    other.size = this.size - kept;
    this.size = kept;
    return other;
}

Four things in there are worth naming.

Build the list you will return at the very top. Then every path out of the method hands back a real object, and the cases where it comes back empty need no extra thought. A method that returns null to mean nothing moved hands the caller a landmine, because the caller then prints it or asks it for its size and gets a NullPointerException instead of an empty list.

Copy the pointer before you sever. other.head = cur.next has to run before cur.next = null, because after the sever there is nothing left that remembers where the second half was. Aim before you break, the same rule as every other rewiring on this site.

The sever is not optional. Skip it and the front list's last kept node still points at the first node you gave away, so both lists walk through the same nodes. Printing the first list walks straight into the second one and prints values it no longer owns, and the size on the first line disagrees with the lines under it.

A missing target needs its own branch. When no node matches, the walk ends with cur at null. There is no node to sever after, so the method returns the empty list before it reads cur.next. The head of this list never moves, because the node that matches always stays in this list.

A target in the last node needs no branch at all, which is worth walking through because it looks like it should. The walk stops on the last node, whose next is already null. The copy puts null into the new list's head, and the sever writes null over a null. The new size comes out 0, and the old size comes out the size it already was. That is the right answer, produced by the ordinary path.

Copying values: the sublist by criterion

Now the rule is not a position, it is a question you ask each value. Every value over 100. Every name that starts with a letter. Every record whose field matches. Walk the original, ask the question, and when the answer is yes, put a copy of the value into the new list. The original is never touched, so its size never moves.

The only hard part is putting values into the new list in order. Reaching for addFirst is the trap, because it pushes each value on the front, so the new list comes out reversed. Walking the new list to its end for every value is the other trap, because then a list of n values costs a full walk each time.

Keep a second cursor on the end of the list you are building. One attach and one step per value, and nothing is ever re-walked.

public LinkedList over(int limit)
{
    LinkedList out = new LinkedList();
    Node tail = null;                  // the last node of the new list
    Node cur = this.head;
    while (cur != null)
    {
        if (((Integer) cur.data).intValue() > limit)
        {
            Node fresh = new Node(cur.data, null);
            if (tail == null)
            {
                out.head = fresh;      // the first one that matched
            }
            else
            {
                tail.next = fresh;
            }
            tail = fresh;
            out.size++;
        }
        cur = cur.next;
    }
    return out;
}

The tail == null branch is the front case again, wearing different clothes: the first matching value has no node in front of it in the new list, so it has to become the head. Give the new list a sentinel and that branch goes away, which is one more place the extra node earns its keep.

Notice what the new nodes hold. new Node(cur.data, null) copies the reference to the value, not the value itself, so both lists point at the same objects. For strings and numbers that never matters, because nothing can change them. For an object with fields somebody can set, it matters a lot, and if the specification says the 2 lists have to be independent you have to copy the object as well as the reference.

Copying a whole list

A copy of a linked list either shares the original's nodes or has nodes of its own.

A shallow copy takes 2 lines:

other.head = this.head;
other.size = this.size;

After those 2 lines, both lists start at the same first node. The table shows what a test sees on the list a b c after each kind of copy, and after the original unlinks its second node.

The shallow copy lost b through a change it never made, and its size no longer matches its printout. A deep copy walks the original once and builds 1 new node per value, in the same order, linked only to each other. The data objects stay shared, as in the copying sublist above, because new Node(cur.data, null) copies the reference to the value.

In the practice APE

The cutList problem in Practice exam 2 and the clone problem in Practice exam 1 use this lesson. Each file's header comment is the specification.

Trace the ordinary case of splitAfter. The list holds first second third four five six seven eight nine ten and the call is splitAfter("four").

What the list you keep prints:

List size is: 4
first
second
third
four

And the list you hand back:

List size is: 6
five
six
seven
eight
nine
ten

Readiness check

The one thing to keep

Decide first whether the original keeps its values. Moving nodes means copying the pointer before you sever, severing so the 2 lists cannot see each other, and fixing both sizes. Copying values means building new nodes and leaving the original alone, with a tail cursor so each match is one attach and one step rather than a fresh walk. A missing target is the branch, and a target in the last node needs no branch at all.