Thread: 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.

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.

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 ) );

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)

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;

}

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

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?

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?

Code:

function additem(list, item)
	find end of list (one simple forloop)
	item->next = NULL
	item->prev = end of list
end function

Try that.