如何从Java的链表中删除特定值？ [英] How to remove a specific value from linked list in Java?
本文介绍了如何从Java的链表中删除特定值？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
如何从链接列表java中删除特定值？
我试图在实现中实现它，但这并不容易。
这就是我要制作的东西：
//如何执行此操作...;< ..
int remove（Item item）{
Node cur = first.next;
Node prev = first;
而（cur！= null）{
if（cur.item.equals（item））{
item = dequeue（）;
}
cur = cur.next;
// TODO
}
返回0;
}
这些是预先设置的：
公共类LinkedQueue< Item>实现Iterable< Item> {
private int N; //队列
专用节点上的元素数优先； //队列的开始
private Node last; //队列结束
//助手链接列表类
私有类Node {
private Item item;接下来是
个私有节点；
}
/ **
*初始化一个空队列。
* /
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--;
如果（isEmpty（））last = null; //避免游荡
assert check（）;
退货项目；
}
主要功能：
public static void main（String [] args）{
LinkedQueue< String> q =新的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（删除一些元素。）;
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 。我不知道为什么。
解决方案
下面的代码段包含各种 remove（）方法，取自我的 LinkedList 实现之一，是用 Java 编写的。
代码
LinkedList.java （部分）
private int size; //节点计数，
private LinkedListNode< T>头; //第一个节点，
private LinkedListNode< T>结束; //最后一个节点，
/ **
*按索引删除。
*
* @参数k索引，从0开始，
* @已删除节点的返回值，如果未删除则返回null，
* /
@Override
public T remove（int k）{
checkElementIndex（k）;
//找到目标节点，并记住前一个节点
LinkedListNode< T> preNode = null;
LinkedListNode< T>节点=头;
而（k--> 0）{
preNode = node;
node = node.next; T结果=（T）node.value;
}
//保留返回值，
removeNode（node，preNode）; //删除
返回结果；
}
/ **
*按值删除，仅删除第一个匹配项（如果有）。
*
* @parav v
* @return是否已删除，
* /
@Override
public boolean removeValue（T v）{
//找到目标节点，并记住上一个节点
LinkedListNode< T> preNode = null;
LinkedListNode< T>节点=头;
而（true）{
if（node == null）返回false; //找不到，
if（node.getValue（）。compareTo（v）== 0）中断; //找到的值，
preNode = node;
node = node.next;
}
removeNode（node，preNode）; //删除
返回true;
}
/ **
*按值删除，删除所有出现的内容。
*
* @param v
* @已删除节点的返回计数，
* /
@Override
public int removeAllValue（T v）{
int rc = 0;
//找到目标节点，并记住前一个节点
LinkedListNode< T> preNode = null;
LinkedListNode< T>节点=头;
while（true）{
if（node == null）返回rc; //到达结尾，如果（node.getValue（）。compareTo（v）== 0）{$找到值，
rc ++;
if（removeNode（node，preNode））中断; //删除，如果结束则中断，
继续； //重新检查该节点，因为它成为下一个节点，所以
}
preNode = node;
node = node.next;
}
return rc;
}
/ **
*删除给定节点，保证存在。还要将大小减小1。
*
* @param节点要删除，
* @param preNode上一个节点，可以为null，
* @return表示是否删除了节点结束，
* /
受保护的布尔值removeNode（LinkedListNode node，LinkedListNode preNode）{
LinkedListNode nextNode = node.next; //下一个节点，
boolean isEnd =（nextNode == null）;
if（isEnd）{//目标是结束，
if（preNode == null）{//目标也是head，
head = null;
} else {//目标不是头部，因此preNode不为空，
preNode.next = null;
}
end = preNode;
} else {//目标未结束，
//用下一个节点替换目标，
node.next = nextNode.next;
node.value = nextNode.value;
}
大小-; //将大小减小1，
返回isEnd;
}
/ **
*删除头节点，
*
* @return
* /
@Override
public T removeHead（）{
return remove（0）;
}
/ **
*删除端节点，
*
* @return
* /
@Override
public T removeEnd（）{
return remove（size-1）;
}
LinkedListTest.java （部分）
（单元测试，通过 TestNG ）
导入org.testng.Assert;
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
/ **
* LinkedList测试。
*
* @author eric
* @date 1/28/19 6:03 PM
* /
public class LinkedListTest {
private int n = 10;
private LinkedList< Integer>利斯特//链表，
私有LinkedList< Integer> dupEvenLlist; //链表，具有重复的偶数值，
@BeforeMethod
public void init（）{
// init llist，
llist = new LinkedList（）; //创建链接列表，
Assert.assertTrue（llist.isEmpty（））;
LinkedList.appendRangeNum（llist，0，n）; //附加范围，
//初始化dupEvenLlist，
dupEvenLlist = new LinkedList（）; //创建链接列表，
LinkedList.appendRangeNum（dupEvenLlist，0，n）; //附加范围，
LinkedList.appendRangeNum（dupEvenLlist，0，n，2）; //再次追加范围，步长为2（仅偶数），
Assert.assertEquals（dupEvenLlist.size（），n + n / 2）;
}
//与删除无关的测试用例...已删除，
// remove（k）-按索引删除，
@Test
public void testRemoveByIndex（）{
for（int i = 0; i< n; i ++）{
Assert.assertEquals（llist.removeEnd（）。intValue（），n -1-i）; //结束删除，然后依次删除索引
Assert.assertEquals（llist.size（），n-1-i）;
}
Assert.assertTrue（llist.isEmpty（））;
}
// remove（v）-按值删除
@Test
public void testRemoveByValue（）{
Assert.assertFalse（llist。 removeValue（n））; //不存在，
for（int i = n-1; i> = 0; i--）{
Assert.assertTrue（llist.removeValue（i））; //按值删除
Assert.assertEquals（llist.size（），i）;
}
Assert.assertTrue（llist.isEmpty（））;
Assert.assertFalse（llist.removeValue（0））; //空，
//从具有重复值的列表中删除，
用于（int i = 0; i< n; i ++）{
Assert.assertTrue（dupEvenLlist。 removeValue（i））;
}
Assert.assertFalse（dupEvenLlist.isEmpty（））;
Assert.assertEquals（dupEvenLlist.size（），n / 2）;
}
// removeAll（v）-按值删除所有出现的值，
@Test
public void testRemoveAllByValue（）{
Assert.assertEquals（ dupEvenLlist.removeAllValue（n），0）; //不存在，
int keepSize = dupEvenLlist.size（）;
for（int i = 0; i< n; i ++）{
int rc = dupEvenLlist.removeAllValue（i）; //按值删除所有值，
Assert.assertEquals（rc，i％2 == 0？2：1）;
keepSize-= rc;
Assert.assertEquals（dupEvenLlist.size（），keepSize）;
}
Assert.assertTrue（dupEvenLlist.isEmpty（））;
Assert.assertEquals（dupEvenLlist.removeAllValue（0），0）; //空，
}
}
所有测试用例都会通过。 / p>
说明
方法：
-
T remove（int k），按索引删除。
步骤：
*循环到目标节点，
*每一步，
记录：
*上一个节点，
*该节点，
*获取目标节点的下一个节点，
*获取目标节点的值，
作为返回值之后，
*如果目标是结束，
*如果也为head，
head = null;
*如果不是头部，
preNode.next = null;
* end = preNode;
*如果目标不是结束，则
用下一个节点
替换：
* node.value = nextNode.value;
* node.next = nextNode.next;
*返回先前跟踪的目标节点的值
-
boolean removeValue（T v），按值删除，仅删除第一个匹配项。
逻辑类似于按索引删除。
区别在于：
- 在初始搜索时，比较元素而不是循环索引以查找目标。
- 返回布尔值，指示是否删除而不是删除值
-
int removeAllValue（ T v），按值删除所有，删除所有出现的内容。
这类似于按值删除。
差异：
- [在while（）内 >]
- 它将搜索所有事件，直到结束。
- 删除事件后，它继续以重新检查当前节点。
因为当前节点已被下一个节点实际替换。 - 如果删除的节点为end，则返回。
此继电器基于removeNode（）。 - 它记录已删除事件的计数。
- [ return值]
- 它返回已删除事件的计数，而不是布尔值。
-
布尔值removeNode（LinkedListNode节点，LinkedListNode preNode），按节点删除，并指定preNode。
删除给定节点，以确保
返回值指示删除的节点是否为结尾，它主要用于支持removeAllValue（）。 -
T removeHead（），T removeEnd（），删除头/尾。
只需按索引调用remove，其索引为0和size-1已通过。
提示：
-
LinkedList代表链接列表，其字段为size，head，end和通用类型T（用于节点中的值类型），它不是线程-li。 -
checkElementIndex（）方法，检查给定的索引，如果超出范围则抛出异常。 -
LinkedListNode，表示链接列表中的节点。字段value，next。
复杂度
- 删除单个：
O（ k） - 按值删除所有内容：
O（n）
其中：
-
k是目标的索引。 -
n是链接列表的大小。
How to remove a specific value from a linked list java?
I tried to make it in my implementation, but it wasn't easy..
Here is what I'm trying to make:
//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;
}
These are the pre-setup:
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;
}
And the main function:
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);
}
}
And I have a result like this. It doesn't change at all..
a b c a b d b abba a z a Remove some of elements. a b d b abba a z a
It only erase value c. I don't know why.
解决方案
Following code snippet contains various remove() methods, taken from one of my LinkedList implementation, written in Java.
Code
LinkedList.java (partly)
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 (partly)
(unit test, via 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,
}
}
All test cases would pass.
Explanation
Methods:
T remove(int k), remove by index.
Steps:
* loop to target node,
* for each step,
record:
* previous node,
* this node,
* get next node, of target node,
* get value of target node,
as return value later,
* if target is end,
* if also head,
head = null;
* if not head,
preNode.next = null;
* end = preNode;
* if targe is not end,
replace it with its next node,
logic:
* node.value = nextNode.value;
* node.next = nextNode.next;
* return previously tracked value of target node,
boolean removeValue(T v), remove by value, only remove first occurrence, if any.
The logic is similar as remove by index.
The differences are:- At initial search, compare element instead of loop to index, to find target.
- Return boolean that indicate whether removed, instead of removed value,
int removeAllValue(T v), remove all by value, remove all occurrences.
This is similar as remove by value.Differences:
- [inside while()]
- It will search all occurrence till end.
- After removing an occurrence, it "continue" to recheck the current node. Because the current node has actual replaced by it's next.
- If removed node is end, then return.
This relay on the return value ofremoveNode(). - It record count of removed occurrence.
- [return value]
- It return count of removed occurrence, instead of boolean.
boolean removeNode(LinkedListNode node, LinkedListNode preNode), remove by node, with preNode given.
Remove given node, which is guaranteed to exists, with previous node given, which might be null.
Return value indicate whether removed node is end, it's mainly used to supportremoveAllValue().T removeHead(),T removeEnd(), remove head / end.
Simply calls remove by index, with corresponding index0andsize - 1passed.
Tips:
LinkedListrepresent linkedlist, with fieldssize,head,end, and generic typeT(for value type in node), it's not thread-safe.checkElementIndex()method, check given index, and throw exception if out of range.LinkedListNode, represent the node in linked list. with fieldsvalue,next.
Complexity
- Remove single:
O(k) - Remove all by value:
O(n)
Where:
k, is the index of target.n, is size of linkedlist.
这篇关于如何从Java的链表中删除特定值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
