从单链表中删除节点

Question

我需要从单链表中删除一个节点。我知道这是一件简单的事情，但我的大脑一片空白，我搜索了 Google 和 Stackoverflow，但我真的没有找到任何可以帮助我的东西。

基本上，节点列表包含在一个桶中；像这样：

struct node{
  unsigned char id[20];
  struct node *next;
};

struct bucket{
  unsigned char id;
  struct node *nodes;
};

我有一个函数

struct bucket *dht_bucketfind(unsigned char *id);  // return bucket with id[20]

可以找到正确的存储桶。所以我知道如何找到正确的存储桶，但我不知道如何删除给定的节点。我想通过 nodeid 删除节点（我想，我还没有真正编写调用删除函数的代码；）但我想如果有必要我可以修改代码）。我认为这就是解决这个问题所需要的一切。提前致谢。

Answer 1

如果您知道要删除的项目，则必须执行两件事：

1. 将所有指向目标项目的指针更改为指向目标项目的 next 成员。这将是前一项的 next 指针，或列表 bucket.nodes 的头部。
2. 释放您刚刚设置为不可访问的节点。

一旦您了解了自己在做什么，操作链表的代码实际上并不那么棘手。

Answer 2

您的节点除了 id 之外没有任何有效负载，因此，根据节点的数据有效负载，您实际上可能不需要以标准方式迭代列表。如果删除者只想知道他们想要删除的节点的地址，这非常有用。

如果您的有效负载是指向其他数据的指针：

struct _node {
     void *data;
     unsigned char id[20];
     struct _node *next
}

那么您可以通过窃取下一个节点的有效负载，然后取消链接下一个节点来“删除”节点：

int delete (struct _node *node)
{
     struct _node *temp;

     memcpy(node->id, node->next->id, 20);
     free_function(node->data);
     node->data = node->next->data;

     temp = node->next;
     node->next = node->next->next);
     free(temp);

     return 0;
 }

Answer 3

/* define your two pointers, prev and cur */
prev=NULL;
cur=head;
/* traverse the list until you find your target */
while (cur != NULL && cur->id != search_id) {
  prev=cur;
  cur=cur->next;
}
/* if a result is found */
if (cur != NULL) {
  /* check for the head of the list */
  if (prev == NULL)
    head=cur->next;
  else
    prev->next=cur->next;
  /* release the old memory structure */
  free(cur);
}

Answer 4

public void Remove(T data)
{
    if (this.Head.Data.Equals(data))
    {
        this.Head = this.Head.Next;
        this.Count = this.Count - 1;
    }
    else
    {
        LinkedListNode<T> node = this.Head;
        bool found = false;
        while (node.Next != null && !found)
        {
            if (node.Next.Data.Equals(data))
            {
                found = true;
                node.Next = node.Next.Next;
                this.Count = Count - 1;
            }
            else
            {
                node = node.Next;
            }
        }
    }
}

Answer 5

自从我使用 C 以来已经很久了，但这应该是编译干净的。

基本上，您需要在迭代链表时跟踪前一个指针。当找到要删除的节点时，只需更改前一个指针即可跳过删除节点。

该函数删除所有具有 id 的节点（查找）。如果只想删除第一个匹配项，请在 free 语句后添加 return。

void delete(struct bucket *thisBucket, unsigned char find[20]) {
  struct node *prev = null;
  struct node *curr = thisBucket->nodes;

  while (curr != null) {
    if (!strcmp(curr->id, find)) { // found the node?
      if (prev == null) { // going to delete the first node (header)?
        thisBucket->nodes = curr->next;  // set the new header to the second node
      } else {
        prev->next = curr->next;
      }
      free(curr);

      // if deleted the first node, then current is now the new header,
      // else jump to the next
      curr = prev == null? thisBucket->nodes : prev->next;

    } else { // not found, keep going
      prev = curr;
      curr = curr->next;
    }
  }
}

Answer 6

以下不包含任何错误检查，仅从列表中删除当前节点...

pPrev->next = pCurrent->next;

您的偏好可能会有所不同，但我倾向于将链表节点放在结构的开头（只要可行）。

struct node{
  struct node *next;
  unsigned char id[20];
};

struct bucket{
  struct node *nodes;
  unsigned char id;
};

我发现这通常有助于简化指针运算，并在需要时允许简单的类型转换。

Answer 7

这将删除给定地址的节点；您可以修改它以删除给定 id 的节点，但您尚未指定 id 的形式 - 它是一个以 NUL 结尾的字符串，还是 20 个字节？

// remove node from bucket and return true
// or return false if node isn't in bucket
int dht_rmnode(struct bucket* bucket, struct node* node)
{
    struct node** ppnode = &bucket->nodes;
    for( ;; ){
        struct node* pnode = *ppnode;
        if( pnode == NULL ) return 0;

        if( pnode == node ){
            *ppnode = pnode->next;
            return 1;
        }
        ppnode = &pnode->next;
    }
}

或者，更紧凑的是，

// remove node from bucket and return true
// or return false if node isn't in bucket
int dht_rmnode(struct bucket* bucket, struct node* node)
{
    struct node** ppnode = &bucket->nodes;
    struct node* pnode;
    for( ; (pnode = *ppnode); ppnode = &pnode->next )
        if( pnode == node ){
            *ppnode = pnode->next;
            return 1;
        }

    return 0;
}

Answer 8

typedef struct node
{
int id;
struct node* next;
}Node;
void delete_element(void)
{
int i;
Node* current=head;
Node* brev=NULL;

if(i==head->id){
head=current->next;
free(current);}
else{
while(NULL!=current->next)
    {
        if(i==current->next->id){
        brev=current;
        current=current->next;
        break;}
        else
        current=current->next;
    }
if(i==current->id)
    {
        if(NULL==head->next){
        head=NULL;
        free(current);}
        else
        brev->next=current->next;
        free(current);
    }
else
    printf("this id does not exist\n");
}
}