java - ArrayList add() 方法行为怪异？

Question

我正在研究使用“桶”的(双)链表实现。简而言之，一个双向链表的节点，每个节点都持有一个由参数指定的集合大小的 ArrayList。

我已经初始化了我的节点并像这样列出:

public class MyLinkedList<T> implements ADTListInterface<T> {

ArrayList<T> list;

private class Node {

    T value;
    Node next;
    Node previous;
    ArrayList<T> list;

    public Node(Node n, Node p) {

        list = new ArrayList<T>(bucketSize);
        next = n;
        previous = p;
    }
}

private Node head;
private Node tail;
private int bucketSize;

public MyLinkedList(int bucketSize) {

    this.bucketSize = bucketSize;
    head = tail = new Node(null, null);

}

我已经设置了这样的添加方法:

    public void add(T o) {

    Node current = head;

    while (current.list.add(o) != true) {

        if (current.next != null) {

            current = current.next;
        }

        if (current.next == null) {

            current.next = new Node(null,current);
        }
    }
}

当使用 bucketSize = 3 和以下命令测试 add 方法时:

list.add("a");
list.add("b");
list.add("c");

我希望头节点包含一个列表，其元素和顺序如下:

c,b,a

但是，行:current.list.add(o) 似乎多次添加指定的对象，直到它填满列表。所以我的节点原来包含元素:

一个，一个，一个

提前感谢您查看我的代码。

Answer 1

您的部分问题在于打印列表内容的逻辑，部分问题在于您的添加方法。首先，您当前的节点是 add 方法的局部变量。这意味着第二个“if”语句:

if (current.next != null) {

            current = current.next;
}

没有做任何有用的事情。您将 current 设置为指向与 current.next 相同的对象，但随后您离开该方法并且您的引用被销毁。这没有意义。

假设您调用了列表的构造函数，然后添加了三个元素:“a”、“b”、“c”这是您的 Node 对象在堆上的行为方式。

构造函数完成后，堆上有一个 Node 对象，如下所示:{ list -> {empty}, prev -> null, next -> null } 这个对象被 head 和 tail 引用变量引用。请注意，如果您调用 new ArrayList(bucketSize)，它将创建具有“bucketSize”初始容量的空列表。

第一次调用 add("a") 后:

nodeObject#1 : { list -> {"a"}, prev -> null, next -> nodeObject#2 }

nodeObject#2 : { list -> {empty}, prev -> nodeObject#1, next -> null}

nodeObject#1 可以通过 head 或 tail 访问。nodeObject#2 可通过 head.next 或 tail.next 访问。

第二次调用 add("b") 后:

nodeObject#1 : { list -> {"a","b"}, prev -> null, next -> nodeObject#2 }

nodeObject#2 : { list -> {empty}, prev -> nodeObject#1, next -> null}

在第 3 次调用 add("c") 之后:

nodeObject#1 : { list -> {"a","b","c"}, prev -> null, next -> nodeObject#2 }

nodeObject#2 : { list -> {empty}, prev -> nodeObject#1, next -> null}

在您的节点中也有 prev 和 next 建议您的列表应该是双向的，这意味着您需要实现 add_at_the_end 和 add_at_the_beginning 之类的方法，但这是另一回事(如果需要，我也可以展示一些示例)。下一个问题是为什么使用 ArrayList 作为 Node 类字段。 T值应该足够了。

这是我在没有 ArrayList 的情况下实现简单列表的示例。有返回迭代器实例的迭代器方法，可用于显示列表的元素。

package com.playground;

import java.util.ArrayList;
import java.util.Iterator;

class CustomList<T>{
    private class Node{
        Node prev;
        Node next;

        T value;
        Node(T rVal, Node p, Node n){
            this.value = rVal;
            this.prev = p;
            this.next = n;
        }
        void setNext(Node n){ this.next = n; }
        void setPrev(Node p){ this.prev = p; }
    }

    private Node head;
    private Node tail;



    public void add(T element) {
        if(tail == null && head == null){
            head = new Node(element, null,null);
            tail = head;
        }
        else{
            Node tmp = new Node(element, tail, null);
            tail.setNext( tmp );
            tail = tmp;
        }

    }

    public Iterator<T> iterator() {

        return new Iterator<T>(){
            Node current = head;
            @Override
            public boolean hasNext() {
                // TODO Auto-generated method stub
                return current != null;
            }

            @Override
            public T next() {
                Node tmp = current;
                current = tmp.next;
                return tmp.value;
            }

            @Override
            public void remove() {
                // TODO Auto-generated method stub

            } };
    }

}

public class CustomListTest {
    public static void main(String [] args){
        CustomList<String> list = new CustomList<String>();
        list.add("my");
        list.add("custom");
        list.add("list");       

        Iterator<String> forwardIterator = list.iterator();
        while( forwardIterator.hasNext()){
            System.out.println( forwardIterator.next());
        }

    }
}