如何在 LinkedList 实现中的指定索引处添加节点

Question

所以我从头开始实现一个 LinkedList，其中一个方法 insertAt(int index, T elem) 确实让我很头疼。该方法应该在指定索引处插入一个节点并相应地移动列表的其余部分。我的实现似乎只是复制和粘贴现有节点。对我做错了什么有帮助吗？（以下用例）

如果包含界面说明或完整的内容，请告诉我 class:

public class LinkedList<T> implements ListInterface<T> {

private Node<T> first;
private Node<T> last;
private int counter;

public LinkedList() {
}

@Override
public ListInterface<T> insertAt(int index, T elem) {
    if(index > counter) {
        throw new IndexOutOfBoundsException();
    }
    Node<T> node = new Node<T>(null, elem, null);
    if(counter == 0) {
        first = last = node;
    }
    else {
        if(index == 0) {
            node.next = first;
            first.prev = node;
            first = node;
        }
        else if(index  == counter) {
            node.prev = last;
            last.next = node;
            last = node;
        }
        else {
            Node<T> current = this.first;

            for(int i = 0; i < index; i++) {
                current = current.next;
            }
            node.next = current;
            node.prev = current.prev;
            current.prev.next = node;
        }
    }
    counter++;
    return this;
}

节点Class:

public class Node<T> {

public T data;
public Node<T> next;
public Node<T> prev;

public Node(Node<T> prev, T data, Node<T> next){
    this.data = data;
    this.next = next;
    this.prev = prev;
}

public Node() {

}

用法示例 #1（错误答案）：

      LinkedList<String> list = new LinkedList <String>();
      list.insertFirst("p");
      list.insertFirst("a");
      list.insertFirst("e");
      list.insertFirst("h");

      list.insertAt(2, "A");

控制台：

之前：{h, e, a, p}

之后：{h, e, e, a, p}

控制台应该是什么：

之前：{h, e, a, p}

之后：{h, e, A, a, p}

Answer 1

current.prev = node; 你丢了这个而 0 < index < counter

我测试了你的代码，似乎有效：

public class LinkedList<T> {
    private Node<T> first;
    private Node<T> last;
    private int     counter;

    public LinkedList() {
    }

    public static void main(String args[]) {
        LinkedList<String> list = new LinkedList<String>();
        list.insertFirst("p");
        list.insertFirst("a");
        list.insertFirst("e");
        list.insertFirst("h");

        list.insertAt(2, "A");
        for (Node n = list.first; n != null; n = n.next) {
            System.out.println(n.data);
        }
    }

    private void insertFirst(T s) {
        insertAt(0, s);
    }

    public LinkedList<T> insertAt(int index, T elem) {
        if (index > counter) {
            throw new IndexOutOfBoundsException();
        }
        Node<T> node = new Node<T>(null, elem, null);
        if (counter == 0) {
            first = last = node;
        } else {
            if (index == 0) {
                node.next = first;
                first.prev = node;
                first = node;
            } else if (index == counter) {
                node.prev = last;
                last.next = node;
                last = node;
            } else {
                Node<T> current = this.first;

                for (int i = 0; i < index; i++) {
                    current = current.next;
                }
                node.next = current;
                node.prev = current.prev;
                current.prev.next = node;
                current.prev = node;
            }
        }
        counter++;
        return this;
    }
}

class Node<T> {

    public T       data;
    public Node<T> next;
    public Node<T> prev;

    public Node(Node<T> prev, T data, Node<T> next) {
        this.data = data;
        this.next = next;
        this.prev = prev;
    }

    public Node() {

    }
}

如何在 LinkedList 实现中的指定索引处添加节点

How to add a node at specified index in LinkedList implementation

java

implementation

list