循环单链列表

我用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;
    }

}

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

示例：

  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;
  }

除了列表之外，还有各种各样的问题。您似乎在将节点与==进行比较。此代码将输出"不匹配"。

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);

您的代码中有很多内容，下面是一些建议：

在Node类中：Java命名约定：与setter应该以"set"为前缀的方式相同，getter也应该以"get"为前缀：nextItem()实际上应该是getNextItem()。
同样在Node类中：据我所知，链表节点的"下一个值"字段通常是对列表中下一个Node的引用，因此应该是Node类型，而不仅仅是任何Object。它应该按照现有的方式工作，但使用显式键入要安全得多。（如果使用"Object"确实是构造链表下一个节点的常用方法，请更正我。）
在remove()的第一种情况下，当移除头时：你正在循环列表以达到最后一个值，可能是为了将其"下一个值"重置为新的头，但你实际上并没有这么做。你想要这样的东西：
```
if (item == head) {
head = head.nextItem();
for(int i = 0; i < arrSize-1; i++){
cur = cur.nextItem();            
}
}
cur.setNextItem(head);
```
我不确定你希望通过第二个循环实现什么。
在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 ]仍然存在于内存中，但没有任何东西指向它，因此它将在下一个垃圾收集周期中被删除。

Implement：在浏览列表时，保留对您访问过的上一个节点的引用。然后，一旦你找到了你要找的项目（使用正确的比较，正如托马斯所指出的），你可以简单地设置prev.setNextItem(cur.nextItem());（注意：未测试的代码）：

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

我希望这些建议能帮助你走上正确的道路。

相关内容

最新更新

热门标签：