Удаление узла из односвязного списка

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

Ваши узлы не имеют никакой полезной нагрузки, кроме идентификатора, поэтому, в зависимости от полезной нагрузки данных узла, на самом деле вам может не потребоваться повторять список стандартным способом.Это полезно, если удалители узнают адрес только узла, который они хотят удалить.

Если ваша полезная нагрузка является указателем на другие данные:

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 2

Если вы знаете элемент, который хотите удалить, вы должны сделать две вещи:

1. Изменить все указатели, которые указывают на целевой элемент, чтобы указывать на элемент next целевого элемента.Это будет указатель next предыдущего элемента или заголовок списка bucket.nodes.
2. Освободить узел, который вы только что сделали недоступным.

Код для управления связаннымСписок действительно не так уж и сложен, если вы понимаете, что делаете.

Answer 3

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 4

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

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

Answer 6

Это удаляет узел по его адресу;Вы можете изменить его, чтобы удалить узел с указанным идентификатором, но вы не указали форму идентификатора - это строка с нулевым символом в конце или 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 7

Следующее не содержит никакой проверки ошибок и только удаляет текущий узел из списка ...

pPrev->next = pCurrent->next;

Ваши предпочтения могут отличаться, но я склоняюсь к тому, что мой узел связанного списка стоит в началеструктура (когда это практически возможно).

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

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

Я считаю, что это, как правило, помогает упростить арифметику указателей и позволяет при необходимости выполнять простое приведение типов.

Answer 8

Это было давно с тех пор, как я работал с C, но это должно быть чисто для компиляции.

По сути, вам нужно отслеживать предыдущий указатель, пока вы перебираете связанный список.Когда вы найдете узел для удаления, просто измените предыдущий указатель, чтобы пропустить узел удаления.

Эта функция удаляет все узлы с идентификатором (find).Если вы хотите удалить только первое вхождение, поместите возврат после оператора free.

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