Need some linked list help

This is a discussion on Need some linked list help within the C Programming forums, part of the General Programming Boards category; I cannot figure out for this function for the life of me, can anyone help, please? my struct Code: typedef ...

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    48

    Need some linked list help

    I cannot figure out for this function for the life of me, can anyone help, please?

    my struct
    Code:
    typedef struct items item_t;
    struct items
    {
       char name[32];
       float cost, weight;
       int dam;
       item_t *next;
    };

    Code:
    /*
     * This function deletes the item at position pos from queue.  pos must be
     * between 0 and 1 less than the number of items in the list.
     * RETURNS: possibly new base ptr for list
     */
    item_t *DelItemAtPos(item_t *itb, int pos)
    {
       item_t  *temp, *prev;
       prev = itb;
       temp = itb;
       int N;
       if( pos == 1 )
       {
          itb = itb->next;
          return(itb);
       }
       for( N=0; N < pos-1; N++)
       {
          prev = prev->next;
       }
         prev = prev->next->next;
       return(itb);
    }
    There's a helper file to this but, pos is a number read in from the keyboard.
    Last edited by jsuite; 11-30-2012 at 09:50 PM.

  2. #2
    Registered User
    Join Date
    Sep 2012
    Posts
    48
    The if(pos==1)
    *do this*

    portion works. I just can't get the second half to work.

  3. #3
    Registered User dariyoosh's Avatar
    Join Date
    Nov 2012
    Location
    Iran / France
    Posts
    33
    Hello there,


    You can try the following (assuming that list element indexes start at 0)

    Code:
    #include <stdio.h>
    
    /*
     * Definition of the data structure for linked list.
    */
    typedef struct items item_t;
    struct items
    {
        int value;
        item_t *next;
    };
    
    
    /*
     * Prints the element in a LinkedList
     * The function returns if the list is empty.
    */
    void printList(item_t *items)
    {
        item_t *tmplist = items;
        while (tmplist != NULL)
        {
            printf("%d, ", tmplist->value);
            tmplist = tmplist->next;
        }
        printf("\n");
    }
    
    
    /*
     * Returns the number of elements in a LinkedList
     * Within this context a NULL list has 0 elemnt. 
    */
    int getSize(item_t *items)
    {
        item_t *tmplist = items;
        int size = 0;
        while (tmplist != NULL)
        {
            tmplist = tmplist->next;
            ++size;
        }
        
        return size;
    }
    
    
    /*
     * Deletes the element at the given position.
    */
    item_t* deleteAtPosition(item_t *items, int const pos)
    {
        if (items == NULL)
            return NULL;
        else if ((pos < 0) || (pos > getSize(items) - 1))
        {
            printf("Error: IndexOutOfRange\n");
            return items;
        }
        else if (pos == 0)
            return items->next;
        else
        {
            item_t *tmpList = items;     
            int counter = 0;
            while (counter < pos - 1)
            {
                tmpList = tmpList->next;
                ++counter;
            }
            
            item_t **ptr = &tmpList;
            (*ptr)->next = tmpList->next->next;
            
            return items;
        }
    }
    
    
    int main(int argc, char *argv[])
    {
        item_t l1 = {12, NULL};
        item_t l2 = {13, NULL};
        item_t l3 = {14, NULL};
        item_t l4 = {15, NULL};
        item_t l5 = {16, NULL};
        item_t l6 = {17, NULL};
        
        l1.next = &l2;
        l2.next = &l3;
        l3.next = &l4;
        l4.next = &l5;
        l5.next = &l6;
        
        item_t *linkedList = &l1;
        printf("size = %d\t", getSize(linkedList));
        printList(linkedList);
    
        linkedList = deleteAtPosition(linkedList, 4);
    
        printf("size = %d\t", getSize(linkedList));
        printList(linkedList);
        
    
        return 0;
    }

    Code:
    $ gcc -Wall testscript.c -o testscript
    $ ./testscript 
    size = 6        12, 13, 14, 15, 16, 17, 
    size = 5        12, 13, 14, 15, 17, 
    $


    Regards,
    Dariyoosh

  4. #4
    Registered User dariyoosh's Avatar
    Join Date
    Nov 2012
    Location
    Iran / France
    Posts
    33
    And here is a second version as a void function which takes as parameter a pointer of pointer

    Code:
    /*
     * Deletes the element at the given position.
    */
    void deleteAtPosition(item_t **items, int const pos)
    {
        if (items == NULL)
            return ;
        else if ((pos < 0) || (pos > getSize(*items) - 1))
        {
            printf("Error: IndexOutOfRange\n");
            return ;
        }
        else if (pos == 0)
            *items = (*items)->next;
        else
        {
            item_t *tmpList = *items;     
            int counter = 0;
            while (counter < pos - 1)
            {
                tmpList = tmpList->next;
                ++counter;
            }
            
            item_t **ptr = &tmpList;
            (*ptr)->next = tmpList->next->next;
        }
    }
    Using this version
    instead of
    Code:
    linkedList = deleteAtPosition(linkedList, 4);
    You write
    Code:
    deleteAtPosition(&linkedList, 4);
    Regards,
    Dariyoosh

  5. #5
    Registered User
    Join Date
    Jan 2009
    Posts
    1,485
    As far as I can tell you have a memory leak since you over write the value of the node pointer you want to delete delete. There is also an issue if you attempt to remove the last node, in that case prev->next should be NULL, so attempting to dereference it using prev->next->next should segfault.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Declaring linked list inside linked list
    By blueboyz in forum C Programming
    Replies: 33
    Last Post: 04-20-2012, 11:13 AM
  2. Replies: 4
    Last Post: 05-01-2010, 11:19 PM
  3. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 09:04 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. Replies: 6
    Last Post: 03-02-2005, 02:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21