☕ DSA Java Articles

Topics › Linked List › Learn 1D LinkedList

Introduction to Singly LinkedList

Easy TUF ID 1237 A2Z

Java source ↗ Edit this article ↗

What this covers

An array stores its elements side by side in one block of memory, which is exactly why arr[i] is a constant-time operation and why growing or shrinking an array in the middle is expensive. A singly linked list makes the opposite trade. Every element lives in its own small object, called a node, and each node carries a reference to the node that comes after it. The elements can be scattered anywhere on the heap; the list exists only through those references. Inserting or removing an element becomes a matter of redirecting one reference, but reaching the i-th element means following i references from the start.

This article introduces the node type used throughout the linked-list section, shows the two standard ways of building a list from an array, then covers traversal, converting back to an array, measuring the length and accessing an element by position. It ends with the one idea that causes most beginner bugs: node variables are references, not copies.

The node

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

A node holds one value and one reference next. The reference is null for the last node, and null is also how we represent the empty list: a list is identified entirely by a reference to its first node, called the head, so “the list is empty” and “the head is null” mean the same thing.

The class is a static nested class so the file compiles on its own, and the two constructors exist for convenience: new ListNode(5) creates a detached node, while new ListNode(5, head) creates a node that already points at an existing list, which is the whole insert-at-head operation in one expression.

A node that is no longer referenced by anything is garbage-collected. There is no explicit free in Java, so “deleting” a node simply means making sure no live reference points at it anymore.

Building a list from an array

The textbook way keeps a mover reference that always points at the current last node. For each new value we create a node, link the mover to it, and then advance the mover onto the new node.

static ListNode arrayToLinkedList(int[] arr) {
    if (arr.length == 0) return null;                  // an empty list is just a null head
    ListNode head = new ListNode(arr[0]);
    ListNode mover = head;                             // always points at the current last node
    for (int i = 1; i < arr.length; i++) {
        ListNode temp = new ListNode(arr[i]);
        mover.next = temp;                             // link the old last node to the new one
        mover = temp;                                  // the new node is now the last one
    }
    return head;
}

Two things are worth noticing. First, head is created once and never moves; it is the handle we return. If we had advanced head instead of a separate mover, we would have lost the start of the list. Second, the first element needs special handling because there is no “previous node” to attach it to, which is why the function starts at index 1 after creating the head separately.

That special case disappears with a dummy node: a placeholder that sits in front of the real first node. Every element, including the first, is then “attached behind the current tail”, and the real head is dummy.next at the end.

static ListNode arrayToLinkedListWithDummy(int[] arr) {
    ListNode dummy = new ListNode(0);                  // placeholder that sits in front of the real head
    ListNode tail = dummy;
    for (int v : arr) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;                                 // skip the placeholder
}

The dummy-node pattern returns null for an empty array without any explicit check, because dummy.next was never assigned. You will meet this trick again and again whenever an algorithm builds a new list or might need to replace the head, for example when merging two sorted lists or removing nodes from the front.

Both versions run in O(n) time and allocate n nodes, so O(n) space.

Traversal

To visit every element, start a temporary reference at the head and keep moving it to next until it becomes null. The loop condition temp != null is what makes the empty list work for free.

static String traverse(ListNode head) {
    StringBuilder sb = new StringBuilder();
    ListNode temp = head;
    while (temp != null) {
        sb.append(temp.val).append(" -> ");
        temp = temp.next;
    }
    sb.append("null");
    return sb.toString();
}

For [1, 2, 3] the output is 1 -> 2 -> 3 -> null, and for the empty list it is just null. Use a temporary variable for walking, never head itself, otherwise the caller’s handle to the list is gone after one traversal.

The inverse operation, copying the values back into an array, needs the count first because a Java array has a fixed length. So it is two passes: count, allocate, fill.

static int[] toArray(ListNode head) {
    int n = 0;
    for (ListNode t = head; t != null; t = t.next) n++;
    int[] out = new int[n];
    int i = 0;
    for (ListNode t = head; t != null; t = t.next) out[i++] = t.val;
    return out;
}

The for (ListNode t = head; t != null; t = t.next) form is the idiomatic one-line traversal in Java. It reads like for (int i = 0; i < n; i++) and keeps the walking variable scoped to the loop.

Length and access by position

Counting nodes is the traversal with a counter. There is no cheaper way for a plain linked list: the length is not stored anywhere, so finding it costs O(n). (Classes such as java.util.LinkedList keep a size field up to date on every insert and delete precisely to avoid this.)

static int length(ListNode head) {
    int count = 0;
    for (ListNode t = head; t != null; t = t.next) count++;
    return count;
}

Access by position is where the array wins decisively. arr[i] is one memory read; the list has to follow index references, which is O(index) time. The loop below stops early when it falls off the end, and returns -1 for a position that does not exist.

static int get(ListNode head, int index) {
    if (index < 0) return -1;
    ListNode t = head;
    for (int i = 0; i < index && t != null; i++) t = t.next;
    return t == null ? -1 : t.val;
}

If your algorithm needs random access, a linked list is the wrong structure. The list pays off when you mostly work at the ends or at a node you already hold a reference to.

Nodes are references, not copies

In Java a variable of type ListNode holds a reference. Writing ListNode alias = head; does not copy the node; it gives the same node a second name. Any change made through alias is visible through head.

static boolean aliasingDemo() {
    ListNode head = new ListNode(1, new ListNode(2));
    ListNode alias = head;                             // a second name for the same node, not a copy
    alias.val = 99;
    alias.next = null;                                 // cuts the list down to one node
    return head.val == 99 && head.next == null && length(head) == 1;
}

This is why traversing with head = head.next destroys the caller’s view of the list, and also why pointer surgery works at all: when mover.next = temp runs inside arrayToLinkedList, it modifies the actual last node of the list, because mover and that node are the same object.

The flip side is that assigning to the variable changes nothing about the object. temp = temp.next moves our local reference forward; the node temp used to point at is untouched. Keep the two operations separate in your head: x.next = y edits the structure, x = y only moves a label.

Arrays versus linked lists

Operation Array Singly linked list
Access element i O(1) O(i)
Insert or delete at the front O(n) (shift everything) O(1)
Insert or delete after a node you hold O(n) O(1)
Insert at the back O(1) amortised with a dynamic array O(n) without a tail reference
Memory per element the value the value plus a reference and object header
Cache behaviour excellent, contiguous poor, nodes are scattered

The honest summary is that linked lists are rarely the fastest container in practice, but they are the simplest structure with cheap insertion and deletion in the middle, and the pointer manipulation they teach is the foundation for trees, graphs and every “rewire the links” interview problem that follows in this section.

Edge cases and pitfalls