C# 从单链表中删除节点

Remove node from single linked list

提问by CasperT

as far as I can see, you can do:

据我所知，你可以这样做：

1. Find the node to remove.
2. node.previous.next = node.next
3. node.next.previous = node.previous
4. node.previous = null
5. node.next = null
6. Dispose of node if you're in a non-GC environment

1. 找到要移除的节点。
2. node.previous.next = node.next
3. node.next.previous = node.previous
4. node.previous = 空
5. node.next = null
6. 如果您处于非 GC 环境中，请处理节点

If your list is a double linked.

如果您的列表是双向链接。

But how do you do it with a single linked list? I have tried a lot of things, with no avail :( I simply get it to remove a specific index instead or it does nothing at all

但是你如何使用单个链表来做到这一点？我已经尝试了很多东西，但都无济于事:(我只是让它删除特定的索引，或者它什么都不做

采纳答案by jason

Start at the beginning of the list. Maintain a reference to the current item (currentItem) and the previous item (previousItem). Linearly search for the item that you want to remove always walking with previousItem = currentItem, currentItem = currentItem.Next. If the item that you want to remove is the head of the list, reassign the head of the list to currentItem.Next. Otherwise, set previousItem.Next = currentItem.Next. If necessary (as you say, in a non-GC environment) dispose of currentItem.

从列表的开头开始。维护对当前项 ( currentItem) 和前一项 ( previousItem)的引用。线性搜索要删除的项目始终与 一起行走previousItem = currentItem, currentItem = currentItem.Next。如果要删除的项目是列表的头部，则将列表的头部重新分配给currentItem.Next。否则，设置previousItem.Next = currentItem.Next。如有必要（如您所说，在非 GC 环境中）处理currentItem.

Basically you are using previousItemto mimic the behavior of a currentItem.Previousin the case of a doubly-linked list.

基本上你是previousItem用来模仿 acurrentItem.Previous在双向链表的情况下的行为。

Edit: This is a correct implementation of Delete:

编辑：这是一个正确的实现Delete：

public void Delete(int rangeStart, int rangeEnd) {
    Node previousNode = null, currentNode = Head;
    while (currentNode != null) {
        if (currentNode.Data >= rangeStart && currentNode.Data <= rangeEnd) {
            if (previousNode == null) {
                Initial = currentNode.Next;
            }
            else {
                previousNode.Next = currentNode.Next;
            }
        }
        else {
            previousNode = currentNode;
        }
        currentNode = currentNode.Next;
    }
}

回答by Heiko Hatzfeld

You keep track of the last node while you try to find the "current node".

当您尝试查找“当前节点”时，您会跟踪最后一个节点。

Then you can wire up the previouse.next to current.next and you are done

然后你可以将previouse.next连接到current.next，你就完成了

回答by alex

The following code uses recursion to keep track of previous node: Source: http://www.cs.bu.edu/teaching/c/linked-list/delete/

以下代码使用递归来跟踪前一个节点：来源：http: //www.cs.bu.edu/teaching/c/linked-list/delete/

nodeT *ListDelete(nodeT *currP, elementT value)
{
  /* See if we are at end of list. */
  if (currP == NULL)
    return NULL;

  /*
   * Check to see if current node is one
   * to be deleted.
   */
  if (currP->element == value) {
    nodeT *tempNextP;

    /* Save the next pointer in the node. */
    tempNextP = currP->next;

    /* Deallocate the node. */
    free(currP);

    /*
     * Return the NEW pointer to where we
     * were called from.  I.e., the pointer
     * the previous call will use to "skip
     * over" the removed node.
     */
    return tempNextP;
  }

  /*
   * Check the rest of the list, fixing the next
   * pointer in case the next node is the one
   * removed.
   */
  currP->next = ListDelete(currP->next, value);


  /*
   * Return the pointer to where we were called
   * from.  Since we did not remove this node it
   * will be the same.
   */
  return currP;
}

回答by Marc Gravell

Well, you could just use LinkedList<T>and Remove; but manually:

好吧，你可以只使用LinkedList<T>and Remove; 但手动：

• iterate forwards until you find the node you want to remove keeping the previous node available in a variable at each point
• set prev.next = node.next
• go home

• 向前迭代，直到找到要删除的节点，保持前一个节点在每个点的变量中可用
• 放 prev.next = node.next
• 回家

回答by RvdK

keep remebering the last node you been too.

继续记住你去过的最后一个节点。

//PSEUDO CODE

Node prevnode = null;
foreach (node n in nodes)
{
    if (n.name.equals(name))
    {
        if (prevnode != null)
        {
            prevnode.next = n.next;
        }
        remove n;
        break;
    }

    prevnode = n;
}

回答by Tor Haugen

This is the primary weakness of the singly-linked list. You'll either need to have a reference to the previous node, or scan through the list from the beginning.

这是单链表的主要弱点。您要么需要引用前一个节点，要么从头开始浏览列表。

回答by Radu094

In THEORY, you could do this to remove any random node from a single link list:

在理论中，您可以这样做以从单个链接列表中删除任何随机节点：

void RemoveNode(Node toRemove)
{
    toRemove.PointerToSomeValue = toRemove.NextNode.PointerToSomeValue ;
    toRemove.NextNode = toRemove.NextNode.NextNode ;

}

But, you need to be carefull about concurency issues. (ie. somebody else has a link to your node assuming it still caries the old value (an ABA problem) ), and you need to have a "marker" (empty) node at the end of the list, which you must never attempt to delete.(because of the toRemove.next.next)

但是，您需要小心并发问题。（即，其他人有一个链接到您的节点，假设它仍然带有旧值（ABA 问题）），并且您需要在列表末尾有一个“标记”（空）节点，您绝不能尝试删除。（因为 toRemove.next.next）

Edit: obviously PointerToSomeValue is whatever data you want to keep in your list. And you're not actually deleting the node, you're basically removing the next node in the list, oh,well.. you get the ideea

编辑：显然 PointerToSomeValue 是您想要保留在列表中的任何数据。你实际上并没有删除节点，你基本上是删除列表中的下一个节点，哦，好吧..你明白了

回答by mpen

Almost ironic you should just ask this. I'm trying to brush up on my singly linked lists too. I just wrote this function in C++ that seems to work:

几乎具有讽刺意味的是，你应该问这个。我也在尝试复习我的单链表。我刚刚用 C++ 编写了这个似乎有效的函数：

void pop_back() {
    if(head == NULL) {
        return;
    }

    if(head->next == NULL) {
        delete head;
        head = NULL;
        return;
    }

    Node *iter = head;
    while(iter->next->next != NULL) {
        iter = iter->next;
    }
    delete iter->next;
    iter->next = NULL;
}

For popping the last element, but you can modify it slightly to work in the middle, I'm sure. Idea is pretty much the same in C#.

对于弹出最后一个元素，但您可以稍微修改它以在中间工作，我敢肯定。想法在 C# 中几乎相同。

回答by Bragaadeesh

You may find the comprehensive implementation of Singly Linked List with all the functions such Add, Remove, InsertAt etc., here. http://tech.bragboy.com/2010/01/linked-lists.htmlNote: This has a working Java code + Test classes so that you would not miss out on anything that a singly linked list is made of,

您可以在此处找到具有添加、删除、插入等所有功能的单向链表的全面实现。 http://tech.bragboy.com/2010/01/linked-lists.html注意：这有一个有效的 Java 代码 + 测试类，这样你就不会错过任何由单链表组成的东西，

回答by Abhishek Hariharan

struct node_t {
    int data;
    struct node_t *next;
}

void delete_node( struct node_t *random) {
    struct node_t *temp;

    /* Save the ptr to the next node */
    temp = random->next;

    /* Copy stuff from the next node to this node */
    random->data = random->next->data;
    random->next = random->next->next;

    /* Delete the next node */
    free (temp);

    return;
}

This should work on most Operating Systems in my opinion.

在我看来，这应该适用于大多数操作系统。