Card 03/ 09
Singly Linked List in Python, Java and TypeScript
A list with head and tail references, then the built-in each language offers.
A singly linked list needs only a node type and two references, to its first node and its last, and every operation is a walk, a rewire or both. This card covers one in Python, Java and TypeScript, with push at the front, append, insert after a node and delete by value, and then what each language provides built in.
The names here are Python's, and Java and TypeScript spell them pushFront and insertAfter. push_front makes a node that points at the old head. append links the new node after the tail, or makes it the head when the list is empty. insert_after sets the new node's next before changing the existing node's, the order that keeps the rest of the list reachable. delete walks with two references, previous one node behind current, because unlinking a node means changing the next of the node before it; when the node removed was the tail, the tail moves back to previous. Each listing prints the values from the head, and the tail's value, after every operation.
Before the output: after 5 is deleted from 1 3 7 4 5, what does the line print for the tail, and where does the 9 appended next go?
The tail is 4, because delete moves it back to the node before the one it removed. The 9 is then linked after the 4, giving 1 3 7 4 9.
The highlighted lines are the two rewires of an insert and the tail update in delete.
A singly linked list with head and tail references
from dataclasses import dataclass
@dataclass
class Node:
value: int
next: Node | None = None
class SinglyLinkedList:
def __init__(self) -> None:
self.head: Node | None = None
self.tail: Node | None = None
def push_front(self, value: int) -> None:
self.head = Node(value, self.head)
if self.tail is None:
self.tail = self.head
def append(self, value: int) -> None:
node = Node(value)
if self.tail is None:
self.head = node
else:
self.tail.next = node
self.tail = node
def find(self, value: int) -> Node | None:
current = self.head
while current is not None and current.value != value:
current = current.next
return current
def insert_after(self, node: Node, value: int) -> None:
new_node = Node(value, node.next)
node.next = new_node
if node is self.tail:
self.tail = new_node
def delete(self, value: int) -> None:
previous: Node | None = None
current = self.head
while current is not None and current.value != value:
previous = current
current = current.next
if current is None:
return
if previous is None:
self.head = current.next
else:
previous.next = current.next
if current is self.tail:
self.tail = previous
def values(self) -> list[int]:
items: list[int] = []
current = self.head
while current is not None:
items.append(current.value)
current = current.next
return items
def show(label: str, numbers: SinglyLinkedList) -> None:
tail = "none" if numbers.tail is None else numbers.tail.value
print(f"{label}: {numbers.values()}, tail {tail}")
numbers = SinglyLinkedList()
for value in (3, 7, 5):
numbers.append(value)
show("append 3, 7, 5", numbers)
seven = numbers.find(7)
if seven is not None:
numbers.insert_after(seven, 4)
show("insert 4 after 7", numbers)
numbers.push_front(1)
show("push 1 at the front", numbers)
numbers.delete(5)
show("delete 5", numbers)
numbers.append(9)
show("append 9", numbers)
numbers.delete(1)
show("delete 1", numbers)OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)
append 3, 7, 5: [3, 7, 5], tail 5
insert 4 after 7: [3, 7, 4, 5], tail 5
push 1 at the front: [1, 3, 7, 4, 5], tail 5
delete 5: [1, 3, 7, 4], tail 4
append 9: [1, 3, 7, 4, 9], tail 9
delete 1: [3, 7, 4, 9], tail 9import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class SinglyLinkedList {
static final class Node {
final int value;
Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
Node head;
Node tail;
void pushFront(int value) {
head = new Node(value, head);
if (tail == null) {
tail = head;
}
}
void append(int value) {
Node node = new Node(value, null);
if (tail == null) {
head = node;
} else {
tail.next = node;
}
tail = node;
}
Node find(int value) {
Node current = head;
while (current != null && current.value != value) {
current = current.next;
}
return current;
}
void insertAfter(Node node, int value) {
Node newNode = new Node(value, node.next);
node.next = newNode;
if (node == tail) {
tail = newNode;
}
}
void delete(int value) {
Node previous = null;
Node current = head;
while (current != null && current.value != value) {
previous = current;
current = current.next;
}
if (current == null) {
return;
}
if (previous == null) {
head = current.next;
} else {
previous.next = current.next;
}
if (current == tail) {
tail = previous;
}
}
List<Integer> values() {
List<Integer> items = new ArrayList<>();
for (Node current = head; current != null; current = current.next) {
items.add(current.value);
}
return items;
}
static void show(String label, SinglyLinkedList numbers) {
String tail = numbers.tail == null ? "none" : String.valueOf(numbers.tail.value);
System.out.println(label + ": " + numbers.values() + ", tail " + tail);
}
public static void main(String[] args) {
SinglyLinkedList numbers = new SinglyLinkedList();
for (int value : new int[] {3, 7, 5}) {
numbers.append(value);
}
show("append 3, 7, 5", numbers);
Node seven = numbers.find(7);
if (seven != null) {
numbers.insertAfter(seven, 4);
}
show("insert 4 after 7", numbers);
numbers.pushFront(1);
show("push 1 at the front", numbers);
numbers.delete(5);
show("delete 5", numbers);
numbers.append(9);
show("append 9", numbers);
numbers.delete(1);
show("delete 1", numbers);
LinkedList<Integer> builtIn = new LinkedList<>(List.of(3, 7, 5));
builtIn.add(2, 4);
builtIn.addFirst(1);
builtIn.remove(Integer.valueOf(5));
builtIn.addLast(9);
builtIn.removeFirst();
System.out.println("java.util.LinkedList: " + builtIn);
}
}OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)
append 3, 7, 5: [3, 7, 5], tail 5
insert 4 after 7: [3, 7, 4, 5], tail 5
push 1 at the front: [1, 3, 7, 4, 5], tail 5
delete 5: [1, 3, 7, 4], tail 4
append 9: [1, 3, 7, 4, 9], tail 9
delete 1: [3, 7, 4, 9], tail 9
java.util.LinkedList: [3, 7, 4, 9]class ListNode {
value: number;
next: ListNode | null;
constructor(value: number, next: ListNode | null) {
this.value = value;
this.next = next;
}
}
class SinglyLinkedList {
head: ListNode | null = null;
tail: ListNode | null = null;
pushFront(value: number): void {
this.head = new ListNode(value, this.head);
if (this.tail === null) {
this.tail = this.head;
}
}
append(value: number): void {
const node = new ListNode(value, null);
if (this.tail === null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
find(value: number): ListNode | null {
let current = this.head;
while (current !== null && current.value !== value) {
current = current.next;
}
return current;
}
insertAfter(node: ListNode, value: number): void {
const newNode = new ListNode(value, node.next);
node.next = newNode;
if (node === this.tail) {
this.tail = newNode;
}
}
delete(value: number): void {
let previous: ListNode | null = null;
let current = this.head;
while (current !== null && current.value !== value) {
previous = current;
current = current.next;
}
if (current === null) {
return;
}
if (previous === null) {
this.head = current.next;
} else {
previous.next = current.next;
}
if (current === this.tail) {
this.tail = previous;
}
}
values(): number[] {
const items: number[] = [];
for (let current = this.head; current !== null; current = current.next) {
items.push(current.value);
}
return items;
}
}
function show(label: string, numbers: SinglyLinkedList): void {
const tail = numbers.tail === null ? "none" : String(numbers.tail.value);
console.log(`${label}: [${numbers.values().join(", ")}], tail ${tail}`);
}
const numbers = new SinglyLinkedList();
for (const value of [3, 7, 5]) {
numbers.append(value);
}
show("append 3, 7, 5", numbers);
const seven = numbers.find(7);
if (seven !== null) {
numbers.insertAfter(seven, 4);
}
show("insert 4 after 7", numbers);
numbers.pushFront(1);
show("push 1 at the front", numbers);
numbers.delete(5);
show("delete 5", numbers);
numbers.append(9);
show("append 9", numbers);
numbers.delete(1);
show("delete 1", numbers);OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3
append 3, 7, 5: [3, 7, 5], tail 5
insert 4 after 7: [3, 7, 4, 5], tail 5
push 1 at the front: [1, 3, 7, 4, 5], tail 5
delete 5: [1, 3, 7, 4], tail 4
append 9: [1, 3, 7, 4, 9], tail 9
delete 1: [3, 7, 4, 9], tail 9Java's java.util.LinkedList is doubly linked, each node referring to the one before it as well, and it keeps both ends, so addFirst, addLast and removeFirst are O(1), while add(2, 4) walks to index 2 first. Python's standard library has no linked list: collections.deque is built from linked blocks of elements and is O(1) at both ends, but it hands out no node to insert after. TypeScript has none either, so a program that needs one writes a class like the one above.
← → move through sections and cards