1. Reference Guide (On your own)

Term Definition / Example Requirement
Node One message in the history. It holds a value and a next reference: new Node("A") CS113 outline II.B Linked lists
head The reference to the first node. When head is null, the list is empty. CS113 outline II.B Linked lists
next The reference inside a node that points to the node after it. The last node’s next is null. CS113 outline II.B Linked lists
Traversal Walking from head along each next until you reach null: for (Node n = head; n != null; n = n.next) CS113 outline II.B Linked lists
Unlink Deleting a node by changing the next of the node before it, so the list skips the target. The target is no longer reachable from head. CS113 outline II.B Linked lists
Soft delete (tombstone) Keeping the node in the list, marking it deleted, and showing a placeholder in its place. OCS deletes DMs this way. CS113 outline II.B Linked lists. Source: DirectMessageService.deleteMessage
Skipping bug A removal that skips a neighbor. Removing from an ArrayList with a forward loop skips the next element, and changing the wrong next in a linked list does the same. AP CSA 2021 Question 3, ClubMembers, which the Collectables Homework cites for removeStanding
  • Unlink removes the node. Soft delete keeps it. This lesson teaches both.
  • The full CS 113 outline is on the CS 113 page. This lesson sits under II.B Linked lists.
  • The AP walkthrough for the skipping bug is 2021 Q3.

2. Real-Life Application (In-Class)

Deleting a DM in OCS

Before you read the table: you delete a message in the middle of a chat. What has to stay the same for everyone else in that chat?

Here is what happens when you delete one of your own DMs in OCS:

What the user sees Which request is sent What the server does
You delete one of your own messages DELETE /api/dm/conversations/{id}/messages/{messageId} Finds the message by its ID, not by its position. Clears the body, sets deleted=true, and keeps the row.
The other people in the chat see a placeholder where the message was None from them. They listen over WebSocket. Sends a "deleted" event to /topic/dm/{conversationId}
You try to delete someone else’s message The same DELETE Throws SecurityException("Not the message sender"). Only the sender may delete, and the controller answers 403.
You delete the same message twice The same DELETE if (message.isDeleted()) return; so nothing changes and no new event is sent
You edit a message PATCH on the same path, not PUT Edits the body of your own message

The service’s own comment says why the row stays: “so the conversation’s order and read-state markers aren’t disturbed.”

The takeaway: unlinking a node is the textbook way to delete from a linked list. OCS doesn’t unlink, because it needs to keep the order and the read markers. You will learn both ways.

Source: DirectMessageApiController.deleteMessage and DirectMessageService.deleteMessage in the OCS spring backend.


3. Tech Talk (In-Class)

Learning Objective: Delete a node from a linked list by changing the right reference, and explain why OCS soft-deletes instead.

Success Criteria: You can find the node before the target, handle the head, tail and invalid indexes, and explain unlink vs. soft delete.

Think of a chat’s message history as a linked list. Each node is one message and points to the next one:

A → B → C → D

Deleting a message by position means removing one node. A request to delete the third message ends in delete(2). OCS itself deletes by message ID, because positions shift as soon as something is deleted.

Here is the starter delete(index). It has a bug: some inputs remove the wrong node and others crash.


// Starter code: delete the node at index
Node cur = head;
for (int i = 0; i < index; i++) {
    cur = cur.next;
}
cur.next = cur.next.next;
size--;

Two ways to delete

  Unlink Soft delete (OCS)
The node Leaves the list Stays in the list, marked deleted
size Goes down by 1 Stays the same
Later nodes Shift up one index Keep their places
Use it when The data is really gone The order and read markers must not move

Code Examples (On your own)

A. A working history. The HistoryList class has add and show, and no delete

add walks to the end of the list and links a new node. show walks from head and collects every value.

Terminology:

A traversal starts at head and follows next until it reaches null. Every method you write in the hacks starts with one.


Code Runner Challenge

Run it, then predict what show() prints after one more add

View IPYNB Source
// CODE_RUNNER: Run it, then predict what show() prints after one more add
// A small working history: add puts a message at the end, show walks the list. There is no delete yet.
public class HistoryList {
    static class Node {
        String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    Node head;
    int size;

    // Add a message at the end of the history.
    void add(String value) {
        Node node = new Node(value);
        if (head == null) {
            head = node;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
        size++;
    }

    // Walk from head to the end and collect every value.
    String show() {
        StringBuilder sb = new StringBuilder();
        for (Node n = head; n != null; n = n.next) {
            if (sb.length() > 0) sb.append(",");
            sb.append(n.value);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        HistoryList history = new HistoryList();
        history.add("A");
        history.add("B");
        history.add("C");
        System.out.println("Before: " + history.show() + " size=" + history.size);

        // Try it: remove the // so one more message is added, but predict the output first.
        // history.add("D");
        System.out.println("After:  " + history.show() + " size=" + history.size);
    }
}

HistoryList.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Popcorn Hack (In-Class)

2-minute challenge: trace the starter delete(0) before you run it.

  1. On paper, draw A → B → C → D. Trace the starter delete(0) from the Tech Talk, one line at a time.
  2. Answer the question in the Popcorn checker under the runner before you run.
  3. Run the starter runner below and compare its output with your prediction.
  4. When the checker finishes, copy its line into your submission notes.

Do not fix the starter here. Fixing it is Homework Hack 1.

Code Runner Challenge

Run the starter delete(0) and compare its output with your prediction

View IPYNB Source
// CODE_RUNNER: Run the starter delete(0) and compare its output with your prediction
// The starter delete(index) has a bug. Do not fix it here: this runner only shows what it does.
public class StarterDelete {
    static class Node {
        String value;
        Node next;
        Node(String value) { this.value = value; }
    }

    Node head;
    int size;

    void add(String value) {
        Node node = new Node(value);
        if (head == null) {
            head = node;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
        size++;
    }

    // Starter code: delete the node at index
    void delete(int index) {
        Node cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }

    String show() {
        StringBuilder sb = new StringBuilder();
        for (Node n = head; n != null; n = n.next) {
            if (sb.length() > 0) sb.append(",");
            sb.append(n.value);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        StarterDelete history = new StarterDelete();
        history.add("A");
        history.add("B");
        history.add("C");
        history.add("D");
        System.out.println("Before: " + history.show() + " size=" + history.size);

        history.delete(0);
        System.out.println("After delete(0): " + history.show() + " size=" + history.size);
    }
}

StarterDelete.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Before you press Run, predict this output.

    Pass every check to finish the Popcorn Hack.

    4. MCQ Check (In-Class)

    4 questions, one at a time. Answer, check, then go to the next one. At the end, copy the score line into your submission notes.


    5. Homework Hacks (On your own)

    Task: Delete from a linked-list history three ways: fix the starter delete(index), delete by ID, then soft-delete the way OCS does. Each starter compiles before you edit it, so you can run the initial version and compare its FAIL lines with the expected results. Change only what the TODO asks for, and keep going until the last line reads ---- N / N passed ----.

    Copy these lines into your submission notes as you finish each part:

    
    Lesson: CS113 Linked List History Deletion
    MCQ History Deletion: <paste the copied score line, such as 2/4 | answers: A,A,A,A>
    Popcorn: <paste the Popcorn checker line>
    Homework Hack 1: ---- <N> / 12 passed ----
    Homework Hack 2: ---- <N> / 4 passed ----
    Homework Hack 3: ---- <N> / 4 passed ----
    

    Submission Safety Rules (Read First)

    • Each runner is a complete program ending with ClassName.main(null);. Run it and leave the output showing.
    • Do not change the tests below the Tests line.
    • Save each runner with its 💾 button before you submit.

    Hack 1: Fix delete(index) (10 minutes)

    Linked list deletion. The starter delete(index) from the Tech Talk is in the runner below, with 12 tests. Fix delete(index) so all 12 checks pass. The first 7 tests each start with a fresh list. The last 5 run several deletes on the same list.

    Test (fresh list each time) Expected after the fix
    A,B,C,D: delete 0 / 2 / 3 B,C,D / A,B,D / A,B,C
    A: delete 0 empty
    Index −1, or index ≥ size IndexOutOfBoundsException; list unchanged

    Code Runner Challenge

    Fix delete(index) until every check prints PASS

    View IPYNB Source
    // CODE_RUNNER: Fix delete(index) until every check prints PASS
    // delete(index) has a bug. Run the tests, read the FAIL lines, then fix delete() until you see 12 / 12 passed.
    import java.util.function.Supplier;
    
    public class HistoryDeletion {
        static class Node {
            String value;
            Node next;
            Node(String value) { this.value = value; }
        }
    
        Node head;
        int size;
    
        HistoryDeletion(String... values) {
            Node tail = null;
            for (String v : values) {
                Node n = new Node(v);
                if (head == null) head = n; else tail.next = n;
                tail = n;
                size++;
            }
        }
    
        // TODO: fix this method. It should remove the node at index.
        // An index below 0 or >= size must throw IndexOutOfBoundsException and leave the list unchanged.
        void delete(int index) {
            Node cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
            size--;
        }
    
        String show() {
            StringBuilder sb = new StringBuilder();
            for (Node n = head; n != null; n = n.next) {
                if (sb.length() > 0) sb.append(",");
                sb.append(n.value);
            }
            return sb.toString();
        }
    
        // ---- Tests: do not change below this line ----
        static String state(HistoryDeletion list) {
            return "[" + list.show() + "] size=" + list.size;
        }
    
        static String tryDelete(HistoryDeletion list, int index) {
            try {
                list.delete(index);
            } catch (IndexOutOfBoundsException e) {
                return "rejected " + state(list);
            } catch (RuntimeException e) {
                return "crash: " + e.getClass().getSimpleName();
            }
            return state(list);
        }
    
        static String afterDelete(int index, String... values) {
            return tryDelete(new HistoryDeletion(values), index);
        }
    
        public static void main(String[] args) {
            System.out.println("-- One delete on a fresh list --");
            Check.that("delete head", "[B,C,D] size=3", () -> afterDelete(0, "A", "B", "C", "D"));
            Check.that("delete middle", "[A,B,D] size=3", () -> afterDelete(2, "A", "B", "C", "D"));
            Check.that("delete tail", "[A,B,C] size=3", () -> afterDelete(3, "A", "B", "C", "D"));
            Check.that("delete only node", "[] size=0", () -> afterDelete(0, "A"));
            Check.that("negative index", "rejected [A,B] size=2", () -> afterDelete(-1, "A", "B"));
            Check.that("index = size", "rejected [A,B] size=2", () -> afterDelete(2, "A", "B"));
            Check.that("empty list", "rejected [] size=0", () -> afterDelete(0));
    
            System.out.println("-- Several deletes on the same list --");
            HistoryDeletion h = new HistoryDeletion("A", "B", "C", "D");
            Check.that("delete 0", "[B,C,D] size=3", () -> tryDelete(h, 0));
            Check.that("then delete 2 (uses new indexes)", "[B,C] size=2", () -> tryDelete(h, 2));
            Check.that("then delete 9", "rejected [B,C] size=2", () -> tryDelete(h, 9));
            tryDelete(h, 0);
            Check.that("delete until empty", "[] size=0", () -> tryDelete(h, 0));
            Check.that("delete from empty", "rejected [] size=0", () -> tryDelete(h, 0));
    
            Check.summary();
        }
    }
    
    // ---- Test helper (do not edit) ----
    class Check {
        private static int passed = 0;
        private static int total = 0;
    
        // An exception counts as a FAIL so one unfinished method does not stop the other checks.
        static void that(String label, String expected, Supplier<String> actual) {
            total++;
            try {
                String got = actual.get();
                if (expected.equals(got)) { passed++; System.out.println("PASS  " + label); }
                else System.out.println("FAIL  " + label + ": expected " + expected + ", got " + got);
            } catch (Exception e) {
                System.out.println("FAIL  " + label + "  (" + e + ")");
            }
        }
    
        static void summary() { System.out.println("---- " + passed + " / " + total + " passed ----"); }
    }
    
    HistoryDeletion.main(null);
    
    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Hack 2: deleteById(String id) (10 minutes)

    Search, then unlink. OCS deletes by ID too. Write deleteById so it searches for the node with this value, then unlinks it. Return true if it deleted a node, or false if the ID was not found, and in that case leave the list unchanged. This runner has add and show plus a deleteById stub. It has no delete(index), so write this one yourself.

    Test (fresh A,B,C,D unless noted) Expected
    deleteById("C") true, [A,B,D] size=3
    deleteById("A") (head) true, [B,C,D] size=3
    deleteById("Z") false, [A,B,C,D] size=4
    deleteById("A") on [] false, [] size=0

    Code Runner Challenge

    Write deleteById until every check prints PASS

    View IPYNB Source
    // CODE_RUNNER: Write deleteById until every check prints PASS
    // OCS deletes a DM by its ID, not by its position. Write the same idea for this list.
    import java.util.function.Supplier;
    
    public class DeleteById {
        static class Node {
            String value;
            Node next;
            Node(String value) { this.value = value; }
        }
    
        Node head;
        int size;
    
        void add(String value) {
            Node node = new Node(value);
            if (head == null) {
                head = node;
            } else {
                Node cur = head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
            size++;
        }
    
        // TODO: write deleteById. Search for the node whose value equals id, then unlink it.
        // Return true if a node was deleted, or false if id was not found (the list must stay unchanged).
        boolean deleteById(String id) {
            /* to be implemented */
            return false;
        }
    
        String show() {
            StringBuilder sb = new StringBuilder();
            for (Node n = head; n != null; n = n.next) {
                if (sb.length() > 0) sb.append(",");
                sb.append(n.value);
            }
            return sb.toString();
        }
    
        // ---- Tests: do not change below this line ----
        static String state(DeleteById list) {
            return "[" + list.show() + "] size=" + list.size;
        }
    
        static String afterDelete(String id, String... values) {
            DeleteById list = new DeleteById();
            for (String v : values) list.add(v);
            boolean deleted = list.deleteById(id);
            return deleted + " " + state(list);
        }
    
        public static void main(String[] args) {
            Check.that("delete a middle node by id", "true [A,B,D] size=3", () -> afterDelete("C", "A", "B", "C", "D"));
            Check.that("delete the head by id", "true [B,C,D] size=3", () -> afterDelete("A", "A", "B", "C", "D"));
            Check.that("id not found changes nothing", "false [A,B,C,D] size=4", () -> afterDelete("Z", "A", "B", "C", "D"));
            Check.that("delete from an empty list", "false [] size=0", () -> afterDelete("A"));
    
            Check.summary();
        }
    }
    
    // ---- Test helper (do not edit) ----
    class Check {
        private static int passed = 0;
        private static int total = 0;
    
        // An exception counts as a FAIL so one unfinished method does not stop the other checks.
        static void that(String label, String expected, Supplier<String> actual) {
            total++;
            try {
                String got = actual.get();
                if (expected.equals(got)) { passed++; System.out.println("PASS  " + label); }
                else System.out.println("FAIL  " + label + ": expected " + expected + ", got " + got);
            } catch (Exception e) {
                System.out.println("FAIL  " + label + "  (" + e + ")");
            }
        }
    
        static void summary() { System.out.println("---- " + passed + " / " + total + " passed ----"); }
    }
    
    DeleteById.main(null);
    
    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Hack 3: Soft delete, the OCS way (10 minutes)

    Keep the node. Add a boolean deleted to Node. Then write:

    • softDeleteById(String id) marks the node deleted and keeps it in the list. It returns false if the ID isn’t found or is already deleted, and in that case nothing changes, like OCS’s if (message.isDeleted()) return;.
    • show() prints [deleted] in place of a deleted node.
    • visibleCount() counts the nodes that are not deleted.
    Test (one list A,B,C,D, in order) Expected
    softDeleteById("B") true, A,[deleted],C,D, size 4, visible 3
    softDeleteById("B") again false, nothing changes
    softDeleteById("Z") false, nothing changes
    softDeleteById("C") true, A,[deleted],[deleted],D, size 4, visible 2

    Code Runner Challenge

    Write softDeleteById, show and visibleCount until every check prints PASS

    View IPYNB Source
    // CODE_RUNNER: Write softDeleteById, show and visibleCount until every check prints PASS
    // OCS keeps the row and marks it deleted. Do the same: the node stays in the list.
    import java.util.function.Supplier;
    
    public class SoftDelete {
        static class Node {
            String value;
            Node next;
            // TODO: add a boolean deleted field here (false until the node is soft-deleted)
            Node(String value) { this.value = value; }
        }
    
        Node head;
        int size;
    
        void add(String value) {
            Node node = new Node(value);
            if (head == null) {
                head = node;
            } else {
                Node cur = head;
                while (cur.next != null) {
                    cur = cur.next;
                }
                cur.next = node;
            }
            size++;
        }
    
        // TODO: find the node whose value equals id and mark it deleted. The node stays in the list.
        // Return false, and change nothing, if id is not found or that node is already deleted.
        boolean softDeleteById(String id) {
            /* to be implemented */
            return false;
        }
    
        // TODO: print [deleted] in place of the value of every deleted node.
        String show() {
            StringBuilder sb = new StringBuilder();
            for (Node n = head; n != null; n = n.next) {
                if (sb.length() > 0) sb.append(",");
                sb.append(n.value);
            }
            return sb.toString();
        }
    
        // TODO: count the nodes that are not deleted.
        int visibleCount() {
            /* to be implemented */
            return 0;
        }
    
        // ---- Tests: do not change below this line ----
        static String state(SoftDelete list) {
            return "[" + list.show() + "] size=" + list.size + " visible=" + list.visibleCount();
        }
    
        static String softDelete(SoftDelete list, String id) {
            boolean deleted = list.softDeleteById(id);
            return deleted + " " + state(list);
        }
    
        public static void main(String[] args) {
            // One list for all four checks, in order: each check starts from what the one before left behind.
            SoftDelete list = new SoftDelete();
            for (String v : new String[] {"A", "B", "C", "D"}) list.add(v);
    
            Check.that("soft delete B", "true [A,[deleted],C,D] size=4 visible=3", () -> softDelete(list, "B"));
            Check.that("soft delete B again changes nothing", "false [A,[deleted],C,D] size=4 visible=3", () -> softDelete(list, "B"));
            Check.that("id not found changes nothing", "false [A,[deleted],C,D] size=4 visible=3", () -> softDelete(list, "Z"));
            Check.that("soft delete C", "true [A,[deleted],[deleted],D] size=4 visible=2", () -> softDelete(list, "C"));
    
            Check.summary();
        }
    }
    
    // ---- Test helper (do not edit) ----
    class Check {
        private static int passed = 0;
        private static int total = 0;
    
        // An exception counts as a FAIL so one unfinished method does not stop the other checks.
        static void that(String label, String expected, Supplier<String> actual) {
            total++;
            try {
                String got = actual.get();
                if (expected.equals(got)) { passed++; System.out.println("PASS  " + label); }
                else System.out.println("FAIL  " + label + ": expected " + expected + ", got " + got);
            } catch (Exception e) {
                System.out.println("FAIL  " + label + "  (" + e + ")");
            }
        }
    
        static void summary() { System.out.println("---- " + passed + " / " + total + " passed ----"); }
    }
    
    SoftDelete.main(null);
    
    Lines: 1 Characters: 0
    Output
    Click "Run" in code control panel to see output ...

    Grading Plan (1 Point Total)

    Part Points What earns the points
    Popcorn 0.2 A prediction for the starter delete(0) written before running, the run compared with it, and the checker line in the notes.
    MCQ 0.2 4 correct. 0.15 for 2 or 3, 0.1 if every question was answered.
    Homework Hack 1 0.2 delete(index) fixed, 12 / 12 passed.
    Homework Hack 2 0.15 deleteById searches then unlinks, 4 / 4 passed.
    Homework Hack 3 0.25 Soft delete keeps the order and size, and the repeat and not-found cases change nothing: 4 / 4 passed.
    Total 1.0  

    Quick Validation Checklist

    • Each runner ends with ClassName.main(null); and shows output.
    • The popcorn checker line and the MCQ score are in the notes.
    • Every runner prints N / N passed.
    • Each runner was saved with 💾 before submitting, as the code submission form asks.
    • While the assignment is open, you can read the AI feedback, fix your code and submit again.

    6. LxD Cycle Process

    Empathize: Students stop at the target node instead of before it. They also assume “delete” always removes the data.

    Define:

    • POV: CS 113 students need to know which reference to change, because one wrong next loses or keeps the wrong message.
    • Learning Goal: Delete by index and by ID, and explain why OCS keeps a tombstone.

    Ideate:

    • HMW Question: How might we make students find the node before the target?
    • HMW Question: How might we show why a real chat app keeps deleted rows?

    Prototype:

    • A reference guide, the real OCS delete path, runnable examples, a popcorn prediction, an MCQ, three self-checking hacks and the grading plan.

    Test:

    • S5CY peer-tested the earlier version.
    • Ask a peer to do the new hacks without help, then revise anything that confused them.

    7. References/Citations

    Open Coding Society. spring backend (Open-Coding-Society/spring). Direct messages, src/main/java/com/open/spring/mvc/directmessages/:

    • DirectMessageApiController.java: deleteMessage (DELETE /api/dm/conversations/{id}/messages/{messageId}) and editMessage (PATCH, same path).
    • DirectMessageService.java: deleteMessage(conversation, requester, messageId) and DM_TOPIC_PREFIX (/topic/dm/).

    Open Coding Society. CS 113 course outline, II.B Linked lists.

    Open Coding Society. Collectables Homework, HW 1 removeStanding, which cites AP CSA 2021 Question 3 (ClubMembers). See also the 2021 Q3 walkthrough.

    Submit Assignment

    Rate the lesson during class in the 💬 Microblog panel's Ratings tab. Anything you skipped there is finished here.

    Choose what to hand in: click Add to submission on each runner you want graded (hacks, popcorn hacks), and save it. Leaving out practice runners does not lower your grade, but a required hack you leave out is graded as missing. Your selection is sent as a Gist for automatic review.

      Need to update a submission later? Open the submissions dashboard.