Java中如何获取LinkedList的Node引用以实现O(1)删除？

Great question! This is a common pain point with Java's standard LinkedList—it fully encapsulates its internal Node implementation, so there are no public APIs that let you directly get a reference to a Node object, including the getLastNode() method you imagined in your code. The internal Node class is marked as private static, and all operations that manipulate nodes are handled internally or via indirect tools like ListIterator (which doesn't let you hold onto a Node reference long-term).

Why doesn't the standard library expose Nodes? #

The Java team designed it this way to preserve the encapsulation and structural integrity of the LinkedList. If external code could directly modify a Node's prev or next pointers, it would be trivial to corrupt the list's state (e.g., creating cycles, orphaning nodes, or breaking size tracking). This would lead to unpredictable bugs that are hard to debug.

How to achieve O(1) removal with node references? #

Since the standard library won't help here, you have a few solid options:

1. Implement your own doubly linked list

This is the most straightforward solution. You can create a simple linked list that exposes its Node class (or provides methods to retrieve Node references) and supports O(1) removal via direct Node pointers. Here's a minimal example:

public class CustomLinkedList<E> {
    // Expose the Node class (or make it package-private if you prefer)
    public static class Node<E> {
        private E item;
        private Node<E> next;
        private Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }

        public Node<E> getPrevious() {
            return prev;
        }

        public Node<E> getNext() {
            return next;
        }

        public E getItem() {
            return item;
        }
    }

    private Node<E> first;
    private Node<E> last;
    private int size;

    // Add an element to the end and return its Node reference
    public Node<E> addLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
        return newNode;
    }

    // O(1) removal using a Node reference
    public void remove(Node<E> node) {
        if (node == null) throw new NullPointerException();

        final Node<E> prev = node.prev;
        final Node<E> next = node.next;

        // Adjust pointers for the previous node
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            node.prev = null;
        }

        // Adjust pointers for the next node
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            node.next = null;
        }

        // Clear the item reference to help garbage collection
        node.item = null;
        size--;
    }

    // Add other utility methods as needed (addFirst, getFirst, etc.)
    public int size() {
        return size;
    }
}

You can use this custom list like so:

public class Main {
    public static void main(String[] args) {
        CustomLinkedList<String> test = new CustomLinkedList<>();
        test.addLast("first");
        test.addLast("second");
        CustomLinkedList.Node<String> thirdNode = test.addLast("third");
        test.addLast("fourth");
        
        // Get the second node via thirdNode's previous reference
        CustomLinkedList.Node<String> secondNode = thirdNode.getPrevious();
        
        // O(1) removal of the third node
        test.remove(thirdNode);
        System.out.println(test.size()); // Outputs 3
    }
}

2. Third-party libraries (limited options)

Most mainstream Java libraries avoid exposing Node references for the same encapsulation reasons as the standard library. However, if you're set on using a pre-built solution, some specialized collections libraries (like those for high-performance computing) might offer this functionality. That said, custom implementation is almost always simpler and more maintainable for this specific use case.

内容的提问来源于stack exchange，提问作者Dost Arora