Java双向链表String列表执行超时问题求助

运行代码时出现超时情况，无任何错误提示。使用String类型的DoublyLinkedList时所有方法无法正常工作，但测试int类型列表时运行正常。

问题代码 #

泛型双向链表实现 #

public class DoublyLinkedList<E> {
    private static class Node<E> {
        private E element;
        private Node<E> prev;
        private Node<E> next;
        
        public Node(E e, Node<E> p, Node<E> n) {
            this.element = e;
            this.prev = p;
            this.next = n;
        }
        
        public E getElement() {
            return element;
        }
        public Node<E> getPrev() {
            return this.prev;
        }
        public Node<E> getNext() {
            return this.next;
        }
        public void setPrev(Node<E> p) {
            this.prev = p;
        }
        public void setNext(Node<E> n) {
            this.next = n;
        }
    }
    
    private Node<E> header;
    private Node<E> trailer;
    int size;
    
    public DoublyLinkedList() { 
        this.header = new Node<>(null, null, null);
        this.trailer = new Node<>(null, this.header, null);
        this.header.setNext(this.trailer);
    }
    
    public int size() {
        return this.size;
    }
    public E first() {
        if (isEmpty()) {
            return null;
        }
        return this.header.next.getElement();
    }
    public E last () {
        if (isEmpty()) {
            return null;
        }
        return this.trailer.prev.getElement();
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public void addFirst (E e) {
        addBetween(e, this.header, this.header.getNext());
    }
    public void addLast (E e) {
        addBetween(e, this.trailer.getPrev(), this.trailer);
    }
    private void addBetween(E e, Node<E> predecessor, Node<E> successor) {
        Node<E> newest = new Node<>(e, predecessor, successor);
        predecessor.setNext(newest);
        successor.setPrev(newest);
        this.size++;
    }
    public E removeFirst() {
        if (this.isEmpty()) {
            return null;
        }
        return this.remove(header.getNext());
    }
    public E removeLast() {
        if (this.isEmpty()) {
            return null;
        }
        return this.remove(trailer.getPrev());
    }
    public E remove(Node<E> e) {
        e.next.setPrev(e.prev);
        e.prev.setNext(e.next);
        this.size--;
        return e.getElement();
    }
    public String toString() {
        StringBuilder sb = new StringBuilder("(");
        Node<E> walk = this.header.next;
        while (walk != this.trailer) {
            sb.append(walk.element);
            if (walk.next != this.trailer)
                sb.append(", ");
            walk = walk.next;
        }
        sb.append(")");
        return sb.toString();
    }
    
    public void add(int index, E element) {
        Node<E> pred = header;
        Node<E> succ = pred.getNext();
        int count = 0;
        while(succ != null) {
            if(count == index) addBetween(element, pred, succ);
            count++;
            pred = pred.getNext();
            succ = succ.getNext();
        }
    }
    
    public void add(E e) {
        add(size, e);
    }
    
    public void clear() {
        while(!isEmpty()) {
            removeFirst();
        }
    }
    
    public E get(int index) {
        if (isEmpty()) return null;
        Node<E> current = header;
        int count = 0;
        while(current != null) {
            if(count == index) return current.getElement();
            count++;
            current = current.getNext();
        }
        return null;
    }
    
    public E set(int index, E element) {
        if(isEmpty()) return null;
        Node<E> current = header;
        E returnVal = null;
        int count = 0;
        while(current != null) {
            if(count == index) {
                if(count == 0) {
                    returnVal = get(0);
                    removeFirst();
                    add(0, element);
                }
                else if(count == size) {
                    returnVal = get(size);
                    removeLast();
                    add(size, element);
                }
                else {
                    returnVal = get(index);
                    remove(current);
                    add(index, element);
                }
            }
        }
        return returnVal;
    }
}

测试代码 #

package labs;

public class DoublyLinkedListDemo {
    
    public static void main(String[] args) {
        //testing methods on a String DoublyList
        DoublyLinkedList<String> stringList = new DoublyLinkedList<>();
        stringList.addFirst("Strawberry");
        stringList.addFirst("Banana");
        stringList.addFirst("Apple");
        stringList.set(0, stringList.get(1));
        System.out.println(stringList);
        stringList.add(1, "Pear");
        System.out.println(stringList);
        stringList.add("Blueberry");
        System.out.println(stringList);
        System.out.println(stringList.get(1));
        stringList.clear();
        System.out.println(stringList);
        System.out.println(stringList.set(0, stringList.get(1)));
        System.out.println(stringList.get(0));
    }
}

问题根源 #

1. 无限循环导致超时：set方法中的while循环未在每次迭代中移动current指针或递增count变量，一旦进入循环就会无限执行，直接引发超时。
2. get方法逻辑错误：将哨兵节点header当作index=0的元素返回，而header的element始终为null，导致获取元素时返回错误值。
3. set方法逻辑冗余且错误：无需通过删除再添加的方式修改元素，且错误地处理了count == size的无效场景（set操作仅能修改已存在的元素，index范围应为0 <= index < size）。

修复方案 #

修复get方法 #

修正遍历起点，添加index合法性检查：

public E get(int index) {
    if (isEmpty() || index < 0 || index >= size) {
        return null;
    }
    Node<E> current = header.next;
    int count = 0;
    while (current != trailer) {
        if (count == index) {
            return current.getElement();
        }
        count++;
        current = current.getNext();
    }
    return null;
}

修复set方法 #

移除冗余逻辑，直接修改节点元素，添加循环退出逻辑和合法性检查：

public E set(int index, E element) {
    if (isEmpty() || index < 0 || index >= size) {
        return null;
    }
    Node<E> current = header.next;
    int count = 0;
    while (current != trailer) {
        if (count == index) {
            E oldValue = current.getElement();
            current.element = element; // 直接修改节点元素，无需删除再添加
            return oldValue;
        }
        count++;
        current = current.getNext();
    }
    return null;
}

优化add方法（可选） #

添加index合法性检查，避免无效遍历：

public void add(int index, E element) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
    }
    Node<E> pred = header;
    Node<E> succ = pred.getNext();
    int count = 0;
    while (count < index) {
        pred = pred.getNext();
        succ = succ.getNext();
        count++;
    }
    addBetween(element, pred, succ);
}

修复后预期输出 #

(Banana, Banana, Strawberry)
(Banana, Pear, Banana, Strawberry)
(Banana, Pear, Banana, Strawberry, Blueberry)
Pear
()
null
null

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