Linked List History Deletion - Removing a DM
Delete a DM from a linked-list history, then build the soft delete that OCS actually uses.
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);
Popcorn Hack (In-Class)
2-minute challenge: trace the starter delete(0) before you run it.
- On paper, draw
A → B → C → D. Trace the starterdelete(0)from the Tech Talk, one line at a time. - Answer the question in the Popcorn checker under the runner before you run.
- Run the starter runner below and compare its output with your prediction.
- 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);
Before you press Run, predict this output.
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
Testsline. - 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);
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);
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 returnsfalseif the ID isn’t found or is already deleted, and in that case nothing changes, like OCS’sif (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);
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
nextloses 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}) andeditMessage(PATCH, same path).DirectMessageService.java:deleteMessage(conversation, requester, messageId)andDM_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.
Need to update a submission later? Open the submissions dashboard.