從單向鏈表中刪除節點

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