CODEWITHSUNDEEP
clinked-listhashtable
PTN
PTN

Reputation: 1692

Filter linked list and return new linked list C

I am trying to filter a linked list. Since I don't want to change the original linked list, I want to create a sub linked list and return it instead.

I am having troubles with this because I only know how to get 1 node from the filtering process, but I don't know how to move around and add nodes from the original linked list to the sub linked list.

I have a struct like this (This represents an entry in a hash table):

typedef struct Entry {
   char *word;
   int len;
   struct Entry *next;
} Entry;

My filter function will receive the word length and the original linked list as arguments, then find nodes that have the same value of len. Whenever it finds a node that has the same value of len, it adds the node to another linked list. Finally it returns the new linked list.

struct Entry* filterLen(int len, struct Entry *en) {
   struct Entry *temp = (struct Entry *)malloc(sizeof(struct Entry));

   while(en->next != NULL) {
      if (en->len == len) {
         // assign values to temp list
         temp->word = en->word;
         temp->len = en->len;
         temp->next = en;
      }

      en = en->next; // move through list
   }

   return temp;
}

Upvotes: 3

Views: 4914

Answers (4)

Mikkel Christiansen
Mikkel Christiansen

Reputation: 137

Entry* filterLen(int len, Entry *en) {
   Entry *result = NULL, **temp = &result;

   while(en != NULL) {
      if (en->len == len) {
     // assign values to temp list
         *temp = malloc(sizeof(Entry));
         (*temp)->word = en->word;
         (*temp)->len = en->len;
         (*temp)->next = NULL;
         temp = &((*temp)->next);
      }

      en = en->next; // move through list
  }

  return result;
}

EDIT Seems to be a competition here, so:

Entry* filterLen(int len, Entry *en) {
   Entry *result, **temp = &result;

   for ( ; en; en = en->next) { // Move through list
      if (en->len == len) {        // Then assign values to temp list
         *temp = malloc(sizeof(Entry));
         (*temp)->word = en->word; // WARNING str shared with en list!!!
         (*temp)->len = en->len;
         temp = &((*temp)->next);
      }
   }
   *temp = NULL;
   return result;
}

Upvotes: 2

BLUEPIXY
BLUEPIXY

Reputation: 40155

Entry* filterLen(int len, Entry *en) {
    Entry result = { NULL, 0, NULL };
    Entry *curr  = &result;

    while(en != NULL){
        if(en->len == len){
            Entry *temp = malloc(sizeof(*temp));
            *temp = *en;
            temp->next = NULL;
            curr = curr->next = temp;
        }
        en = en->next;
    }
    return result.next;
}

Upvotes: 2

Clarence Heckman
Clarence Heckman

Reputation: 11

From what I understood in you question, you want to return a linked list of entries with a len field equal to the input parameter. Currently, your code is only storing a single 'temp' and you need to rebuild a new list.

struct Entry* filterLen(int len, struct Entry *en) {
  struct Entry *first = NULL;
  struct Entry *last = NULL;
  while(en != NULL) {
    if (en->len == len) {
      if(last){
        last->next = (struct Entry *)malloc(sizeof(struct Entry));
        last = last->next;
      } else {
        last = (struct Entry *)malloc(sizeof(struct Entry));
        first = last;
      }
      // assign values to temp list
      last->word = en->word;
      last->len = en->len;
      last->next = NULL;
    }
    en = en->next; // move through list
  }
  return first;

}

Upvotes: 1

dbush
dbush

Reputation: 225757

Right now, your filtering function is copying the contents of the last node it found (including the next pointer) into the temp node. This results in the function returning the last matching node plus whatever comes after it in the list.

What you need to do is create a new node each time you find a matching node and copy the contents to that node. That includes duplicating the string so you don't have to worry about potentially double-freeing anything.

struct Entry* filterLen(int len, struct Entry *en) {
   struct Entry *result = NULL, *temp = NULL;

   while(en != NULL) {
      if (en->len == len) {
         // copy node to end of temp list
         if (temp == NULL) {
             result =  malloc(sizeof(struct Entry));
             temp = result;
         } else {
             temp->next =  malloc(sizeof(struct Entry));
             temp = temp->next;
         }
         temp->word = strdup(en->word);  // Perform a deep copy
         temp->len = en->len;
         temp->next = NULL;
      }

      en = en->next; // move through list
   }

   return result;
}

Upvotes: 1

Related Questions