Linked Lists 101?
Author
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?
a linked list contains: nodes.
each node has:
1. something (pointer) that points to the next node.
2. something (pointer) that points to data.
that''s pretty much it.
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.
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.
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.
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.
[edited by - beernutts on February 20, 2004 9:23:45 PM]
[edited by - beernutts on February 20, 2004 9:25:27 PM]
/***************************************************************** 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]
quote:Original post by KrakNo, he is.
I read Jesse Liberty''s chapter on Linked Lists, and...well, I guess I''m retarded.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
