1

我在 Java 中做了一些练习，现在我遇到了这样一个问题——我的列表工作不正确。我确信它remove工作不正确，也许你可以帮助我（通过建议或代码）以正确的方式实现循环单链表。我不确定其他功能是否正常工作，但我已尽力做到最好。

这是我的代码：

import java.util.*;


public class Node {
    private Object value;
    private Object nextValue;

    private Node next;


    public Node(int data) {
        this.value = data;
        this.next = null;
    }

    public Object getValue() {
        return this.value;
    }

    public Node nextItem() {
        return this.next;   
    }

    public void setNextItem(Node nextItem) {
        this.next = (Node) nextItem;
        this.next.setValue(nextItem.getValue());
    }


    public void setValue(Object arg0) {
        this.value = arg0;
    }

}

    -------------------------------------------------------------------

   import java.util.*;



public class CircularList  {
    private Object[] array;
    private int arrSize;
    private int index;
    private Node head;
    private Node tail;
    public CircularList() {
        head = null;
        tail = null;
    }



    public boolean add(Node item) {

        if (item == null) {
            throw new NullPointerException("the item is null!!!");
        }


        if (head == null) {
            head = item;
            head.setNextItem(head);
            arrSize++;

            return true;
        } 

        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == item.getValue()) {
                throw new IllegalArgumentException("the element already " +
                        "exists!");
            }
            cur = cur.nextItem();
        }

            head.setNextItem(item);
            item.setNextItem(head);
            arrSize++;

            return true;

    }


    public Node getFirst() {
        return head;
    }


    public void insertAfter(Node item, Node nextItem) {

        if ((item == null) || (nextItem == null)) {
            throw new NullPointerException("the item is nul!!!");
        } else if (this.contains(nextItem) == true) {
            throw new IllegalArgumentException("the item already exists!");
        } 

        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == item.getValue()) {
                nextItem.setNextItem(item.nextItem());
                item.setNextItem(nextItem);
            } else {
                cur = cur.nextItem();
            }
        }

    }


    public boolean remove(Node item) {

        if(item == head) {
            Node cur = head;
            for(int i = 0; i < arrSize-1; i++) {
                cur = cur.nextItem();
            }

            head = head.nextItem();

            for(int i = 0; i < arrSize; i++) {
                cur = cur.nextItem();
            }
            arrSize--;
            return true;
        }

        Node cur = head;
        int counter = 0;
        while(cur.nextItem() != head) {
            if(cur == item) {
                item = null;
                cur = cur.nextItem();
                while(cur.nextItem() != head) {
                    cur.setNextItem(cur.nextItem().nextItem());
                }
            return true;    
            }
            cur = cur.nextItem();
        }



        return false;
    }

    public int size() {

        return arrSize;
    }

    public boolean contains(Object o) {
        if ((o == null) && (arrSize == 0)) {
            return false;
        }
        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == o) {
                return true;
            }
            cur = cur.nextItem();
    }


        return false;
    }



}
4

3 回答 3

0

其中许多算法可能更简单。

例子：

  public boolean remove(Node item) {
     Node current = head;
     for(int i = 0; i < size; i++) {
       if (current.getNext() == item) {
          current.next = current.getNext().getNext();
          size --;
          return true;
       }
       current = current.getNext()
     }
     return false;
  }
于 2012-03-05T20:02:37.577 回答
0

除了列表之外，这里还有很多问题。您似乎正在将您的节点与 == 进行比较。此代码将输出“不匹配”。

Node n1 = new Node(5);
Node n2 = new Node(5);
if (n1 == n2)
  System.out.println("objects match");
else
  System.out.println("no match");

在 add() 中，看起来列表中只能有两个项目，所以

head.setNextItem(item);
item.setNextItem(head);

应该是这样的：

cur.setNextItem(item);
item.setNextItem(head);
于 2012-03-05T20:44:53.117 回答
0

您的代码中发生了很多事情，这里有一些建议：

  1. 在您的 Node 类中： Java 命名约定：与 setter 应以“set”为前缀的方式相同，getter 应以“get:”为前缀nextItem()实际上应该是getNextItem().

  2. 同样在您的 Node 类中：据我所知，链表节点的“下一个值”字段通常是对列表中下一个节点的引用，因此应该是 type Node，而不仅仅是任何 Object。它应该按照您的方式工作，但是使用显式类型会更安全。（如果使用“对象”确实是构造链表下一个节点的常用方法，请纠正我。）

  3. 在第一种情况下remove()，当删除头时：您正在遍历列表以到达最后一个值，大概是将其“下一个值”重置为新头，但您实际上并没有这样做。你想要这样的东西：

    if (item == head) {
head = head.nextItem();
for(int i = 0; i < arrSize-1; i++){
cur = cur.nextItem();            
}
}
cur.setNextItem(head);

    我不确定您希望通过第二个循环完成什么。

  4. 在第二种情况下remove()：我不确定您要对第二个while循环做什么-重置整个列表中的所有链接？链表的全部意义在于让它变得不必要。删除链表中的节点实际上并不会删除该对象（因此您不必设置item为null）。相反，您只需“绕过”不需要的对象并“忽略”它，有效地将其从列表中删除，如下所示：

原名单：

[ Value: A; Next: B ] --> [ Value: B; Next: C ] --> [ Value C; Next: D ] ...

删除节点 B 后：

  [ Value: A; Next: C ] --> [Value C; Next: D ] ...

[ Value: B; Next: C ]仍然存在于内存中，但没有任何东西指向它，所以它会在下一个垃圾回收周期中被移除。

实现元素：当您遍历列表时，请保留对您访问的上一个节点的引用。然后，一旦你找到你正在寻找的项目（使用正确的比较，如 Thomas 所述），你可以简单地设置prev.setNextItem(cur.nextItem());（警告：未经测试的代码）：

    Node prev = head;
    Node cur;
    while ((cur = prev.nextItem()) != head) {
    if (cur.equals(item)) {
    prev.setNextItem(cur.getNextItem());
    return true;
    }
    }

我希望这些提示可以帮助您走上正确的道路。

于 2012-03-05T21:10:15.770 回答