Как удалить определенное значение из связанного списка java?

Question

public class LinkList 
{ 
private Node list; 
private int count; // number of values stored in the list 

public LinkList(){ 
    list = null; 
    count = 0; 
    } 

// Returns number of values in the LinkList 
public int count() { 
    return count; 
} 



/* 
* delete all nodes with this value 
* if the count is zero do nothing 
* if count is 1 delete front node (can use front() and ignore return) 
* else travel the list and when found make prev.next cur.next ... return 
* if still in method delete rear node. 
* 
*/ 


public void deleteNode(int value) 
{ 

    } 


} 


public class Node{ 

int value; 
Node next; 

public Node() { 
    next=null; 
} 

public Node(int n, Node nextNode){ 
    setValue(n); 
    setNext(nextNode); 
} 

public int getValue(){ 
    return value; 
} 

public void setValue(int n){ 
    value = n; 
} 

public Node getNext(){ 
    return next; 
} 

public void setNext(Node node){ 
    next = node; 
} 

public boolean equals(Node other) { 
    return (this.getValue() == other.getValue()); 
} 

public String toString() { 
    return "" + value; 
} 

} 

Answer 1

Вы хотите пересечь связанный список, пока значение не равно нулю. Если вы встретите значение, которое вы пытаетесь удалить, удалите узел, переработайте ссылки и вернитесь. Ваша функция должна выглядеть так:

public void deleteNode(int value) 
{ 
    if(count == 0) { 
     return; 
    } else if (count == 1){ 
     // delete this node. I'm not quite sure what you mean by use front() in your instruction 
    } else { 
     Node x = Node first; // This should be the first node in the list 
     while(x != null && x.next != null) { 
      if(x.value == value) { 
       if(x == first) { 
        first = x.next; // If your first node is bad, make 2nd node your first node 
       } else { 
        prev.next = x.next; // This skips the current node, with the sought-after value 
       } 
      } else { 
       x = x.next; // Traverse to check the next node 
      } 
     } 
    } 
} 

Следует помнить, что вам необходимо объявить предыдущий и первый узлы в вашем классе узлов. Не думайте, что я видел тех, которые определены в данном коде.

Answer 2

Во-первых, используйте существующую реализацию Java ArrayList. Он находится в O(n) линейном времени для большинства операций, причем некоторые даже являются O(1). Он также прекрасно сочетается с коллекциями, итераторами и наборами.

Вместо этого я бы рекомендовал использовать список с двойной связью. Просто добавьте поле previous с необходимыми геттерами и сеттерами.

Затем, чтобы удалить, просто соедините предыдущие и следующие вокруг корневого узла. Это значит, что это упражнение для читателя. (или найти его в истории изменений) Это просто связывает ссылки вокруг выбранного в данный момент узла.

Если вы хотите использовать односвязный список, вам необходимо пройти через список и проверить, является ли следующий узел, который вы хотите удалить. Затем вы устанавливаете следующий из текущего узла nextNode.getNext().

Этот последний метод будет весьма неэффективным.

Answer 3

    +------+  +------+  +------+ 
        |  |  |  |  |  | 
      Step 0 |  |+------>|  |+------>|  | 
        |  |  |  |  |  | 
        |  |  |  |  |  | 
        +------+  +------+  +------+ 

           +----------------+ 
        +------+ | +------+ | +------+ 
        |  |+--+ |  | +-->|  | 
      Step 1 |  |  |  |+------>|  | 
        |  |  |  |  |  | 
        |  |  |  |  |  | 
        +------+  +------+  +------+ 


        +------+      +------+ 
        |  |      |  | 
      Step 2 |  |+---------------------->|  | 
        |  |      |  | 
        |  |      |  | 
        +------+      +------+