我正在研究使用“桶”的(双)链表实现。简而言之,一个双向链表的节点,每个节点都持有一个由参数指定的集合大小的 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) 似乎多次添加指定的对象,直到它填满列表。所以我的节点原来包含元素:
一个,一个,一个
提前感谢您查看我的代码。
最佳答案
您的部分问题在于打印列表内容的逻辑,部分问题在于您的添加方法。首先,您当前的节点是 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());
}
}
}
关于java - ArrayList add() 方法行为怪异?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20344851/