Jump to content
  • Advertisement
Sign in to follow this  
Winegums

Linked Lists

This topic is 4596 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'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 NULL


I'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 temp
temp.ID= 5;          //whatever
temp.next = NULL;    //last item on the list so its a null pointer

if (start_ptr == NULL) //if the start pointer hasnt been pointed at anything
    start_ptr = temp;  //make this the first item in the list

else
temp2 = new MyStruct  //create another temporary struct
temp2.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 MyStruct

Is 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.

Share this post


Link to post
Share on other sites
Advertisement
>>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

Share this post


Link to post
Share on other sites
you dont create a new myStruct to iterate over a linked list.


just change this bit:

//temp2 = new MyStruct //create another temporary struct
MyStrcut *temp2= start_ptr;


Share this post


Link to post
Share on other sites
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 node
Node *temp;
temp = new Node;
temp.value = 10;
temp.next = NULL;

// Attach node to list
if (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 nodes
int count = 0;
Node *countnode = start;
while (countnode != NULL) {
count++;
countnode = countnode.next;
}

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Quote:
Original post by Winegums
from what i get they are just structs/classes with a pointer to the next one,

yes
Quote:
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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;
}
};

#endif


If I'm correct, this might be able to work with for_each, ALTHOUGH I AM NOT SURE.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!