CODEWITHSUNDEEP
cdata-structureslinked-list
borg
borg

Reputation: 1

Removing node from singly linked list

I need to remove a node from a singly linked list. I know this is a simple thing to do, but my mind is blank and I've searched both Google and Stackoverflow, but I seriously haven't found anything that will help me.

basically the list of nodes is contained in a bucket; like this:

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

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

and I have a function

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

to find the correct bucket. So I know how to find the correct bucket, but I don't know how to remove a given node. I would like to remove the node by nodeid (I think, I haven't really written the code that will call the remove function yet ;) but I think I'll be able to modify the code if necessary). I think that's all that's needed to solve this. Thanks in advance.

Upvotes: 0

Views: 3865

Answers (8)

mostafa
mostafa

Reputation: 1

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

Upvotes: 0

Kiran Marke
Kiran Marke

Reputation: 11

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

Upvotes: 1

Jon L
Jon L

Reputation: 273

Your nodes don't have any payload other than an id, so, depending on the data payload of a node, you might not actually need to iterate the list in the standard way. This is useful if deleters are going to know the address of only the node they want to delete.

If your payload is a pointer to other data:

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

Then you could "delete" a node by stealing the payload of the next node, and then delinking the next node:

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

Upvotes: 2

Jim Balter
Jim Balter

Reputation: 16406

This removes a node given its address; you can modify it to remove a node given its id, but you haven't specified the form of an id -- is it a NUL-terminated string, or is it 20 bytes?

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

Or, more compactly,

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

Upvotes: 0

Sparky
Sparky

Reputation: 14057

The following does not contain any error checking and only removes the current node from the list ...

pPrev->next = pCurrent->next;

Your preferences may vary, but I tend to put my linked list node at the start of the structure (whenever practical). 

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

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

I find this generally helps to simplify pointer arithmetic and allows simple typecasting when needed.

Upvotes: 0

Jose Rui Santos
Jose Rui Santos

Reputation: 15319

Its been a long time ago since I worked with C, but this should be compile clean.

Basically, you need to keep track of the previous pointer while you iterate through the linked list. When you find the node to delete, just change the previous pointer to skip the delete node.

This function deletes all nodes with id (find). If you want to delete only the first occurrence, then put a return after the free statement.

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

Upvotes: 0

Matt K
Matt K

Reputation: 13832

If you know the item you want to remove, you must do two things:

  1. Change all pointers that point to the target item to point to the target item's next member. This will be the preceding item's next pointer, or the head of the list bucket.nodes.
  2. Free the node you just made unreachable.

The code for manipulating a linked list is really not that tricky, once you understand what you are doing.

Upvotes: 2

BMitch
BMitch

Reputation: 263489

/* 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);
}

Upvotes: 1

Related Questions