Java: удалить все элементы из связанного списка

Question

В Java, как удалить все элементы в связанном списке без , используя уже доступный метод clear()? Это упражнение было вдохновлено вопросом, полученным в телефонном интервью.

Скажи, что я могу сделать это в C

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

Спасибо

Answer 1

Java имеет автоматическую сборку мусора, поэтому вам просто нужно установить для ссылки на голову значение 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 закрытым, мы можем просто выполнить первый фрагмент кода, который я разместил.

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, а не пользовательского класса связанного списка.

Answer 3

Чтение реального кода полезно. Я предлагаю вам взглянуть.

Для односвязного списка, который вы можете просто сделать как @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++;
}

Первое, что нужно отметить; это двусвязный список для прямого и обратного прохождения, и он агрессивно очищает все ссылки. Не уверен, почему он делает это, чтобы быть честным, потому что GC очистит их в любом случае, а 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;
}

Answer 4

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

или см. этот пример .