Singly linked lists in Python

Why it matters

A linked list is the first structure you build out of references. The same tool is used for stacks, queues, trees and graphs. Python's built-in list is an array, so everyday Python code rarely needs a linked list. Interviewers still ask about them, because a small mistake with a next reference shows whether you understand what the program does with each object. This lesson starts from how Python stores objects and builds the list one step at a time.

Start with names and objects

In Python, a name is a label that points at an object. The line x = 5 creates an int object that holds 5, and the name x points at it. The line y = x does not copy the 5. It makes y point at the same object as x.

Every object has an identity, a number that stays the same for the object's whole life. The function id(x) returns it. In CPython, the standard Python program, this number is the object's memory address. Your numbers will differ from any example, so never rely on the exact value.

Python does not let you write addresses yourself. A variable that holds an object holds a reference, which is a hidden pointer to the object. Think of a reference as a sticky note with the object's location written on it. Copying the sticky note does not copy the object. Two sticky notes can lead to the same object.

Python frees an object when nothing refers to it anymore. CPython keeps a count of the references to each object and frees the object when the count reaches zero. A separate part of CPython, the cycle collector, handles groups of objects that refer to each other. You never free memory yourself. This is why a linked list is easy to write in Python: you change references, and the nodes you no longer reach are freed on their own.

Local names live in a function's frame, the record Python keeps for each call that is running. When the function returns, its local names disappear. An object stays alive as long as some reference still reaches it.

The idea: a chain of nodes

An array is like a row of lockers placed side by side. If you know the locker number, you open it directly. A linked list is more like a scavenger hunt. Each clue is a node. A clue holds a prize, which is its value, and it tells you where the next clue is. You cannot jump to clue number 7. You must start at the first clue and follow the chain.

Each node has two attributes. An attribute is a named value stored on an object and read with a dot, such as node.val.

• val, the value the node stores.
• next, a reference to the next node. The last node has next set to None, which means "nothing follows". None is Python's name for "no object".

The list itself holds a reference to the first node, called head. An empty list has head set to None. Here is a list of two values in a text diagram:

head -> [val 10 | next] -> [val 20 | next] -> None

Every operation in this lesson changes next attributes, and every one of them must keep the chain connected. Here is the rule for every change: before you overwrite a reference, make sure you have saved it somewhere. A node that no reference can reach is lost. Python frees a lost node as soon as its last reference disappears, so the rest of the list vanishes from your program without any error.

Writing the Node class

Python needs a class that describes a node. Here is the smallest useful version:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

class Node: defines a new kind of object. The method named __init__ runs when you write Node(10). Python creates the empty object, passes it in as the first argument, and __init__ fills it in. That first argument is named self by convention. self.val means "the field of the object being built". Java hides this object behind this. Python writes it out in every method, so self. appears on every attribute.

The plain name val on the right side is the parameter, the value passed in by the caller. self.val is the attribute on the object. The two names are different, and the dot tells you which one you mean.

Python does not check types while the program runs. You may see a type hint such as def __init__(self, val: int):. Tools like mypy read those hints, but the program runs the same with or without them. This lesson leaves them out to keep the code short.

Worked example 1: add at the front

Adding at the front is the easiest operation, and it teaches the rule that matters most in this lesson. Suppose the list is 10 -> 20 -> None and you want to add 5 at the front. Do three things, in this exact order.

1. Create the new node: n = Node(5). Its next is None.
2. Point the new node at the old first node: n.next = self.head. Now n.next refers to the node with 10.
3. Move the head to the new node: self.head = n.

Trace the state after each step. Start with head pointing to node 10, and node 10 pointing to node 20.

• After step 1: there are two separate pieces. n refers to the node 5 with a None next. head still leads to 10 and 20.
• After step 2: the node 5 now leads to 10 and 20. head still points at node 10, so the list is not yet reachable from the head through node 5.
• After step 3: head points at node 5, and the chain reads 5 -> 10 -> 20 -> None.

Now swap steps 2 and 3. After self.head = n, the head points at the new node. Then n.next = self.head makes the new node point at itself. Nodes 10 and 20 have no references left, so Python frees them. The list now holds one node that points at itself, so any walk over it never ends. Always save the old head before you move it, or always point the new node first.

The next program is a complete class for the operations in the first part of this lesson. It builds a fixed list and prints it. It needs no input.

Output:

5 -> 10 -> 20 -> 30 -> None
size: 4
contains 20: True
contains 99: False
Node(5)

Three Python features appear in this program.

• __repr__ tells Python how to show a node. Without it, print(lst.head) would show something like <__main__.Node object at 0x...>. The f"Node({self.val})" text is an f-string, a string with values filled in from {...}.
• __iter__ makes the list iterable. The method uses yield, which makes it a generator. A generator gives one value at a time and remembers where it stopped. for v in lst: runs the method and receives each value in turn.
• len(lst) calls __len__, and 20 in lst has no __contains__ method, so Python falls back to walking __iter__. Python checks membership this way for any iterable.

The loop shape in __len__ is the basic walk. It starts with cur = self.head, keeps going while cur is not None, and moves with cur = cur.next. You will write it many times, so learn to write it without thinking.

What happens inside

Take add_last(30) in the program above and follow it in memory. The method does not receive a copy of the list. It works on the same node objects that lst already refers to. The local name cur is a new label on the frame. At first it points at the same node as self.head. Each pass of the while loop executes cur = cur.next, which moves the label from one node to the next. When cur points at the last node, cur.next is None, the loop stops, and cur.next = n stores the reference to the new node in the last node's attribute.

Notice what does not change. self.head still points at the first node, because the method never wrote self.head = something. Only the last node's next changed. This is why add_last on a non-empty list never touches head.

Compare that with add_first. It writes self.head = n, which changes the reference stored on the list object, so every method that reads self.head sees the new value. That is why head is an attribute of the list, not a local name inside one method.

The local name n in add_last disappears when the method returns, but the node it pointed to does not. It stays alive, reached from the last node's next attribute. A reference is what keeps a node alive, not the name of the variable.

Comparing references and values

Python has two ways to compare, and linked lists make the difference visible. The operator == asks whether two values are equal. The operator is asks whether two names point at the same object.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
 
 
a = Node(20)
b = Node(20)
c = a
print(a == b, a is b, c is a)

Output:

False False True

Two nodes can hold the value 20 and still be different nodes. For your own classes, == falls back to is unless the class defines __eq__. So a == b is False, because they are two objects. c is a is True, because c is the same object as a.

Use is to test for None, as in while cur is not None. Python's style guide asks for is with None, because None is a single object and is checks exactly that. Use == when you compare the contents of two numbers, strings or other values, such as cur.val == v. For a plain number stored in a node, == compares the numbers.

Worked example 2: delete a value

Deleting is harder than adding because you must remember the node before the one you remove. Suppose the list is 10 -> 20 -> 30 -> None and you want to delete 20. The node 20 cannot delete itself. The node 10 has to point past it, so you set cur.next = cur.next.next, where cur is the node 10.

There are four cases, and each has its own line of code.

• The list is empty. Nothing to delete. Return False.
• The head holds the value. Move the head: self.head = self.head.next. There is no node before the head to fix.
• A middle node holds the value. Walk with cur until cur.next.val equals the value, then cur.next = cur.next.next.
• The value is not in the list. The walk reaches None and nothing changes.

The last node is a middle case in disguise. If you delete 30 from 10 -> 20 -> 30 -> None, the node 20 gets next = None, which is correct.

The next program has its data built in, so it needs no input. It deletes 20, tries a value that is not there, then deletes the head.

Output:

10 -> 20 -> 30 -> 40 -> None
removed 20
10 -> 30 -> 40 -> None
not found: 99
10 -> 30 -> 40 -> None
removed 10
30 -> 40 -> None

Trace the delete of 20 step by step. The head holds 10, which is not 20, so the head case does not apply. cur starts at the head. The loop checks cur.next is not None, which is true because the node is 20, and then cur.next.val != v, which is 20 != 20, so it is false. The loop stops with cur on the node 10. The check cur.next is None is false, so the code runs cur.next = cur.next.next. The node 10 now points at the node 30. The node 20 has no references left, and Python frees it.

If you delete 99 instead, the loop walks to the last node 40. There cur.next is None, so the loop stops. The test cur.next is None is true, the method returns False, and the list is not touched.

The and in the loop condition matters. Python evaluates and from left to right and stops as soon as the answer is known. So cur.next is not None is checked first, and cur.next.val is read only when cur.next is not None. Swap the two parts and the program raises an error on the last node. You will see that error in the common mistakes section.

Worked example 3: insert in sorted order

Keeping a list sorted is a common task. A leaderboard, a list of due dates and a list of ticket numbers all need the new value in the right place. The method has two cases. If the new value is at most the head's value, the new node becomes the head. Otherwise, walk forward while the next value is still smaller than the new value, then insert after the node you stopped on.

Take the list 1 -> 3 -> 8 -> 9 and insert 5. The head holds 1, and 5 is not at most 1, so the head case does not apply. cur starts on 1. The next node holds 3, which is smaller than 5, so cur moves to 3. The next node holds 8, which is not smaller than 5, so the loop stops. Now cur is the node before the right place. Set n.next = cur.next, which points the new node at 8, then cur.next = n, which links 3 to the new node. The result is 1 -> 3 -> 5 -> 8 -> 9.

The program below inserts five values in no particular order. It prints the list after each insert, so you can see each walk stop in the right place.

Output:

after inserting 8 : 8 -> None
after inserting 3 : 3 -> 8 -> None
after inserting 9 : 3 -> 8 -> 9 -> None
after inserting 1 : 1 -> 3 -> 8 -> 9 -> None
after inserting 5 : 1 -> 3 -> 5 -> 8 -> 9 -> None

Trace the first two inserts. Insert 8 into an empty list: head is None, so the head case runs and the list is 8. Insert 3: 3 is not greater than 8, so the head case runs again and the list is 3 -> 8. Insert 9: the head is 3, so the walk starts. The next node is 8, which is smaller than 9, so cur moves to 8. The next node is None, so the loop stops, and 9 goes after 8. Each insert walks only as far as it needs to.

Reading by position

Lists have no index, so the only way to read the k-th value is to walk k steps. The method below returns None when the index is too large. Returning None is a common way to say "no answer". The caller must check for it, or the program fails later with an AttributeError.

Python's own list raises an IndexError for a bad index instead. Both styles are used. Pick one for your own classes and write it in the method's name or comment, so the caller knows what to expect.

Output:

value at index 2 : 30
no value at index 7
no value at index -1

The loop for _ in range(index) takes exactly index steps. The name _ marks a value you do not use. The first if cur is None handles a list shorter than index. The check index < 0 handles negative indexes. Without it, get_at(-1) would return the head's value, because range(-1) is empty.

Trace table: four operations in a row

A trace table is the most useful tool for linked lists. You write one row for each operation and record what the head points to and what the list reads after the operation. You can see mistakes before running the code. Start from an empty list and perform these four operations in order: add_last(10), add_last(20), add_first(5), and delete(10).

Look at step 1 closely. The head was None, so add_last takes the special branch and sets self.head = n. Step 2 takes the walk: cur starts at node 10, sees that its next is None, and stores the new node in cur.next. The head does not change. Step 3 writes n.next = self.head and then self.head = n, which is the save-before-overwrite order. Step 4 is the head-and-middle logic from the delete method. The head holds 5, which is not 10, so the head case is skipped. The walk stops on node 5, because cur.next holds 10. Then cur.next = cur.next.next points node 5 at node 20.

Node 10 still exists after step 4, but nothing refers to it. Python frees it at that moment, because its reference count reaches zero. You do not call any free function. In a language like C, you would have to free the node yourself, and forgetting to do so is a memory leak.

When you write your own trace table, fill the last column with care. A printed list with a missing node is almost always a node that became unreachable too early.

What the cost is

Each operation has a cost in steps, which we write in Big-O notation. Big-O describes how the work grows as the list grows. O(n) means the work grows in proportion to the number of nodes, n.

An array gives you O(1) access to any position, but inserting in the middle means shifting many values. A linked list gives you O(1) insertion at a known place, but finding that place takes a walk. A later lesson in this module adds a tail reference, which makes adding at the end O(1).

Space is O(n) for n nodes. Each node is a full Python object. Python objects carry extra data for their type and attributes, so a node that holds one number takes much more memory than the number inside a Python list. If the size matters, sys.getsizeof reports the size of one object. The exact number depends on your Python version and machine.

Common mistakes and the messages you will see

The most common bugs in linked lists show up when the program runs, not as errors before it starts. Python does not check your references ahead of time, so you learn to read the message.

Losing the rest of the list. In add_first, moving the head before saving the old one makes the rest of the list unreachable. The program does not crash. It prints a shorter list than you expect, and the missing nodes are freed. Print the list after every step while you learn.

Reading an attribute of None. This is the error you will see most often. Take the loop while cur.next.val != 5: cur = cur.next on the list 10 -> 20 -> None. When cur reaches 20, cur.next is None, and cur.next.val tries to read an attribute of nothing. Python stops the program with this message:

AttributeError: 'NoneType' object has no attribute 'val'

Read it in two parts. NoneType is the type of None, and 'val' is the attribute that was read. Python is saying that None has no attribute named val. The traceback above this line shows the file and line number. Fix it by checking cur.next is not None before reading cur.next.val. The loop is then while cur.next is not None and cur.next.val != 5:.

Forgetting the head case. A delete method that starts its loop at head and checks cur.next.val never looks at the head itself. Delete the first node, and nothing happens. Always test self.head.val before the loop.

Using the head as the walking name. If you write self.head = self.head.next inside a print loop, the list loses its first node every time you print. Use a second name such as cur for walking.

Recursion on a long list. A recursive walk calls itself once per node. Python limits the depth of nested calls, and the default limit is 1000. The program below walks a list of 2000 nodes recursively. It fails with the last line shown here. Python also prints a traceback above that line, which lists the nested calls.

import sys
 
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
 
 
def print_reverse(n):
    if n is None:
        return
    print_reverse(n.next)
    print(n.val, end=" ")
 
 
print("limit:", sys.getrecursionlimit())
head = None
for v in reversed(range(2000)):
    node = Node(v)
    node.next = head
    head = node
print_reverse(head)

Output, first line and last line (the traceback in between is left out):

limit: 1000
...
RecursionError: maximum recursion depth exceeded

The first printed line, limit: 1000, is the value of sys.getrecursionlimit(). For long lists, write the walk with a loop, which has no depth limit. Use recursion only when the list is known to be short.

Debugging walkthrough

Suppose you wrote delete and the output after deleting 20 from 10 -> 20 -> 30 -> 40 is 10 -> 40 -> None. Both 20 and 30 are missing, and the list should be 10 -> 30 -> 40. Do not guess. Follow this routine.

1. Print the list before the operation, then after it. You now know the bug is in the operation.
2. Draw the list on paper with boxes and arrows. Mark each name with an arrow that points at the node it holds.
3. Step through the code with the input. For each loop pass, write down the value of cur and cur.next.
4. Ask at each assignment: which references did I change, and did I save every node I still need?

In this case, step 3 reveals the bug. Suppose the code had cur.next = cur.next.next.next by mistake. Then 20 and 30 are both skipped, and 40 is linked to 10. Writing the values down in a table exposes that the link jumped two nodes instead of one.

A good habit is to define __repr__ early and call print after every change. The output shows the state in one glance, and you will not need a debugger for simple lists. Python's pdb debugger is available too, with the command python3 -m pdb yourfile.py, but a printed list is faster for this kind of bug.

Variations and edge cases

Interviewers like to ask about the edge cases, so check each one before you call a method finished.

• Empty list. head is None. Every method must handle this before reading self.head.val or self.head.next.
• One node. The head is also the last node. Deleting it sets head to None. Adding at the end writes into head.next.
• Duplicate values. Deleting 5 from 5 -> 5 -> 5 should decide whether to remove one 5 or all three. The method above removes only the first match. The practice exercises ask you to write the other version.
• Value not present. Return a clear result, such as False, so the caller knows nothing changed.
• Negative values. Nothing special happens. A value of -1 is a normal value. Do not use -1 as a sentinel for "not found" if negative values are allowed. Return None or a boolean instead.

Test your methods on each case, not only on a happy path. The fastest way is a list of small test lists, each printed after the operation.

Null checks, step by step

Most linked-list code is a sequence of None checks. The safe pattern is to decide, before each attribute read, which reference could be None. Here are the three places where it can happen in this lesson.

The head itself. An empty list has self.head is None. Any method that reads self.head.val or self.head.next must test self.head is not None first. delete tests it at the top, and insert_sorted tests self.head is None or v <= self.head.val. The second test is safe because or stops as soon as the first part is true. If the list is empty, self.head.val is never evaluated.

The next node. In a walk, cur.next is None on the last node. The loop condition cur.next is not None stops before the code reads cur.next.val. Reverse the order and you get the error shown earlier.

The current node. The walk while cur is not None lets cur become None after the last node. Use this form when you only read values. Use cur.next is not None when you need to change the last node, because you must stop on the last node itself, not after it.

The order of tests in one condition matters as much as the tests themselves. Write cur is not None and cur.val == v, not the reverse. The first form is safe. The second raises an AttributeError when cur is None, because Python evaluates the left side first and the right side only if the left side is true.

When you are unsure, write the None check on paper before the code. Circle every reference that could be None and ask whether a check is in place before it is read. Experienced programmers do this in their heads, and interviewers can see when it is missing.

Interview patterns

Most linked-list questions reduce to three patterns, and you will meet them again in this module.

The walk. Start at self.head, loop while cur is not None, and move with cur = cur.next. Counting, searching and printing all use it.

The one-node-behind pointer. To delete or insert after a node, keep a reference to the node before the target. The change is always prev.next = something. The case where the target is the head is the special one, and a dummy node removes it, as a later lesson in this module shows.

The save-before-you-overwrite rule. Any time you write to a reference, check that no node is now lost. Save next before you change it, and save the old head before you move it.

In interviews, say these patterns out loud. Explain what each name holds at each step. An interviewer who hears "cur holds the node before the one I delete" knows you understand the structure, even if your code has a small slip.

Questions to answer out loud

Interviewers ask the same few questions about linked lists, and a clear spoken answer matters as much as the code. Practise these until you can explain each one in under a minute.

Why not use a Python list? A Python list is an array. It is faster for reading by index and for scanning, because each element is found by a direct calculation. A linked list is faster for inserting and removing at a known place, because only references change and no values move. If the program mostly reads by index, use a list. If it mostly inserts and removes at known places, a list of nodes fits better. Say which operations dominate your workload, then pick.

How do you get the last node? Walk from the head until cur.next is None. That costs O(n). If the list needs many appends, keep a tail reference so each append is O(1). Mention the cost of keeping tail correct after a removal, because forgetting it is a common bug.

Why check the head first? The head is the only node with no predecessor, so inserting or removing it changes the head reference itself. A method that starts its walk at the head and only looks at cur.next never examines the head, so it misses that case. Checking the head first is the simplest fix.

How do you find the middle? Use two pointers: one moves one step and one moves two steps. When the fast one reaches the end, the slow one is at the middle. Say which middle you return for an even count, because interviewers often ask for the other one.

What do you do when the list is empty? Return early, or return the value the question asks for, before reading self.head.val or self.head.next. Test the empty case on every method. Interviewers often check this first, because an empty-list error is the most common failure.

Real-world uses

Linked lists are rarely the best answer in production Python. The built-in list is faster for most work. Linked structures still matter for three reasons. Many systems keep a chain of items where insertion and removal happen at known places, such as a queue of tasks or an undo history. Many larger structures are built from nodes: trees, graphs and hash table buckets. And the reference skills you practise here are the same ones you need to read code written by others.

collections.deque gives fast adds and removes at both ends. Its CPython version stores items in small blocks that are chained together, so the structure is linked at the block level. A stack, which you will meet in module 18, is often a singly linked list where you add and remove only at the head. In Python, a stack is usually a list with append and pop, which are also O(1) on average at the end.

Practice

Try these before you open the solutions. Write the code on paper first, then check it by tracing the list. Each exercise adds a method to SinglyList, the class from the first program in this lesson.

Exercise 1 (easy). Write a method total(self) that returns the sum of all values.

Show the answer

def total(self):
    total = 0
    cur = self.head
    while cur is not None:
        total += cur.val
        cur = cur.next
    return total

The loop is the walk pattern. It visits each node once, so the time is O(n). An empty list returns 0 because the loop never runs.

Exercise 2 (easy). Write a method find_node(self, v) that returns the first node holding v, or None if none does.

Show the answer

def find_node(self, v):
    cur = self.head
    while cur is not None:
        if cur.val == v:
            return cur
        cur = cur.next
    return None

This is in with the node returned instead of a boolean. Returning the node lets the caller change it, which the next exercises need.

Exercise 3 (easy). Write a method count_value(self, v) that returns how many nodes hold the value v.

Show the answer

def count_value(self, v):
    count = 0
    cur = self.head
    while cur is not None:
        if cur.val == v:
            count += 1
        cur = cur.next
    return count

Unlike find_node, this method does not stop at the first match. It walks the whole list, so the time is O(n) in every case.

Exercise 4 (easy). Write a method insert_after(self, target, v) that inserts a new node right after the first node holding target. If no node holds target, do nothing.

Show the answer

def insert_after(self, target, v):
    node = self.find_node(target)
    if node is None:
        return
    n = Node(v)
    n.next = node.next      # save the rest of the list first
    node.next = n           # then link the new node in

The order matters. Setting node.next = n first would lose every node after node. The new node points at the old successor before the successor is lost, which is the same save-before-overwrite rule as add_first.

Exercise 5 (medium). Write a method delete_all(self, v) that removes every node holding v, not only the first.

Show the answer

def delete_all(self, v):
    while self.head is not None and self.head.val == v:
        self.head = self.head.next          # clear the matching head nodes
    cur = self.head
    while cur is not None and cur.next is not None:
        if cur.next.val == v:
            cur.next = cur.next.next        # skip the match, stay on cur
        else:
            cur = cur.next                  # only move when nothing was removed

The first loop handles a run of matches at the head. The second loop must not move cur after a removal, because the new cur.next might also match.

Exercise 6 (medium). Write a method add_at(self, index, v). Index 0 means the front. If the index is larger than the size, add at the end.

Show the answer

def add_at(self, index, v):
    if index <= 0 or self.head is None:
        n = Node(v)
        n.next = self.head
        self.head = n
        return
    cur = self.head
    for _ in range(index - 1):
        if cur.next is None:
            break
        cur = cur.next                      # stop on the node just before the position
    n = Node(v)
    n.next = cur.next
    cur.next = n

The loop stops one node early, on the node before the position. If the list ends sooner, cur stops on the last node, and the new node becomes the last one. That gives the "add at the end" behaviour for large indexes.

Exercise 7 (medium). Write a function reverse_values(n) that takes a node and returns a Python list of the values from the last node to the first, using recursion. Call it as reverse_values(lst.head).

Show the answer

def reverse_values(n):
    if n is None:
        return []
    return reverse_values(n.next) + [n.val]

Each call waits for the call on the next node to finish. The last node's value ends up first in the returned list, and the head's value ends up last. The recursion goes one level per node, so it hits the recursion limit on long lists, as the common mistakes section shows.

Exercise 8 (hard). Write a method remove_duplicates(self) for a sorted list, so that each value appears only once. For example, 1 -> 1 -> 2 -> 2 -> 2 -> 3 becomes 1 -> 2 -> 3.

Show the answer

def remove_duplicates(self):
    cur = self.head
    while cur is not None and cur.next is not None:
        if cur.next.val == cur.val:
            cur.next = cur.next.next        # drop the repeat, do not move cur
        else:
            cur = cur.next

Because the list is sorted, equal values sit next to each other. A repeat is removed by skipping it, and cur stays put in case the next node is also a repeat. The time is O(n) and the extra space is O(1).

Exercise 9 (hard). Write a method copy(self) that returns a new list with the same values. Changing the copy must not change the original.

Show the answer

def copy(self):
    result = SinglyList()
    tail = None
    cur = self.head
    while cur is not None:
        n = Node(cur.val)               # a new node with the same value
        if tail is None:
            result.head = n
        else:
            tail.next = n
        tail = n
        cur = cur.next
    return result

The copy creates new Node objects. Copying only the head reference would make both lists share the same nodes, so a change to one would appear in the other. This is the difference between a shallow copy, which shares the nodes, and a deep copy, which makes new ones. The standard library's copy module has both kinds for other objects, but a linked list needs the walk shown here.

What you now know

• A name is a label that points at an object. A node is an object with a val attribute and a next attribute.
• The head reference is the only way into the list, so moving it changes what the whole list means.
• To walk, start at the head and move with cur = cur.next while cur is not None.
• Adding at the front and deleting a node you already have a reference to both need the saved next node.
• Deleting by value needs the node before the target, and the head is a special case.
• Most linked-list bugs appear as an AttributeError on None or a list that is silently shorter than expected.