从单向链表中删除节点

Question

我需要从单向链表中删除一个节点。我知道这是一件简单的事情，但我的思想是空白的，我已经搜索谷歌和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删除节点（我想，我还没有真正写过将调用remove函数的代码;但是我认为如果需要，我将能够修改代码）。我认为这就是解决这个问题所需要的。提前致谢。

Answer 1

/* 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 2

如果你知道你要删除的项目，你必须做两两件事：

1. 更改指向目标项指向目标项的next成员的所有指针。这将是前面的项目的next指针，或者是列表bucket.nodes的头部。
2. 释放您刚才无法访问的节点。

一旦你明白你在做什么，操纵链表的代码真的不是那么棘手。

Answer 3

自从我与C合作以来，它已经很久以前了，但这应该是编译清理的。

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

该函数删除所有具有id（find）的节点。如果您只想删除第一个匹配项，请在空闲语句后输入回车符。

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 4

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

pPrev->next = pCurrent->next; 

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

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

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

我觉得这通常有助于简化指针算术，并允许在需要时进行简单的类型转换。

Answer 5

这将删除给定其地址的节点;你可以修改它以删除一个给定它的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 6

您的节点没有超过一个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 7

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 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"); 
} 
}