Thread: Doubly Linked List

  1. #1
    Registered User
    Join Date
    May 2013
    Posts
    4

    Circular Double Linked List

    I need to make the functions using these function prototypes.

    I am mainly having problems with GetFirst() and SwapData() but if you know how to do anything it would be much appreciated..


    Header File with Prototypes
    Code:
    #ifndef LINKEDLIST_H
    #define LINKEDLIST_H
    
    /**
     * @file
     * This file provided a doubly-linked list implementation capable of storing any arbitrary data.
     * The list implementation relies on a chain metaphor: a list is merely a sequence of links
     * (ListItems) and there is no separate construct to represent the entire list, each ListItem in it
     * does that implicitly.
     * ListItems can hold any data, or even none (indicated by a NULL pointer), and so the Sort() and
     * Print() functions are entirely generic, relying on additional user-created functions that know
     * the type of data stored in the ListItems for doing the real work.
     */
    
    /**
     * This is the struct that will hold an individual list item. This is a doubly-linked list and
     * so there is no need to have a separate list struct that holds all of the individual list items
     * as they're already chained together. Note that the data is a (void *), which means that it can
     * hold any type of pointer, even pointers to multi-dimensional arrays. This also means that any
     * data stored in a list item must first be allocated.
     */
    typedef struct ListItem {
        struct ListItem *previousItem;
        struct ListItem *nextItem;
        void *data;
    } ListItem;
    
    /**
     * This function starts a new linked list. Given an allocated pointer to data it will return a
     * pointer for a malloc()ed ListItem struct. If malloc() fails for any reason, then this function
     * returns NULL otherwise it should return a pointer to this new list item. data can be NULL.
     *
     * @param data The data to be stored in the first ListItem in this new list. Can be any valid 
     *             pointer value.
     * @return A pointer to the malloc()'d ListItem. May be NULL if an error occured.
     */
    ListItem *NewList(void *data);
    
    /**
     * This function will remove a list item from the linked list and free() the memory that the
     * ListItem struct was using. It doesn't, however, free() the data pointer and instead returns it
     * so that the calling code can manage it.  If passed a pointer to NULL, Remove() should return
     * NULL to signal an error.
     *
     * @param item The ListItem to remove from the list.
     * @return The data pointer from the removed item. May be NULL.
     */
    void *Remove(ListItem *item);
    
    /**
     * This function returns the total size of the linked list. This means that even if it is passed a
     * ListItem that is not at the head of the list, it should still return the total number of
     * ListItems in the list.
     *
     * @param list An item in the list to be sized.
     * @return The number of ListItems in the list (0 if `list` was NULL).
     */
    int Size(ListItem *list);
    
    /**
     * This function returns the head of a list given some element in the list. If it is passed NULL,
     * it will just return NULL. If given the head of the list it will just return the pointer to the
     * head anyways for consistency.
     *
     * @param list An element in a list.
     * @return The first element in the list. Or NULL if provided an invalid list.
     */
    ListItem *GetFirst(ListItem *list);
    
    /**
     * This function allocates a new ListItem containing data and inserts it into the list directly
     * after item. It rearranges the pointers of other elements in the list to make this happen. If
     * passed a NULL item, InsertAfter() should still create a new ListItem, just with no previousItem.
     * It returns NULL if it can't malloc() a new ListItem, otherwise it returns a pointer to the new
     * item. The data parameter is also allowed to be NULL.
     *
     * @param item The ListItem that will be before the newly-created ListItem.
     * @param data The data the new ListItem will point to.
     * @return A pointer to the newly-malloc()'d ListItem.
     */
    ListItem *InsertAfter(ListItem *item, void *data);
    
    /**
     * SwapData() switches the data pointers of two ListItems. This is most useful when trying to
     * reorder ListItems but when you want to preserve their location. It is used within Sort() for
     * swapping items, but probably isn't too useful otherwise. This function should return
     * STANDARD_ERROR if passed a pointer to NULL, otherwise it should return SUCCESS.  Also, it is good
     * to note that SwapData() should be able to swap data pointers that point to NULL.
     *
     * @param firstItem One of the items whose data will be swapped.
     * @param secondItem Another item whose data will be swapped.
     * @return SUCCESS if the swap worked or STANDARD_ERROR if it failed.
     */
    int SwapData(ListItem *firstItem, ListItem *secondItem);
    
    /**
     * Sort() performs a selection sort on list to sort the elements into decending order. It makes no
     * guarantees of the addresses of the list items after sorting, so any ListItem referenced before a
     * call to Sort() and after may contain different data. Its second argument is a comparison function
     * that calculates the ordering. This function takes two const ListItem pointers and returns 1 if
     * the first one is "larger", 0 if they're "equal", and -1 if the second one is "bigger". Since
     * sorting relies on understanding the data within the ListItem, the comparison function is left up
     * to the caller to define. This comparison function follows the same return types as the one used
     * for qsort(). See qsort()'s  documentation for further information. For consistency Sort() returns
     * SUCCESS if successful. If passed a NULL pointer for either argument, it will do nothing and
     * return STANDARD_ERROR.
     *
     * @param list Any element in the list to sort.
     * @param CompareItems A function that can do a <, =, > sort between two items in `list`.
     * @return SUCCESS if successful or STANDARD_ERROR is passed NULL pointers.
     */
    int Sort(ListItem *list, int (*CompareItems)(const ListItem *, const ListItem *));
    
    /**
     * Print() prints out the complete list to stdout. Like Sort() it relies on a function pointer as
     * its second argument. In this case the passed function prints an individual LifheadstItem along with
     * any delimiters. The passed PrintItem function needs to add a two-character delimiter to the
     * output. The delimiters are then removed after the last item using two \b characters. The entire
     * list is surrounded by square brackets on output. An example for the printout of a list of ints is
     * "[1, 5, 2, 10, 9]". If Print() is called with a NULL list or a NULL function pointer, Print()
     * does nothing and returns STANDARD_ERROR, and will otherwise return SUCCESS.
     *
     * @param list Any element in the list to print.
     * @param PrintItem A function that can print one of the list items to stdout.
     * @return SUCCESS or STANDARD_ERROR if passed NULL pointers.
     */
    int Print(ListItem *list, void (*PrintItem)(const ListItem *));
    
    #endif
    Last edited by Nicholas Mata; 05-15-2013 at 09:33 PM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What have you tried and how does it not work?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2013
    Posts
    4
    Quote Originally Posted by laserlight View Post
    What have you tried and how does it not work?
    what i have so far but I am not 100% sure if it is correct.

    Code:
    ListItem *NewList(void *data) {
            ListItem *new = NULL;
        if(!(new=malloc(sizeof(ListItem)))) return NULL;
        new->data = data;
        new->nextItem=NULL;
            new->previousItem=NULL;
        return new;
    }
    void *Remove(ListItem *item) {
       if(item == NULL) {
            return NULL;
        }else {
            Remove(item->nextItem);
        }
        free(item);
    }
    
    ListItem *InsertAfter(ListItem *item, void *data) {
        ListItem *newNode = (ListItem*) malloc(sizeof(ListItem));
            newNode->data = data;
            newNode->nextItem = NULL;
    
            if(item == NULL)
            {
                item = newNode;
            }
            else
            {
                while(item != NULL)
                    item = item->nextItem;
    
                item->nextItem = newNode;
                (item->nextItem)->previousItem = item;
            }
    
    }

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Your prototypes define the list items, but you missing a structure normally used for a linked list that includes pointers to the first and last items on a list (or NULL). As an alternative, you can have a list where there is a dummy list item. In this case the linked list is a "circular" list where the first previousItem pointer and the last nextItem pointer point to the dummy list item. If the list is empty, then the dummy list items pointers both point to the dummy list item.

    If you're going to have a size function, you may consider using the data portion of the dummy list item to hold the count of items on the list, but you'll have to be careful to update this count when doing list operations.

  5. #5
    Registered User
    Join Date
    May 2013
    Posts
    4
    Quote Originally Posted by rcgldr View Post
    Your prototypes define the list items, but you missing a structure normally used for a linked list that includes pointers to the first and last items on a list (or NULL). As an alternative, you can have a list where there is a dummy list item. In this case the linked list is a "circular" list where the first previousItem pointer and the last nextItem pointer point to the dummy list item. If the list is empty, then the dummy list items pointers both point to the dummy list item.

    If you're going to have a size function, you may consider using the data portion of the dummy list item to hold the count of items on the list, but you'll have to be careful to update this count when doing list operations.
    Alright that makes sense do you know if the functions that I already did are correct? and How would I go about a the GetFirst()?

    Thank you for what you have already provided by the way

  6. #6
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Once the list structure is actually working GetFirst() is just a loop over the list that stops if and when it finds the head.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by Nicholas Mata View Post
    Alright that makes sense do you know if the functions that I already did are correct?
    There is an issue with the prototype definitions. If the idea here is to use a dummy list item, then NewList should not have an input parameter of (void * data). NewList would allocate and return a pointer to that dummy list item.

    The other possibility is that there should be yet another structure for list as opposed to list item. This structure would have pointers to the first and last items on the list (or NULL).

    Either way, it seems the prototype issue needs to be resolved before you can continue. Normally list functions would include a parameter for the "head" of the list (the special structure or the dummy item), but the prototypes above don't include this.

    Assuming you did choose to use a dummy list item, you have another issue. Since a linked list using a dummy item is commonly implemented as a circular list, you need a way to identify the dummy list item, but there's no way to identify it using the prototypes as defined above. One way you could identify it is to use an illegal value for the void * data, such as 0xcccccccc, or some odd value assuming the compiler would require all structures to at least be on an even boundary, but this seems risky and not something that would be part of a normal class assignment.

    About my comment to keep track of the list size at all times, it would probably better (and safer) to just iterate through the list for the Size() function. In addition, my "workaround" of using an illegal void * data value for the dummy list item would make this impossible (you could store size as (size<<1 + 1) to keep the variable odd, a form of "clever code" and something I don't think should be done as part of a class assignment).
    Last edited by rcgldr; 05-15-2013 at 11:05 PM.

  8. #8
    Registered User
    Join Date
    May 2013
    Posts
    4
    Quote Originally Posted by rcgldr View Post
    There is an issue with the prototype definitions. If the idea here is to use a dummy list item, then NewList should not have an input parameter of (void * data). NewList would allocate and return a pointer to that dummy list item. For this assignment, rather than trying to keep track of the list size at all times, it would probably better (and safer) to just iterate through the list for the Size() function.

    The other possibility is that there should be yet another structure for list as opposed to list item. This structure would have pointers to the first and last items on the list (or NULL).

    Either way, it seems the prototype issue needs to be resolved before you can continue.
    This is an assignment in which I am not allowed to change the prototypes, so I don't know how I would continue then. I really appreciate the help though it has been very useful.

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by Nicholas Mata View Post
    This is an assignment in which I am not allowed to change the prototypes, so I don't know how I would continue then.
    OK. I just wanted to make sure the prototypes were what you are supposed to be implementing. You can implement all of the list functions mentioned in the prototypes as described in the prototypes without changing the prototypes. They will work as is.

    So to continue with the prototype as they are currently written:

    The code you have for NewList is OK.

    The code you have for Remove and InsertAfter needs to be fixed.

    Quote Originally Posted by Nicholas Mata View Post
    I am mainly having problems with GetFirst() ...
    So let me help with this one first:

    Quote Originally Posted by Nicholas Mata View Post
    /**
    * This function returns the head of a list given some element in the list. If it is passed NULL,
    * it will just return NULL. If given the head of the list it will just return the pointer to the
    * head anyways for consistency.
    *
    * @param list An element in a list.
    * @return The first element in the list. Or NULL if provided an invalid list.
    */
    ListItem *GetFirst(ListItem *list);
    You're given a pointer to an item that could be anywhere on the list. In order to find the head of the list, you program will need to repeatedly follow previousItem pointer until previousItem pointer == NULL (which it might already be if the given parameter is the head of the list) . The item where item->previousItem == NULL will be the head of the list and that will be the value you're supposed to return.
    Last edited by rcgldr; 05-16-2013 at 01:03 AM.

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Here a diagram that should help with Remove and InsertAfter.

    The input parameter will be a pointer to itemb:

    Code:
    list:
    
        |---------------|    |---------------|    |---------------|
        | itema         |    | itemb         |    | itemc         |
    <---|  previousItem |<---|  previousItem |<---|  previousItem |
        |  nextItem     |--->|  nextItem     |--->|  nextItem     |--->
        |---------------|    |---------------|    |---------------|
    Last edited by rcgldr; 05-16-2013 at 01:35 AM.

  11. #11
    Registered User
    Join Date
    Mar 2013
    Posts
    31
    Quote Originally Posted by rcgldr View Post
    OK. I just wanted to make sure the prototypes were what you are supposed to be implementing. You can implement all of the list functions mentioned in the prototypes as described in the prototypes without changing the prototypes. They will work as is.

    So to continue with the prototype as they are currently written:

    The code you have for NewList is OK.

    The code you have for Remove and InsertAfter needs to be fixed.

    So let me help with this one first:



    You're given a pointer to an item that could be anywhere on the list. In order to find the head of the list, you program will need to repeatedly follow previousItem pointer until previousItem pointer == NULL (which it might already be if the given parameter is the head of the list) . The item where item->previousItem == NULL will be the head of the list and that will be the value you're supposed to return.
    I'm following along this topic with interest. Would the answer to this particular walking be recursive call?

  12. #12
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    It could be recursive but it doesn't need to be; all you need is a loop.

  13. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    Quote Originally Posted by AAnderson View Post
    I'm following along this topic with interest.
    Based on the prototype descriptions, there's no separate structure for the first and last items on the list, or the equivalent using a dummy list item, so it's not a "normal" implementation of a linked list. Instead, part of the apparent point of this exercise is for the student to create programs to search for the first or last item, given a pointer to any item within the list. If your goal is to learn about linked lists, I'm not sure this particular thread (topic) would be a good one to use as an example.

  14. #14
    Registered User
    Join Date
    Mar 2013
    Posts
    31
    Hmm, as a noobish question, is the benefit of maintaining a separate structure for first and last items faster look up times? I looked over this link: C Linked List Data Structure Explained with an Example C Program they appear to use a global (local?) *head and *curr. Is this typical? Or do you actually define a new structure which maintains the pointers of the head? Is your "last" and their "current" an equivalent idea?

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    I hope the original poster returns. I was having a lot of trouble with lockups on this forum last night and wasn't able to correspond quickly enough to determine that the somewhat unusual prototype was intended and not missing some information.

    Quote Originally Posted by AAnderson View Post
    Is the benefit of maintaining a separate structure for first and last items faster look up times?
    Faster for linked list operations like inserting before list, appending to end of list, removing from either end of list. For operations on the middle of a list it doesn't make much difference.

    Quote Originally Posted by AAnderson View Post
    I looked over this link ... they appear to use a global (local?) *head and *curr. Is this typical? Or do you actually define a new structure which maintains the pointers of the head? Is your "last" and their "current" an equivalent idea?
    In that link they are using "curr" in the same manner that a conventional linked list would use "last" or "tail" (the start would be "first" or "head"). Usually these pointers are kept in a separate structure. The structure with "head" and "tail" is the "list" structure, and the structure with "previous" and "next" is the "node" structure. In that article you referred to, the nodes only have next pointers, so that would be considered a single linked list as opposed to the double linked list being used in this thread.

    As an option, a linked list may use a dummy or head "node". This is how the hp / microsoft version of the standard template library list class is implemented. The head node's "prev" pointer is used as a "first" pointer, and the head node's "next" pointer is used as a "last" pointer. Rather than using NULL to indicate the end of a list, the beginning and the end of the list are pointers to the head node, and the list is considered "circular". In the case of an empty list, both head node pointers point to the head node. There's also a "list" structure / class that contains stuff needed for a template class and functions, and that "list" structure contains a single pointer to the head node.
    Last edited by rcgldr; 05-16-2013 at 07:07 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubly linked list
    By BEN10 in forum C Programming
    Replies: 4
    Last Post: 07-21-2009, 09:32 AM
  2. Help with doubly linked list
    By Furbiesandbeans in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2008, 11:41 AM
  3. doubly linked list
    By bahareh in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2007, 01:31 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. Doubly Linked List.. please Help!!
    By ProgrammingDlux in forum C++ Programming
    Replies: 8
    Last Post: 10-24-2004, 08:27 PM

Tags for this Thread