如何在Java中从链表中删除特定值？

Question

如何从Java链表中删除特定值？
我尝试在我的实现中完成它，但并不容易。

这是我正在尝试制作的内容：

//How to do this...;<..
int remove(Item item) {
    Node cur = first.next;
    Node prev = first;
    while (cur !=null) {
        if (cur.item.equals(item)) {
            item = dequeue();
        }
        cur = cur.next;

        // TODO 
    }


return 0;

}

以下是预先设置:

 public class LinkedQueue<Item> implements Iterable<Item> {
   private int N;         // number of elements on queue
   private Node first;    // beginning of queue
   private Node last;     // end of queue

  // helper linked list class
 private class Node {
    private Item item;
    private Node next;
}

/**
 * Initializes an empty queue.
 */
public LinkedQueue() {
    first = null;
    last  = null;
    N = 0;
    assert check();
}

  public Item dequeue() {
      if (isEmpty()) throw new NoSuchElementException("Queue 
    underflow");
    Item item = first.item;
    first = first.next;
    N--;
    if (isEmpty()) last = null;   // to avoid loitering
    assert check();
    return item;
   }

主要功能：

 public static void main(String[] args) {
    LinkedQueue<String> q = new LinkedQueue<String>();

    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("c");
    q.enqueue("a");
    q.enqueue("b");
    q.enqueue("d");
    q.enqueue("b");
    q.enqueue("abba");
    q.enqueue("a");
    q.enqueue("z");
    q.enqueue("a");
    System.out.println(q);
    System.out.println("Remove some of elements.");

    q.remove("a");
    q.remove("f");
    q.remove("c");
    System.out.println(q);
   }
  } 

我有一个结果，像这样。它根本没有改变。

a b c a b d b abba a z a 
删除一些元素。
a b d b abba a z a 

它只删除了值为c的元素。我不知道为什么。

- pigpug pee

Answer 1

自Java 8开始，有一个名为removeIf(Predicate<? super E> filter)的方法，您可以在其中放置自己的条件来删除元素。"最初的回答"。

list.removeIf(cur -> cur.item.equals(item));

- dehasi

Answer 2

根据问题的细节，我假设您在Java方面相当新。你所问的和你展示的细节完全不同。

1. LinkedQueue<String> q = new LinkedQueue<String>(); 仅适用于LinkedQueue是一种通用类而不是特定于Item类型类的实现。也就是说，您没有创建LinkedQueue<Item>类的对象。LinkedQueue<String>和LinkedQueue<Item>是不同的。

2. cur.equals(item)缺乏了解等式合同和== vs equal的差异。也就是说，您正在比较两个完全不同的对象。一个是Node，另一个是Item类对象。

建议：清晰基础知识，阅读Cathy Sierra的书。Java 6 SCJP认证程序员

至于答案，您实际上没有从主要方法中调用remove（通过remove方法中的打印语句进行测试）。这就是为什么您一直得到相同答案的原因。

注意：即使我们告诉您真正的解决方案，您也无法真正理解。

- Sachin

Answer 3

以下代码片段包含各种remove()方法，取自我用Java编写的LinkedList实现之一。

---

代码

LinkedList.java (部分)

private int size; // node count,
private LinkedListNode<T> head; // first node,
private LinkedListNode<T> end; // last node,

/**
 * Remove by index.
 *
 * @param k index, start from 0,
 * @return value of removed node, or null if not removed,
 */
@Override
public T remove(int k) {
    checkElementIndex(k);

    // find target node, and remember previous node,
    LinkedListNode<T> preNode = null;
    LinkedListNode<T> node = head;
    while (k-- > 0) {
        preNode = node;
        node = node.next;
    }

    T result = (T) node.value; // keep return value,

    removeNode(node, preNode); // remove

    return result;
}

/**
 * Remove by value, only remove the first occurrence, if any.
 *
 * @param v
 * @return whether removed,
 */
@Override
public boolean removeValue(T v) {
    // find target node, and remember previous node,
    LinkedListNode<T> preNode = null;
    LinkedListNode<T> node = head;
    while (true) {
        if (node == null) return false;// not found,
        if (node.getValue().compareTo(v) == 0) break; // value found,

        preNode = node;
        node = node.next;
    }

    removeNode(node, preNode); // remove

    return true;
}

/**
 * Remove by value, remove all occurrences.
 *
 * @param v
 * @return count of nodes removed,
 */
@Override
public int removeAllValue(T v) {
    int rc = 0;

    // find target node, and remember previous node,
    LinkedListNode<T> preNode = null;
    LinkedListNode<T> node = head;
    while (true) {
        if (node == null) return rc; // reach end,
        if (node.getValue().compareTo(v) == 0) { // value found,
            rc++;
            if (removeNode(node, preNode)) break; // remove, break if it's end,
            continue; // recheck this node, since it become the next node,
        }

        preNode = node;
        node = node.next;
    }

    return rc;
}

/**
 * Remove given node, which guarantee to exists. Also reduce the size by 1.
 *
 * @param node    node to delete,
 * @param preNode previous node, could be null,
 * @return indicate whether removed node is end,
 */
protected boolean removeNode(LinkedListNode node, LinkedListNode preNode) {
    LinkedListNode nextNode = node.next; // next node,
    boolean isEnd = (nextNode == null);
    if (isEnd) { // target is end,
        if (preNode == null) { // target is also head,
            head = null;
        } else { // target is not head, thus preNode is not null,
            preNode.next = null;
        }
        end = preNode;

    } else { // target is not end,
        // replace target with next node,
        node.next = nextNode.next;
        node.value = nextNode.value;
    }

    size--; // reduce size by 1,

    return isEnd;
}

/**
 * Remove head node,
 *
 * @return
 */
@Override
public T removeHead() {
    return remove(0);
}

/**
 * Remove end node,
 *
 * @return
 */
@Override
public T removeEnd() {
    return remove(size - 1);
}

LinkedListTest.java（部分）（单元测试，通过TestNG）

import org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;

/**
 * LinkedList test.
 *
 * @author eric
 * @date 1/28/19 6:03 PM
 */
public class LinkedListTest {
    private int n = 10;
    private LinkedList<Integer> llist; // linked list,
    private LinkedList<Integer> dupEvenLlist; // linked list, with duplicated even values,

    @BeforeMethod
    public void init() {
        // init llist,
        llist = new LinkedList(); // create linked list,
        Assert.assertTrue(llist.isEmpty());
        LinkedList.appendRangeNum(llist, 0, n); // append range,

        // init dupEvenLlist,
        dupEvenLlist = new LinkedList(); // create linked list,
        LinkedList.appendRangeNum(dupEvenLlist, 0, n); // append range,
        LinkedList.appendRangeNum(dupEvenLlist, 0, n, 2); // append range, again, with step as 2 (only even numbers),
        Assert.assertEquals(dupEvenLlist.size(), n + n / 2);
    }

    // non-remove related test cases ... are deleted,

    // remove(k) - remove by index,
    @Test
    public void testRemoveByIndex() {
        for (int i = 0; i < n; i++) {
            Assert.assertEquals(llist.removeEnd().intValue(), n - 1 - i); // remove by end, in turn it remove by index,
            Assert.assertEquals(llist.size(), n - 1 - i);
        }
        Assert.assertTrue(llist.isEmpty());
    }

    // remove(v) - remove by value,
    @Test
    public void testRemoveByValue() {
        Assert.assertFalse(llist.removeValue(n)); // not exists,

        for (int i = n - 1; i >= 0; i--) {
            Assert.assertTrue(llist.removeValue(i)); // remove by value,
            Assert.assertEquals(llist.size(), i);
        }
        Assert.assertTrue(llist.isEmpty());

        Assert.assertFalse(llist.removeValue(0)); // empty,

        // remove from list with duplicated value,
        for (int i = 0; i < n; i++) {
            Assert.assertTrue(dupEvenLlist.removeValue(i));
        }
        Assert.assertFalse(dupEvenLlist.isEmpty());
        Assert.assertEquals(dupEvenLlist.size(), n / 2);
    }

    // removeAll(v) - remove all occurrences by value,
    @Test
    public void testRemoveAllByValue() {
        Assert.assertEquals(dupEvenLlist.removeAllValue(n), 0); // not exists,

        int remainSize = dupEvenLlist.size();
        for (int i = 0; i < n; i++) {
            int rc = dupEvenLlist.removeAllValue(i); // remove all by value,
            Assert.assertEquals(rc, i % 2 == 0 ? 2 : 1);
            remainSize -= rc;
            Assert.assertEquals(dupEvenLlist.size(), remainSize);
        }
        Assert.assertTrue(dupEvenLlist.isEmpty());

        Assert.assertEquals(dupEvenLlist.removeAllValue(0), 0); // empty,
    }
}

所有测试用例都将通过。

---

解释

方法：

• T remove(int k)，按索引删除。

步骤：
* 循环到目标节点，
    * 对于每一步，
        记录：
        * 上一个节点，
        * 这个节点，
* 获取目标节点的下一个节点，
* 获取目标节点的值，
    作为返回值，
* 如果目标是尾部，
    * 如果也是头部，
        head = null;
    * 如果不是头部，
        preNode.next = null;
    * end = preNode;
* 如果目标不是尾部，
    用其下一个节点替换它，
    逻辑：
    * node.value = nextNode.value;
    * node.next = nextNode.next;
* 返回之前跟踪的目标节点的值，

• boolean removeValue(T v)，根据值删除元素，仅删除第一次出现的元素（如果有）。
  逻辑与按索引删除相似。
  区别在于：

  • 在初始搜索时，比较元素而不是循环到索引以找到目标。
  • 返回布尔值表示是否已删除，而不是已删除的值。

• int removeAllValue(T v)，根据值删除所有元素，删除所有出现的元素。
  类似于按值删除。
  区别在于：

  【while()内部】

  • 它会搜索直到结束的所有出现。
  • 删除一个出现后，它“继续”重新检查当前节点。 因为当前节点实际上已经被其下一个节点替换了。
  • 如果删除的节点是末尾，则返回。
    这依赖于removeNode()的返回值。
  • 它记录已删除出现的计数。

  【返回值】

  • 它返回已删除出现的计数，而不是布尔值。

• boolean removeNode(LinkedListNode node, LinkedListNode preNode)，根据给定的preNode和node删除节点。
  删除给定的节点（保证存在）和给定的前一个节点，可能为null。
  返回值表示已删除节点是否为末尾，主要用于支持removeAllValue()。

• T removeHead()，T removeEnd()，删除头部/尾部。
  只需调用按索引删除，并传递相应的索引0和size - 1即可。

提示：

• LinkedList 表示链表，包含 size、head、end 三个字段和泛型类型 T（节点中的值类型），它不是线程安全的。
• checkElementIndex() 方法用于检查给定索引是否超出范围，如果超出范围则抛出异常。
• LinkedListNode 表示链表中的节点，包含 value 和 next 两个字段。

---

复杂度

• 移除单个元素：O(k)
• 根据值移除所有元素：O(n)

其中：

• k，是目标元素的索引。
• n，是链表的大小。

- Eric

Answer 4

在你的if语句中，你正在检查curNode是否等于传入的Item：if (cur.equals(item))。

我认为你应该检查存储在curNode中的Item是否等于传入函数的Item：if (cur.item.equals(item))。

- Matt Berteaux

---

“prev.next = cur.next;” 对我来说也没有太多意义。在 while 循环中，prev 总是处于“last”的位置。 - kpark

我已经修改了问题。 - pigpug pee