Thread: Removing A Node From A Linked List In C

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    2

    Removing A Node From A Linked List In C

    I'm trying to delete and free a node from a linked list with the following struct:

    Code:
    typedef struct{
    	char * str;
    	int    len;
    }string;
    
    typedef struct linkNode{
    	string data;
    	struct linkNode * next;
    }linkNode;
    
    typedef struct{
    	linkNode * head;
    }linklist;
    
    // The heads of two lists;
    linklist list1, list2;
    I pass the list in as a pointer to the following function:
    Code:
    void Remove(linklist *link){
      int loc, i, left=1;
      linkNode *p;
    
      // ask user to input the index of the node to remove;
      printf("\nWhich string # would you like to remove?\n");
      scanf("%d", &loc);
    
    
      p=link->head;
      while(p->next!=NULL){
        p=p->next;
        left+=1;
      };
      if((1<= loc) && (loc<=left)){
        left=0;
        p=link->head;
        while(p!=NULL && loc!=1){
          loc-=1;
          p=p->next;
        }
        while(p->next!=NULL){
        p->data.str=p->next->data.str;
        p->data.len=p->next->data.len;
        p=p->next;
        }
        printf("%s\n", p->data.str);
      
    /*PROBLEM*/
       p = NULL;
        free(p);
    /*PROBLEM*/
    
        }
      else{
        printf("\nThis string does not exist\n");
        }
    }
    The code does what I want it to in that it will replace the node inicated by the user with the node following it. However, I can't get rid of the last node. It doesn't turn NULL. I'll appreciate any advice you guys have.

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Code:
      p=link->head;
      while(p->next!=NULL){
        p=p->next;
        left+=1;
      }; /* unneeded semicolon. */
      if((1<= loc) && (loc<=left)){ /* loc is not initialized. */
    
    /* ... */
    
    /*PROBLEM*/
       p = NULL;
        free(p);
    /*PROBLEM*/
    /* why are you trying to free NULL? */

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    robatino: Isn't this "intiailizing" loc:
    Code:
      scanf("%d", &loc);
    [Of course, there's the case where the scanf isn't reading valid data - but I don't think that's what you meant, was it]

    This is wrong:
    Code:
        p->data.str=p->next->data.str;
        p->data.len=p->next->data.len;
    One of the main points of linked lists is that the data stays in one place whether you insert or delete things.

    You should find keep track of the previous item in the list, and then let "prev->next = current->next". Then free the memory of current. A special case is where you are deleting the first item of the list, in which case you set the first-pointer to the current->next and free current. [Current here means the item you want to delete].

    I would, from a stylistic point of view try to split the "Remove" function from the code of the input - that is, presuming you'd like to produce a generic set of functions to deal with linked lists that can be re-used for another project, rather than just write the code for this purpose only.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Quote Originally Posted by matsp View Post
    robatino: Isn't this "intiailizing" loc:
    Code:
      scanf("%d", &loc);
    [Of course, there's the case where the scanf isn't reading valid data - but I don't think that's what you meant, was it]
    ah yes, I overlooked that.

  5. #5
    Registered User
    Join Date
    Oct 2007
    Posts
    2

    Thanks

    Thanks for your help guys. I'm still confused by the whole link list thing though. I know what it's supposed to do, but I can't seem to get it to work.

    I'm trying to create a new node and insert it into an already established link list.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    It depends a little bit on what you actually want your list to look like after you've inserted.

    If you want a "queue" where you insert at one end and remove at the other, you need to keep a head and a tail pointer, where the tail is the last element of the list. Insertion here is very easy, just do
    Code:
    tail->next = element; 
    tail = element;
    Inserting at the beginning of the list is also easy:
    Code:
    element->next = head;
    head = element;
    The complicated thing is when you have a list that is sorted in some way, where you have to search through the list to find the right element.

    You then need to search through the list, and keeping an extra varaible to hold the last element if you run off the end of the list. You also have a special case for empty list or list where the element needs to go frist, which is essentially the same as the "insert at head of list". [You can actually treat both as the same case - it works exactly the same whether the list is empty or the element goes first in the list].

    We now have the following fairly simple code.
    Code:
    node *prev; // previous element (can be NULL if we insert before head)
    node *curr; // element that we insert BEFORE (can be NULL if we reached end of list)
    
    prev = NULL;
    curr = head;
    while(curr && curr->value < element->value) {
       prev = curr;
       curr = curr->next;
    }
    
    if (prev == NULL)
       element->next = head;
       head = element;
    } else {
       prev->next = element;
       element->next = curr;
    }
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Quote Originally Posted by Creal Default View Post
    I'm trying to create a new node and insert it into an already established link list.
    any code?

  8. #8
    Registered User
    Join Date
    Jun 2007
    Posts
    63
    Quote Originally Posted by robwhit View Post
    any code?
    The following program creates a list under your specifications, adds nodes in the head and deletes from head as well. The function that destroys the list is up to you to think of a way of doing it. Keep up, Bokarinho.

    Code:
    //------------------------------------------------------------------------------------------------//
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <conio.h>
    //------------------------------------------------------------------------------------------------//
    typedef struct{
            char *str;
            int Len;
    }string;
    
    typedef struct linkNode{
    	string data;
    	struct linkNode * next;
    }linkNode;
    
    typedef struct{
    	linkNode *head;
    }linklist;
    
    linklist* CreateList()
    {
              linklist* l = malloc(sizeof(linklist));
              if(l)
              {
                   l->head = NULL;
                   return l;
              }
              else
                  return NULL;
    }
    
    //Function inserts a node into a single connected linked list.
    void InsertNode(linklist *l, char *Val, int iLen)
    {
         //Pointer to head.
         linkNode **ptrHeadNode = &l->head;
         //Firstly create the node.
         linkNode *p = malloc(sizeof(linkNode));
         if(p == NULL)
         {
              printf("Memory Error.\n");
              return;
         }
         else
         {
             //Initialise node.
             p->data.str = strdup(Val);
             p->data.Len = iLen;
             //Set node to list.
             p->next = *ptrHeadNode;
             *ptrHeadNode = p;
         }
    }
    //Prints a list using a double pointer, a simple pointer can be used.
    void DumpList(linklist *l)
    {
         linkNode **ptrNode = &l->head;
         printf("Dumping Linked List:\n");
         for(; *ptrNode != NULL; ptrNode = &(*ptrNode)->next)
               printf("%s %d\n", (*ptrNode)->data.str, (*ptrNode)->data.Len);
         printf("\n\n");
    }
    
    void RemoveNode(linklist *l)
    {
         //Get a pointer to point the list head.
         linkNode **ptrHead = &l->head;
         //Save head node in n node.
         linkNode *n = l->head;
         //Set pointer to point the next item.
         *ptrHead = (*ptrHead)->next;
         //Delete node.
         free(n);
         
    }
    void DeleteList(linklist *l)
    {
         //Deletes the whole list.
    }                  
    int main(int argc, char *argv[])
    {
      linklist *l = CreateList();
      linkNode *pNode = NULL;
      InsertNode(l,"test", 5);
      InsertNode(l,"new", 10);
      InsertNode(l,"delete", 15);
      DumpList(l);
      RemoveNode(l);
      DumpList(l);
      //DeleteList(l);
      printf("Hit any key to continue..\n");
      getch();
      return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Replies: 7
    Last Post: 06-16-2006, 09:23 PM
  3. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 05:41 PM
  4. Dynamic list of Objects in External File
    By TechWins in forum C++ Programming
    Replies: 3
    Last Post: 12-18-2002, 02:05 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM