java - 在 LinkedList 中实现 AddAtIndex 方法

Question

目前，我正在努力实现 AddAtIndex 方法，并且在大多数情况下它似乎工作正常。但是，我的方法没有通过 JUnit 测试，我似乎无法理解为什么。因此，我选择展示到目前为止我所做的代码:

**
     * Add an element to the list at the specified index
     * @param The index where the element should be added
     * @param element The element to add
     */
    public void add(int index, E element ) //Method should be O(1) time.
    {
        // TODO: Implement this method
        if (index < 0) { 
            System.out.println("Can't add an element at a negative index.");
        }
        int i = 0;
        LLNode<E> currentNode = head.next;
        while ( i < size ) {
            if ( i == index ) {
                LLNode<E> newNode = new LLNode<E>(element);
                LLNode<E> tempNode = new LLNode<E>(currentNode.data);

                currentNode.next = tempNode;
                currentNode.data = newNode.data;

                newNode.prev = currentNode.prev;
                newNode.next = tempNode;
                tempNode.prev = newNode;
                size++;
            }
            currentNode = currentNode.next;
            i++;
        }

    }

我的代码背后的思考过程是，该方法创建一个新的 Node，然后替换链表指定索引处的数据。然而，它所替换的节点处的数据存储在临时节点中，该临时节点的位置递增到新节点之后的下一个节点。尽管代码看起来有点草率，但我对自己的实现有大约 80% 的信心。我创建了一个驱动程序来演示实现。驱动代码如下:

public class LinkedListDriver {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyLinkedList<String> nameList = new MyLinkedList<String>();
        nameList.add("Hamadi");
        nameList.add("Ballo");
        nameList.add(1, "Salisu");
        nameList.add(2, "Galo");
        System.out.println(nameList.toString());
        System.out.println(nameList.size());
        nameList.set(2, "Abdullahi");
        System.out.println(nameList.toString());
        nameList.remove(1);
        System.out.println(nameList.toString());
        MyLinkedList<Integer> list1 = new MyLinkedList<Integer>();
        list1.add(65);
        list1.add(21);
        list1.add(42);
        System.out.println(list1.toString());
        list1.remove(0);
        System.out.println(list1.toString());
    }

}

驱动程序的输出如下:

List: Hamadi, Salisu, Galo, Ballo, 
4
Replacing Galo with Abdullahi
List: Hamadi, Salisu, Abdullahi, Ballo, 
Removing Salisu from the list
List: Hamadi, Abdullahi, Ballo, 
List: 65, 21, 42, 
Removing 65 from the list
List: 21, 42, 

单元测试失败，但出现以下错误:

AssertEquals 方法失败:

shortList.add(2, "E");
        shortList.add(3, "F");
        **assertEquals("AddAtIndex: at position 2 ", "E", shortList.get(2)); //fails here**
        assertEquals("AddAtIndex: at position 3 ", "F", shortList.get(3));
        assertEquals("AddAtIndex: List size is ", 6, shortList.size());

我想知道我做错了什么。我已经完全弄清楚了这一点，尽管我知道我的 AddAtindex 方法有点不对劲。谢谢!

Answer 1

您不需要那个tempNode。只需创建 newNode 并将其正确插入到 currentNode 与其前一个节点之间。

您还应该考虑在列表的开头(无上一个)或结尾(无下一个)添加元素的可能性。