Java：删除链表中的所有元素

Question

在Java中，如何在不使用已有的clear()方法的情况下删除链表中的所有元素？这个问题是受到一次电话面试中的提问而启发的。

我可以在C语言中实现这个操作。

void DeleteAllElement( ListElement **head ) {  
    ListElement *deleteMe = *head;  
    while( deleteMe )  {  
        ListElement *next = deleteMe->next;  
        delete deleteMe;  
        deleteMe = next;  
    }  
    *head = NULL;  
}

谢谢

- SuperMan

---

将以下有关编程的内容从英语翻译成中文。只返回已翻译的文本：每行缩进4个空格以获取自动“代码”块。已经有一个工具可以做到这一点：选择这些行并单击“{}”图标。 - Uriah Carpenter

已删除我的答案，但真的，为什么不使用 clear() 呢？这就是它存在的意义。何必重新发明轮子呢？ - squawknull

因为我在电话面试中被问到了。 - SuperMan

他们更有可能在寻找bdares的答案。 - Adisesha

Answer 1

Java具有自动垃圾回收功能，所以您只需要将Head引用设置为null即可：

myList.headNode = null;

假设我们有一个名为LinkedList的类，它还有一个resetList函数...

public class LinkedList{
     private Node head;
     public Node find(Key k){ ... }
     public void add(Node n){ ... }
     ...
     public void reset(){ head = null;}
     public static void reset(LinkedList l){l.reset();}
}

如果我们不将 head 节点设为私有，我们可以直接执行我发布的第一个代码片段。

- user684934

---

你需要将列表的引用设置为null，而不是传递的引用。DeleteAllElement应该接受列表，而不是头节点，并将列表的头设置为null。否则，实际列表会保留对现有头的引用。 - user684934

你能否在回答中以代码形式表达措辞，这样我就可以接受它吗？ - SuperMan

Answer 2

如果您正在谈论的是 java.util.LinkedList 的一个实例：

    while (!linkedlist.isEmpty()) {
        linkedlist.removeFirst();
    }

如果您在谈论任何java.util.List的实例：

    while (!list.isEmpty()) {
        list.remove(0);
    }

考虑到remove是可选操作，但是根据列表的实现方式，这可能会非常低效。对于ArrayList来说，以下方法更好：

    while (!list.isEmpty()) {
        list.remove(list.size() - 1);
    }

另一种选择是迭代列表并在每个元素上调用Iterator.remove()，这也是一个可选操作。（但再次强调，对于某些列表实现而言，这可能极其低效。）

如果您正在谈论自定义链表类，则答案取决于您声明列表类的内部数据结构的方式。

---

我怀疑如果面试官提到了clear()方法，他们期望在标准Java集合框架的上下文中得到答案，而不是自定义链表类。

- Stephen C

Answer 3

for(i=0;i<linkedlist.size;i++){
  linkedlist.removeFirst();
}

或者查看这个示例。

- Nirmal- thInk beYond

Answer 4

阅读实际代码是有用的。我建议你看一下。

对于单向链表，你可以像@bdares建议的那样，在查看java.util.LinkedList的实际代码时，答案会有所不同（这是大多数开发人员使用的）。

public void clear() {
    Entry<E> e = header.next;
    while (e != header) {
        Entry<E> next = e.next;
        e.next = e.previous = null;
        e.element = null;
        e = next;
    }
    header.next = header.previous = header;
    size = 0;
    modCount++;
}

首先需要注意的是，这是一个双向链表，可以进行前向和后向遍历，并且它会积极地清除所有引用。说实话，我不确定为什么要这样做，因为垃圾回收器无论如何都会清除这些引用，而modCount将会在另一个线程中检测到任何更改。事实上，它应该先执行modCount。

相比之下，这里是ArrayList.clear()的代码：

public void clear() {
    modCount++;

    // Let gc do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

- Peter Lawrey

---

“不确定为什么会这样…”- 简短回答：代际垃圾回收。如果老一代中的列表节点引用了年轻一代中的节点，则前者会防止后者被年轻一代收集器回收。这可能导致无法访问的列表节点大量存活。积极的空值避免了这种情况。 - Stephen C

（关联的列表元素...可能比节点更重要。） - Stephen C

Answer 5

关于链表中节点之间的链接清除，有几个关键点需要注意：

分代垃圾回收：

一些垃圾回收器，包括分代垃圾回收器，在对象从所有引用中清除时可以更高效地工作。分代垃圾回收器根据对象的年龄将其分为不同的代。

断开节点之间的所有链接有助于处理废弃节点可能存在于多个代的情况。通过断开所有连接，可以确保这些节点可以更有效地被回收。

迭代器的可达性：

清除节点之间的链接可以确保即使存在可达的迭代器或其他引用，节点本身也不能通过链表结构可达。这保证了节点可以被垃圾回收。

在某些情况下，对象可能通过迭代器或其他外部引用间接地被引用，断开内部链接有助于确保节点不会因为这些外部引用而在内存中保留。

在实际应用中，是否清除节点之间的所有链接取决于您的应用程序的具体要求和特性。如果您确信没有外部引用持有节点，出于性能原因，您可以考虑省略此步骤。然而，如果您希望在复杂情况下确保内存被回收，清除所有链接可能是一种保守且安全的方法。因此，在我看来，即使您有一个单链表，在程序的任何文件中，如果存在一个变量直接或间接地引用了someRaddomVarible = head.next.next.next;，那么即使您将head和tail设置为null，someRaddomVarible仍然是可访问的，并且与链接（直接或间接地）相连，这将导致GC不会删除RAM中连接的（直接或间接地）对象，因此我认为对于任何类型的链表，O(n)的时间复杂度更好。

单链表：

public void clear() {

    // Disconnect all links between nodes

    LinkedListNode current = head;

    while (current != null) {

        LinkedListNode next = current.next;

        current.next = null;

        current = next;

    }

    

    // Set head to null

    head = null;

}

循环链表：

public void clear() {

    if (head == null) {

        return; // Empty list

    }

    // Disconnect all links between nodes

    LinkedListNode current = head;

    do {

        LinkedListNode next = current.next;

        current.next = null;

        current = next;

    } while (current != head);

    

    // Set head to null

    head = null;

}

双向链表：

public void clear() {

    // Disconnect all links between nodes

    LinkedListNode current = head;

    while (current != null) {

        LinkedListNode next = current.next;

        // For doubly linked lists

        current.prev = null;

        current.next = null;

        current = next;

    }

    

    // Set head and tail to null

    head = null;

    // For doubly linked lists

    tail = null;

}

循环双向链表：

public void clear() {
    // Disconnect all links between nodes
    LinkedListNode current = head;
    while (current != null) {
        LinkedListNode next = current.next;
        // For doubly linked lists
        current.prev = null;
        current.next = null;
        current = next;
    }
    
    // Set head and tail to null
    head = null;
    // For doubly linked lists
    tail = null;
}

- chirag patel