Java singly linked lists
A singly linked list stores each item in a node that holds a value and a reference to the next node. The list keeps a reference to the first node, called the head. Inserting at the front is O(1): create a node whose next is the old head and make it the new head. Appending at the end is O(n) unless the list also keeps a tail reference.
Java
class Main {
static class Node {
int value;
Node next;
Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
static Node head = null;
static void addFirst(int value) {
head = new Node(value, head);
}
static void addLast(int value) {
Node node = new Node(value, null);
if (head == null) {
head = node;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
static void reverse() {
Node previous = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = previous;
previous = current;
current = next;
}
head = previous;
}
static String show() {
StringBuilder sb = new StringBuilder();
for (Node n = head; n != null; n = n.next) {
sb.append(n.value).append(n.next == null ? "" : " -> ");
}
return sb.toString();
}
public static void main(String[] args) {
addFirst(2);
addFirst(1);
addLast(3);
addLast(4);
System.out.println(show());
reverse();
System.out.println(show());
}
}