Archived

This topic is now archived and is closed to further replies.

Linked Lists 101?

This topic is 5046 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I read Jesse Liberty''s chapter on Linked Lists, and...well, I guess I''m retarded. I really didn''t have much of a clue what was going on. All I knew was that there were like 1000 pointers involved. Can anyone give me a retard''s guide to linked lists, or maybe link me to a site you know of that covers the subject well?

Share this post


Link to post
Share on other sites
a linked list contains: nodes.

each node has:
1. something (pointer) that points to the next node.
2. something (pointer) that points to data.

O = node
-> = pointer points to the next node

O->O->O->O->O->O->O->O->O->O->O->O->...

a linked list.


that''s pretty much it.

Share this post


Link to post
Share on other sites
Have a look at

http://www.cprogramming.com/tutorial/lesson15.html

and

http://www.fortunecity.com/skyscraper/false/780/linklist.html

Hope they help




Stevie

Don''t follow me, I''m lost.

Share this post


Link to post
Share on other sites
Here's my implentation of Linked-lists in C. I use this with most of my projects, andit works well with all kindas of data.


/***************************************************************
*
* List.cpp - Provides functions for Linked Lists
*
*****************************************************************/


#include <stdlib.h>
#include <memory.h>
#include "Types.h"
#include "List.h"


/**********************************************************
*
* CreateNode()
*
* Takes the pointer for the data, and the size of the data
* and returns a pointer to list.
*
***********************************************************/

tList *CreateNode(void *pvNewData, int Size)
{
tList *pList;

// make room for List...

pList = (tList *)malloc(sizeof(tList));

// then make room for Data (using size passed in)

pList->pvData = (void *)malloc(Size);
pList->Next = NULL;

// then copy the data passed in into List data

memcpy(pList->pvData, pvNewData, Size);

pList->Next = NULL;

return (pList);
}

/**********************************************************
*
* AddToList()
*
* Adds the passed in List Ptr to the passed in list and returns
* the result.
*
***********************************************************/

tList *AddToList(tList *pList, tList *pNode)
{

tList *TempPtr;

// if the list is empty, make node New Head

if (pList == NULL)
{
pList = pNode;
}
else
{
TempPtr = pList;

// go to end of list and...

while(TempPtr->Next != NULL)
{
TempPtr = TempPtr->Next;
}

// put our node at end of list

TempPtr->Next = pNode;
}

return (pList);
}

/**********************************************************
*
* GetNthElement()
*
* Returns the Nth data element given in the passed in list
*
***********************************************************/

void *GetNthElement(tList *pList, ULONG ulElement)
{
register tList *pTemp = pList;
register ULONG ulIndex;

// loop through until we're at end, or we're at the one we want

for (ulIndex = 0; (pTemp != NULL) && (ulIndex < ulElement); ulIndex++)
{
pTemp = pTemp->Next;
}

if (pTemp == NULL)
return (NULL);
else
return (pTemp->pvData);
}

/**********************************************************
*
* RemoveElement()
*
* Remove an Element from a linked list
*
***********************************************************/

tList *RemoveElement(tList *pList, void *pvRemove)
{
tList *pTemp = pList;
tList *pTemp2;

if (pList == NULL)
return (NULL);

// if the 1st node is the one we want, move Head to Next, and remove it

if (pTemp->pvData == pvRemove)
{
pList = pList->Next;
free(pTemp->pvData);
free(pTemp);
}
else
{
// while we're not at end of list, and we haven't found our node, go to next

while((pTemp->Next != NULL) && (pTemp->Next->pvData != pvRemove))
{
pTemp = pTemp->Next;
}

// if we didn't find it, return NULL

if (pTemp->Next == NULL)
return (NULL);

// otherwise, mark the Next node (node to be deleted), make Next

// point to Next's Next, and remove old Next (the one we Marked (pTemp2))

pTemp2 = pTemp->Next;
pTemp->Next = pTemp->Next->Next;
free(pTemp2->pvData);
free(pTemp2);
}

return (pList);
}

/**********************************************************
*
* FreeList()
*
* Frees all the memory from the list
*
***********************************************************/

void FreeList(tList *pListToFree)
{
void *pvFree;

if (pListToFree == NULL)
return;

// go through each element, removing the head of the list until empty

while(pvFree = GetNthElement(pListToFree, 0))
{
pListToFree = RemoveElement(pListToFree, pvFree);
}
}


[edited by - beernutts on February 20, 2004 9:23:45 PM]

[edited by - beernutts on February 20, 2004 9:25:27 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Krak
I read Jesse Liberty''s chapter on Linked Lists, and...well, I guess I''m retarded.
No, he is.

quote:
I really didn''t have much of a clue what was going on. All I knew was that there were like 1000 pointers involved.
Are you comfortable with pointers? If you''re not, you can''t grok the implementation linked lists in C/C++.

An "executive summary" says that a linked list is a data structure in which each element keeps an indicator of what the next object is with no physical restrictions on where each element is actually stored. This means that finding an arbitrary element may take up to N steps, where N is the number of elements in the list. However, inserting or removing an element from the list (once it has been found) takes the same amount of time regardless of the number of elements in the list. We say that insertion and removal take constant time.

That''s it in a nutshell. From there you should be able to figure out how to insert an object into or remove it from a list without losing the lower portion of the list, and how to traverse the list element-to-element.

Share this post


Link to post
Share on other sites