   Linked Lists
  I've never really gotten these, I hope someone can explain them...from what i get they are just structs/classes with a pointer to the next one, and at the end of the 'list' is a null pointer.  This means you can use them for flexible length lists of variables as opposed to an array which would generally be limited by a maximum size (ok there are ways round this) and which may not allways be used to its fullest (eg a 100 element array with only the first 17 being used).So the reasoning/theory behind them is fine, but its the implimentation i cant do.Struct MyStruct{  int ID;//Any old variable  MyStruct *next;   // Pointer to next struct};MyStruct *start_ptr = NULL;  //pointer to the start of list, //nothing in list so it initialises to NULLI'm fine till here..now heres where it gets hazy and im not sure what to do..I 'think' you create a temporary input struct, then another temporary struct to find the last link in the chain.temp = new MyStruct; //create a new mystruct called temptemp.ID= 5;//whatevertemp.next = NULL;    //last item on the list so its a null pointerif (start_ptr == NULL) //if the start pointer hasnt been pointed at anything    start_ptr = temp;  //make this the first item in the listelsetemp2 = new MyStruct  //create another temporary structtemp2.next = start_ptr;   while (temp2.next != NULL) // While temp2 isnt the last link on the chain  {  temp2 = temp2.next;   // Move to next link in chain  }temp2.next = temp;    // Point to the new instance of MyStructIs this correct?  I guess one of my biggest problems with it is that it doesn't feel like you can 'grab' data like you can from an array.  Any feedback would be appreciated.  This is based on a tutorial i found on the internet, but I want to be sure that im following this correctly.   
  >>I guess one of my biggest problems with it is that it doesn't feel like you >>can 'grab' data like you can from an array.this is the problem with linked lists.One rough way to directly access data like you can from an array would be to make a test and check if start_ptr->ID==desired_element_ID   ;  you dont create a new myStruct to iterate over a linked list.just change this bit://temp2 = new MyStruct  //create another temporary structMyStrcut *temp2= start_ptr;  ;  A linked list can be treated as a dynamic array, except that you can randomly access it by index number.  Instead, you must iterate through each node until you get the one you want.You have the right idea, but the code is all messed up.  This will create a node from an empty list, then count the nodes:typedef struct {   int value;   Node *next;} Node;Node *start = NULL;   // empty list// Allocate a new nodeNode *temp;temp = new Node;temp.value = 10;temp.next = NULL;// Attach node to listif (start == NULL) {   // first node in list   start = temp;}else {   // insert node at beginning of list   Node *work = start;   start = temp;   temp.next = work;  // next node will be the previous start node}// Iterate through list, count nodesint count = 0;Node *countnode = start;while (countnode != NULL) {   count++;   countnode = countnode.next;};  Oh, and once you've figured out the linked lists, check out docs on std::list.   ;  Do note that the way you (Winegums) was filling the list is by putting a new node at the end of the list while Spoulson is putting the new node at the begin of the list. So the last node put in Spoulson's list is at the begin of the list and the first node at the end of the list.Spoulson's way is faster because you don't have to walk through all of the nodes in the list to get to the end.[Edited by - Kamos on January 19, 2006 10:49:19 AM];Quote:Original post by Winegumsfrom what i get they are just structs/classes with a pointer to the next one,yesQuote:and at the end of the 'list' is a null pointer.no. At least, not necessarily.All a linked list is, in theory, is a collection of elements, where you know where the first element is, and that first element knows where the second is, and so on. The last element will contain something that tells you it's the last one, like a NULL pointer, or a -1 array index, or whatever, depending on your implementation.Quote:So the reasoning/theory behind them is fine, but its the implimentation i cant do.Your basic implementation looks fine to me, but don't call those structs 'temporary' - they last just as long as the variable you're storing.Quote:I guess one of my biggest problems with it is that it doesn't feel like you can 'grab' data like you can from an array.Every data structure has pros and cons. Linked lists make it quick to add and delete from the middle, but there's no instant access to arbitrary elements.   ;  A traditial linked-list is SLOW at "grabbing" data at a certain position, compared to an array, in fact they are exact opposite ends of the performance spectrum ... an array has the fastest access time to read a specific indexed location of any container type.  A linked-list is one of the slowest (because you must "walk" the list to find an item).A linked-list shines not in "grabbing" data at a specified location, but in allowing insertions ... and compared to other data types which allow insertions, a linked-list excels specifically at insertions ANYWHERE inside of the list.  There are many many container data structures, and most others are better at retrieving data than a plain linked-list - but at the cost of being worse at inserting data arbitrarily into the list.  For instance things like the std::vector are almost just like dynamic arrays - great retrieval, not-so-great insertion at end, and terrible insertion anywhere else.  And the std::deque is another hybrid - really-good retrieval, good-insertions nearly anywhere.  The std:deque is kind-of the best middle of the road container available in the std library ... because you don't have to know ahead of time what type of usage you will have.All of that was basically to say that you are right, "walking" the list to find an indexed item is NOT quick and simple like direct indexing an array ... but when you list sizes are small, it's not a really big deal.Also, the list is really good at "iterating" (walking through all items), and is as good at "finding" as any other non-sorted / non-hashed data structure.  So that "walking" concept makes a lot of sense in those cases.Every type / concept has its strengths and weaknesses.   ;  Linked list or doubly linked list?By the way you have it, 1 - way linked.Well, I suggest you wrap it into a templated class.Maybe something like this would do fine:template<typename T, typename ID> class LinkedList {    private:   struct SNode {  ID NodeId;  T Object;  SNode *pNext;   };   SNode *m_pHead, *m_pTail;    public:   ...};All you would have to do then is make access methods.It'd be pretty easy to move on from the above, but if you need help ask for it.Just for fun, here is how my list is done:#ifndef CAPP_LIST_H_#define CAPP_LIST_H_#pragma once#include "CApp_Error.h"namespace CApp {template<typename Type, typename Id = unsigned> class List {private:struct SNode {Id NodeId;SNode *pNext;SNode *pPrev;Type NodeObject;};SNode *m_pHead;SNode *m_pTail;unsigned m_Size;public:class Iterator {private:SNode *m_pNode;public:Iterator(SNode *pStart = NULL);Id GetId() { return m_pNode->NodeId; }bool IsGood();Iterator operator =(SNode *pStart) { m_pNode = pStart; return (*this); }bool operator ==(SNode *pEqual);bool operator !=(SNode *pDiffer);void operator --();void operator ++();Type &operator *();};List();~List();unsigned GetSize() { return m_Size; }SNode *GetNode(const Id &NodeId) const {SNode *pIter = m_pHead;while (pIter->NodeId != NodeId && pIter->pNext)pIter = pIter->pNext;if (pIter->NodeId != NodeId)return (SNode*)NULL;return pIter;}SNode *End() const { return NULL; }SNode *Begin() const { return m_pHead; }void Add(const Id &NodeId);void Remove(const Id &NodeId);bool Find(const Id &NodeId);void Clear();Type &operator [](const Id &NodeId);};template<typename Type, typename Id> List<Type, Id>::Iterator::Iterator(SNode *pStart) {m_pNode = pStart;}template<typename Type, typename Id> bool List<Type, Id>::Iterator::IsGood() {return (m_pNode != NULL);}template<typename Type, typename Id> bool List<Type, Id>::Iterator::operator !=(SNode *pDiffer) {return (m_pNode != pDiffer && m_pNode != NULL);}template<typename Type, typename Id> bool List<Type, Id>::Iterator::operator ==(SNode *pEqual) {return (m_pNode == pEqual && m_pNode != NULL);}template<typename Type, typename Id> void List<Type, Id>::Iterator::operator ++() {m_pNode = m_pNode->pNext;}template<typename Type, typename Id> void List<Type, Id>::Iterator::operator --() {m_pNode = m_pNode->pPrev;}template<typename Type, typename Id> Type &List<Type, Id>::Iterator::operator *() {return (m_pNode->NodeObject);}template<typename Type, typename Id> List<Type, Id>::List() {m_pHead = NULL;m_pTail = NULL;m_Size = 0;}template<typename Type, typename Id> List<Type, Id>::~List() {Clear();}template<typename Type, typename Id> void List<Type, Id>::Add(const Id &NodeId) {   if (this->Find(NodeId))  return;m_Size++;if (m_pHead == NULL) {m_pHead = new SNode;m_pHead->NodeId = NodeId;m_pHead->pPrev = NULL;m_pHead->pNext = NULL;m_pTail = m_pHead;return;}SNode *pNode = new SNode;pNode->NodeId = NodeId;pNode->pPrev = m_pTail;pNode->pNext = NULL;m_pTail->pNext = pNode;m_pTail = pNode;}template<typename Type, typename Id> void List<Type, Id>::Remove(const Id &NodeId) {SNode *pRemove = m_pHead;if (pRemove == NULL) {throw Error("Tried to remove id from no nodes.");return;}while (pRemove->NodeId != NodeId && pRemove->pNext)pRemove = pRemove->pNext;if (pRemove->NodeId != NodeId) {throw Error("Tried to remove non-existent node.");return;}if (pRemove->pNext && pRemove->pPrev) {pRemove->pPrev->pNext = pRemove->pNext;pRemove->pNext = pRemove->pPrev;delete pRemove;} else if (pRemove->pNext) {pRemove->pNext->pPrev = NULL;m_pHead = pRemove->pNext;delete pRemove;} else if (pRemove->pPrev) {pRemove->pPrev->pNext = NULL;m_pTail = pRemove->pPrev;delete pRemove;} else {delete pRemove;m_pHead = NULL;m_pTail = NULL;}m_Size--;}template<typename Type, typename Id> bool List<Type, Id>::Find(const Id &NodeId) {SNode *pIter = m_pHead;if (pIter == NULL)return false;while (pIter->NodeId != NodeId && pIter->pNext)pIter = pIter->pNext;if (pIter->NodeId != NodeId) {return false;}return true;}template<typename Type, typename Id> Type &List<Type, Id>::operator [](const Id &NodeId) {SNode *pIter = m_pHead;if (pIter == NULL)throw Error("m_pHead is NULL while seaching for node.");while (pIter->NodeId != NodeId && pIter->pNext)pIter = pIter->pNext;if (pIter->NodeId != NodeId)throw Error("Can't find a node with specified id.");return pIter->NodeObject;}template<typename Type, typename Id> void List<Type, Id>::Clear() {m_Size = 0;if (m_pHead == NULL)return;SNode *pIter = m_pHead;while (pIter) {SNode *pLast = pIter;pIter = pIter->pNext;delete pLast;}m_pHead = NULL;m_pTail = NULL;}};#endifIf I'm correct, this might be able to work with for_each, ALTHOUGH I AM NOT SURE.   ;  agi_shi, your class is not a run-of-the-mill linked list. it is an associative container, implemented as a linked list, which isnt very efficent.as i've explained to you, even sorted you cannot use many techniques to make it faster, as there is no random access. all your code could be made simple by use of a std::map.   