A linked list is a collection of nodes, where each node stores a value and a reference to the successor. The following definition captures that structure:
class Cell {
int data;
Cell next;
Cell(int data) {
this.data = data;
this.next = null;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Cell current = this;
while (current != null) {
sb.append(current.data);
if (current.next != null) sb.append(" -> ");
current = current.next;
}
return sb.toString();
}
}
You can manually wire several Cell objects to form a chain:
Cell a = new Cell(5);
Cell b = new Cell(7);
Cell c = new Cell(4);
Cell d = new Cell(2);
Cell e = new Cell(0);
a.next = b;
b.next = c;
c.next = d;
d.next = e;
System.out.println(a); // prints 5 -> 7 -> 4 -> 2 -> 0
alenation at the head and tail are common insertion patterns:
// Insert as new first node
public void prepend(int value) {
Cell node = new Cell(value);
node.next = root;
root = node;
}
// Insert as new last node
public void append(int value) {
Cell node = new Cell(value);
if (root == null) {
root = node;
return;
}
Cell cursor = root;
while (cursor.next != null) {
cursor = cursor.next;
}
cursor.next = node;
}
Removing a node by value requires skipping it in the chain:
public void remove(int target) {
if (root == null) return;
if (root.data == target) {
root = root.next;
return;
}
Cell cursor = root;
while (cursor.next != null) {
if (cursor.next.data == target) {
cursor.next = cursor.next.next;
return;
}
cursor = cursor.next;
}
}
Updating a value in place also walks the list:
public void replace(int oldVal, int newVal) {
for (Cell c = root; c != null; c = c.next) {
if (c.data == oldVal) {
c.data = newVal;
return;
}
}
}
Fetching a element by its numerical position:
public int elementAt(int idx) {
Cell current = root;
int pos = 0;
while (current != null) {
if (pos == idx) return current.data;
pos++;
current = current.next;
}
throw new IndexOutOfBoundsException("Index " + idx + " out of bounds");
}
A complete implemantation demonstrates all these actions together:
public class SingleLL {
private Cell root;
private static class Cell {
int data;
Cell next;
Cell(int data) { this.data = data; this.next = null; }
}
public void prepend(int value) {
Cell n = new Cell(value);
n.next = root;
root = n;
}
public void append(int value) {
Cell n = new Cell(value);
if (root == null) { root = n; return; }
Cell c = root;
while (c.next != null) c = c.next;
c.next = n;
}
public void remove(int target) {
if (root == null) return;
if (root.data == target) { root = root.next; return; }
Cell c = root;
while (c.next != null) {
if (c.next.data == target) {
c.next = c.next.next;
return;
}
c = c.next;
}
}
public void replace(int old, int updated) {
for (Cell c = root; c != null; c = c.next) {
if (c.data == old) { c.data = updated; return; }
}
}
public int elementAt(int index) {
Cell c = root;
int i = 0;
while (c != null) {
if (i == index) return c.data;
i++;
c = c.next;
}
throw new IndexOutOfBoundsException("invalid index: " + index);
}
public void display() {
for (Cell c = root; c != null; c = c.next) {
System.out.print(c.data + " ");
}
System.out.println();
}
public static void main(String[] args) {
SingleLL list = new SingleLL();
list.prepend(30);
list.prepend(20);
list.prepend(10);
System.out.print("After prepend: ");
list.display();
list.append(40);
list.append(50);
System.out.print("After append: ");
list.display();
list.remove(20);
System.out.print("After removing 20: ");
list.display();
list.replace(30, 35);
System.out.print("After replacing 30 with 35: ");
list.display();
try {
System.out.println("Element at index 2: " + list.elementAt(2));
} catch (IndexOutOfBoundsException ex) {
System.out.println(ex.getMessage());
}
}
}