Linked list anarchEEE!!!

This is a discussion on Linked list anarchEEE!!! within the C Programming forums, part of the General Programming Boards category; Hello, I made what I believed to be a simple linked-list system a short while ago, but ever since I ...

  1. #1
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266

    Unhappy Linked list anarchEEE!!!

    Hello,

    I made what I believed to be a simple linked-list system a short while ago, but ever since I stopped coding it and started using it with things I have been patching holes in my logic ever since. Most recently, the code seems to work fine, but over extended periods of usage of the list more holes seem to appear...

    Anyways, could people please take a look at this:-
    Code:
    typedef struct TAGlist {
    	unsigned long data;
    	struct TAGlist *prev;
    	struct TAGlist *next;
    } list;
    
    list *root = NULL;
    
    list *NewListItem(list *list, list *parent, unsigned long data)
    {
    	if (list == NULL)
    	{
    		list = malloc(sizeof(list));
    		list->data = data;
    		list->prev = parent;
    		list->next = NULL;
    	}
    	else
    		list->next = NewListItem(list->next, list, data);
    
    	return list;
    }
    
    int DeleteListItem(list *olditem)
    {
    	if (olditem == NULL)
    		return FALSE;
    
    	if (olditem->prev != NULL)
    	{
    		if (olditem->next != NULL)
    			olditem->prev->next = olditem->next;
    		else
    			olditem->prev->next = NULL;
    
    	}
    	else if (olditem->next != NULL)
    	{
    		root = olditem->next;
    		root->prev = NULL;
    	}
    	else
    		root = NULL;
    
    	free(olditem);
    	olditem = NULL;
    
    	return TRUE;
    }
    
    list *GetListItem(list *list, unsigned long data)
    {
    	if (list != NULL)
    	{
    		if (list->data == data)
    			return list;
    		else
    			return GetListItem(list->next, data);
    	}
    
    	return NULL;
    }
    ...and tell me where in the code there might be some ambiguity? My last error stemmed from the fact that although an item was supposedly deleted and freed, it was somehow referred to later on in execution and its next member was accessed, obviously leading nowhere but a stalwart Access Violation.

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    Some of the code is a little bit confusing. Why would I call GetListItem with unsigned long data? If I have the data, why would I try to get it from the list?

    I would do your NewListItem differently. Instead of calling with parent, just call with the new data and the root of the list, and have it insert it wherever in there.

    Your delete function makes little sense to me. I would pass pointer to the list and an index number of the item you wan to get rid of. Your delete is rather confusing, and I'm under the impression that is where your code is broken.

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    This line of code is incorrect:

    Code:
    list = malloc(sizeof(list));
    Thats a pointer, it will always return sizeof 4 bytes assuming 32-bit processor.

    What you want is the sizeof the contents ...

    Code:
    list = malloc( sizeof( *list ) );

  4. #4
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    Originally posted by orbitz
    Some of the code is a little bit confusing. Why would I call GetListItem with unsigned long data? If I have the data, why would I try to get it from the list?

    I would do your NewListItem differently. Instead of calling with parent, just call with the new data and the root of the list, and have it insert it wherever in there.

    Your delete function makes little sense to me. I would pass pointer to the list and an index number of the item you wan to get rid of. Your delete is rather confusing, and I'm under the impression that is where your code is broken.
    Well, I wrote GetListItem with a view to retrieving the list item assoicated with particular data. At the time I needed the list for storing object references, hence when an object is created, a new list item is created to go with it, and when the object is deleted, the list is searched for the associated item and that is deleted as well. A bit contrived, perhaps, but it works well in theory.

    When inserting a new list item I need to know the parent item so the prev member can be filled in. I suppose I could do it a different way, but I've found neatly recursive functions to be quite handy in these situations.

    Technically, you use GetListItem to retrieve the item you want to delete, and then pass it to DeleteListItem. It checks if it's a valid pointer, if it has a parent it rearranges the parent's next member appropriately (Either the next item if there is one or NULL), if it doesn't have a parent but does have a child it sets it as the new root of the list and makes sure it doesn't reference the now defunct parent. Finally it frees the memory associated with the item and clears the pointer for good measure.

    MrWizard: Well, list is also the name of the typedef, so it would work (If I had copied the names properly, bah)

  5. #5
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    In the DeleteListItem code, you might want to add a line.
    Code:
    if (olditem->prev != NULL)
    {
        if (olditem->next != NULL)
        {
            olditem->prev->next = olditem->next;
            olditem->next->prev = olditem->prev; // Added
        }
        else
        olditem->prev->next = NULL;
    
    }

  6. #6
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    Originally posted by Salem
    > Well, list is also the name of the typedef, so it would work
    I guess this is lesson 1 for today then - NEVER name variables after types
    Yes, I know Salem, if I had copied the names properly from my code to here that issue wouldn't have arisen. I've done stupid things like that in the past, it's not as if I don't check sizeofs... don't I?

    Also originally posted by big hungry Salem
    And there's simply no need for NewListItem to be recursive
    How so? Okay, perhaps I'm applying too much K&R tree logic here, but I'm pretty certain a non-recursive function would be a drawn-out affair.

    Originally posted by XSquared
    In the DeleteListItem code, you might want to add a line.
    Code:
    if (olditem->prev != NULL)
    {
        if (olditem->next != NULL)
        {
            olditem->prev->next = olditem->next;
            olditem->next->prev = olditem->prev; // Added
        }
        else
        olditem->prev->next = NULL;
    
    }
    Correct, 10 points! Completely forgot about that

  7. #7
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    Hmm...

    (Adopts poker face)

    ...

    (Looks at hand, raises eyebrow)

    ...

    (Twitches nasal hairs)

    I'll see your and raise you

    What are the rules of this game, incidentally?

    I didn't post from memory (With my blood alcohol level?), it was simply a case of tearing out code rather firmly set into a program, which meant removing non-important references and changing names so they make more sense (I name things in a funny way). This time I forgot to adjust the name of the pointer so it didn't clash with the typedef. An honest mistake. Can you stay mad at me for long?

  8. #8
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    Well, I've now adjusted the structure used for the list (As I realised that a linked list is not a flat tree) and removed the prev member. I've also changed the NewListItem and DeleteListItem functions like so:-
    Code:
    typedef struct TAGlist {
    	unsigned long data;
    	struct TAGlist *next;
    } list;
    
    list *root = NULL;
    
    list *NewListItem(list *listitem, unsigned long data)
    {
    	if (listitem == NULL)
    	{
    		listitem = malloc(sizeof(list));
    		listitem->data = data;
    		listitem->next = NULL;
    	}
    	else
    		listitem->next = NewDebugSocket(listitem->next, data);
    
    	return listitem;
    }
    
    list *DeleteListItem(list *listitem, unsigned long data)
    {
    	list *nextitem = NULL;
    
    	if (listitem != NULL)
    	{
    		if (listitem->data == data)
    		{
    			nextitem = listitem->next;
    			free(listitem);
    			listitem = NULL;
    			if (nextitem != NULL)
    			{
    				listitem = nextitem;
    			}
    		}
    		else
    			listitem->next = DeleteListItem(listitem->next, data);
    
    	}
    
    	return listitem;
    }
    However, this still seems to be causing similar problems as before. Any ideas?

  9. #9
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    Code:
    function additem(list, item)
    	find end of list (one simple forloop)
    	item->next = NULL
    	item->prev = end of list
    end function
    Try that.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 11:03 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 09:04 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 11:03 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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