• Advertisement
Sign in to follow this  

Linked List Confusion..

This topic is 4680 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'm starting to go a little loopy trying to work out what im doing wrong with my linked lists.. So maybe someone can help curb another sleepless night of confusion.. The Code for the linked list is borrowed and slightly modifyed from one of the linked list articles off of this site. Heres the Source: See below To the formatted Code.. [Edited by - Ethical on April 26, 2005 6:37:34 PM]

Share this post


Link to post
Share on other sites
Advertisement
A description of what's wrong would be helpful....

Although, one thing I did notice is that you'll never be able to create a new list....you have no way of returning the new node when Head is passed in as null. Perhaps you want this as the declaration of AddChips():

Pile_Ptr AddChips(Pile_Ptr Head, int Value, int Quantity, char Location)

and instead of returning 1 on success as you are now, return the newly created node.

Share this post


Link to post
Share on other sites
Sorry..

My Problem is pointers.. Im always getting confused by them.

It's just I didn't understand a few steps in the linked lists tutorials, and had no complete code to figgure out why mine produces unknown results..

If I compile.. The first Node all values equal 0 instead of changing, except the *next pointer.. which points correctly to the next Node if i have added several nodes to the list.. but when i try to print the last node, the program crashes.

So is it part of the AddChips() function which is using faulty logic..? Remember I havent created a working linked list yet.. so I can't manage to grasp what im doing till i can use a complete one..

Any links to simple Structure type linked lists with complete code would be much appriciated.

Share this post


Link to post
Share on other sites
OP's code just formatted; no changes done.

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
using std::cout;
using std::endl;

typedef struct Chips_t
{
int Value; // 1, 5, 25, 50, 100, 500
int Quantity; //Number of Same Chips in Pile
char Location; //Where has the bet been placed
struct Chips *Next;
}Pile, *Pile_Ptr;

int AddChips(Pile_Ptr Head, int Value, int Quantity, char Location)
{
Pile_Ptr Temp, Cur = Head;
// Go to the end of the list
if (Cur)
while(Cur->Next)
Cur = Cur->Next;

// Allocate a new block of
// memory for this address
Temp = (Pile_Ptr)malloc(sizeof(Pile));

// ensure that the allocation passed
if (!Temp) return (0);
// Put a plug on the end of the list
Temp->Next = NULL;
if (!Cur)
{
// If this is the first element,
// then avoid assertion
Cur = Temp;
}
else
{
// Add to the end of the list
Cur->Next = Temp;
}

// Update the values of the new block
Temp->Value = Value;
Temp->Quantity = Quantity;
Temp->Location = Location;
return (1);
}

int CleanUp (Pile_Ptr Head)
{
Pile_Ptr Cur = Head;
while (Cur)
{
Head = Cur;
Cur = Cur->Next;
free(Head);
}
return(1);
}



int main()
{
int x;
int Value, Quantity;
char Location;
Pile Chip;
Pile_Ptr Current = &Chip;

Chip.Next = NULL;
Chip.Location = NULL;
Chip.Value = NULL;
Chip.Quantity = NULL;

while(1)
{
cin >> Value;
if (Value == 0) //tempory for escaping the loop
break;
cin >> Quantity;
cin >> Location;
AddChips(&Chip, Value, Quantity, Location);
}


Current = &Chip;

while (Current)
{
cout << Current->Value << " " << Current->Quantity << " " << Current->Location;
Current = Current->Next;
cin >> x;
}
CleanUp(&Chip);

return 0;
}

Share this post


Link to post
Share on other sites
Can you be more specific about where exactly the code is crashing? If you debug the code, what line in particular is causing the problem? If debugging is not directly available, try adding simple output statements at various places so you can get an idea of what step the code is failing in, and then narrow it down to a specific line or three. That should make it much easier to determine what exactly is going wrong.

Share this post


Link to post
Share on other sites
Ok, I rewrote My Linked List code using another code example and realise my errors were a mixture of bad logic and incorrect use of pointers.

I'm interested in vectors though, Any simple examples?
I've noticed many different Linked List Techniques aswell.. If anyone would like to Show thier technique they usualy use when implementing a linked list, please post it.

Sorry I couldnt be more helpful with debugging my own code for others to help me out... I'm fairly sure if i found the problem i could fix it right? ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by Ethical
I'm interested in vectors though, Any simple examples?


He is most likely referring to the C++ standard library vector, std::vector which is a C++ dynamic array, weather you want that over a list depends on the context but there not the same thing. Somebody saying to use std::vector with-out any rationale and not knowing the context is pretty useless, a list may actually be more appropriate it all depends on the context.

Quote:
Original post by Ethical
I've noticed many different Linked List Techniques aswell.. If anyone would like to Show thier technique they usualy use when implementing a linked list, please post it.


If all you want to do is use a list then the C++ standard library provides a generic list type (among other containers & algorithms) called std::list in the header list (#include <list>)

If i showed you how i would implement one i'd end up just replicating something very very simillar to most implementations of the standard library list and you would most likely be completely lost looking at it. So if you don't need to learn how to write a list currently and your still iffy with pointers i suggest using the standard library list, here & here are two good references on std::list.

quick example:

1: long winded way:


#include <list>
#include <iostream>

int main() {

typedef std::list<int> ilist; // a type alias for a list of integers

ilist l;

l.push_back(30);
l.push_back(43);

for(ilist::const_iterator itr = l.begin(), end = l.end();
itr != end;
++itr)
std::cout << *itr << std::endl;
}


2. using more of the standard library:


#include <list>
#include <algorithm> // std::copy
#include <iterator> // std::ostream_iterator
#include <iostream>

int main() {

typedef std::list<int> ilist; // a type alias for a list of integers

ilist l;

l.push_back(30);
l.push_back(43);

// copy elements to standard out.
std::copy(l.begin(), l.end(),
std::ostream_iterator<int>(std::cout, "\n"));
}


[Edited by - snk_kid on April 25, 2005 4:02:42 PM]

Share this post


Link to post
Share on other sites
This is what I wrote for linked lists for my game engine:


//Used in win32, otherwise just use inline :)
#define MyInline __forceinline

template <class T> struct GenericList_S
{
T Cur;
GenericList_S *Next;
GenericList_S *Prev;
};

template <class T> class GenericList_C
{
private:
GenericList_S<T> *First;
GenericList_S<T> *Cur;
public:
GenericList_C(void) { First = Cur = 0;};
T Add(T ToAdd)
{
GenericList_S<T> *tmp = new GenericList_S<T>;
tmp->Cur = ToAdd;
if (!First) //Nothing in list yet?
{
First = tmp;
First->Next = First;
First->Prev = First;
}
else //We have a list already, lets add it to the end!
{
tmp->Next = First;
tmp->Prev = First->Prev;
First->Prev = tmp;
tmp->Prev->Next = tmp;
}
return tmp->Cur;
}

T AddBefore(T ToAdd, T AddBefore)
{
GenericList_S<T> *adder = new GenericList_S<T>;
adder->Cur = ToAdd;

if (First)
{
GenericList_S<T> *tmp = First;
do
{
if (tmp->Cur==AddBefore)
{
//This is our guy!
adder->Next = tmp;
adder->Prev = tmp->Prev;
adder->Prev->Next = adder;
adder->Next->Prev = adder;
if (First==tmp) //Ahh crap, it was our first in list, lets set us to first now!
First = adder;
return adder->Cur;
}
tmp = tmp->Next;
} while (tmp!=First);
}

return Add(ToAdd);;
}

MyInline T GetFirst(void)
{
if (First)
{
Cur = First;
return First->Cur;
}
return 0;
}

MyInline T GetNext(void)
{
if (First && Cur->Next!=First)
{
Cur = Cur->Next;
return Cur->Cur;
}
Cur=0;
return 0;
}

MyInline T GetPrev(void)
{
if (First && Cur->Prev!=First)
{
Cur = Cur->Prev;
return Cur->Cur;
}
Cur = 0;
return 0;
}


void Remove(T ptr)
{
if (First->Cur==ptr) //Our first?
{
if (First==First->Next) //Only one in the list!
{
delete First; //Only responsible to delete the list, not the stuff in the list!
First = 0;
Cur = 0;
}
else
{
GenericList_S<T> *tmp = First;
First->Next->Prev = First->Prev;
First->Prev->Next = First->Next;
First = First->Next;
Cur = First;
delete tmp;
}
}
else //Not our first one!
{
GenericList_S<T> *tmp = First->Next;
while (tmp!=First)
{
if (tmp->Cur == ptr) //This our guy?
{
tmp->Next->Prev = tmp->Prev;
tmp->Prev->Next = tmp->Next;
Cur = tmp->Next;
delete tmp; //Delete our guy
return; //Ok, lets bail, we removed him
}
}
}
}

void SelfCleanup(void)
{
T tmp;
while (First)
{
tmp = First->Cur;
Remove(First->Cur);
delete tmp;
}
}

void Clear(void) { while (First) Remove(First->Cur); };

~GenericList_C(void) { Clear(); };
};

Share this post


Link to post
Share on other sites
Quote:
Original post by Ready4Dis
This is what I wrote for linked lists for my game engine:


This is why people keep going on and on about using the standard library, just a quick glance and i can already see floors with your custom list:

Most notably your passing parameters by value and returning elements contained by value all over your code causing redundant copies. You've actually made it virtually impossiable to change the state of an element contained.

Not explicitly defining copy/value semantics there-for the compiler default kicks in that does a member-wise (or bit-wise if it's a POD type) copy thus only pointers are copied in GenericList_C and thus eventually if there is a copy of GenericList_C some where else once out of scope you'll eventually invoke delete on the same area of memory twice or more!

Hard-coded memory scheme/model and not separated (i.e. seperating allocation/deallocatoin & construction/destruction).

Virtually no exception safety.

No constant correct-ness, accessor methods (i.e. getters) should always be constant member functions that either returns by value or constant reference depending on context.

Share this post


Link to post
Share on other sites
Wow.. A different Linked List article further down was so much more easy to understand... If anyone is looking for an introduction to them.. Definately read.

http://www.gamedev.net/reference/articles/article1072.asp

Thanks for those examples aswell, feel free to add other techniques/examples not only for myself but others that are starting out. GameDev and its users are an invaluable resource :D

Share this post


Link to post
Share on other sites
Note: If you go the STL route, std::list is indeed the closest approximation to a hand-rolled linked list, but it is not necessarily the best data structure for your task. You should consider carefully what kinds of operations will occur most often on the container. However, one big benefit to the standard library is that you can typedef your container, write a bunch of stuff that uses the standard library algorithms, and then after profiling, just change the typedef and recompile to use a new container - the algorithms are designed to work with "a container", and will perform better or worse on different container types according to how they're implemented, but will still work.* :) Thus the method behind the madness of snk_kid. ;)

* There are some exceptions. For example, std::lists must be sorted using a member function, rather than the free function std::sort, because the default sorting algorithm doesn't make sense for the list container - it expects random access, which a list doesn't give you (finding an item by position in a list requires traversing it from the head).

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
This is why people keep going on and on about using the standard library, just a quick glance and i can already see floors with your custom list:



This is why I said it was for my game engine, I mostly keep lists of pointers, so passing by value IS passing a pointer, this was the reason I put the code in for SelfCleanup, that way it would go through my list and call delete on each item before clearing the list. There is NEVER a second copy of the same list (why on earth would you want 2 copies?) I would never need to set a list == another list, it makes no sense, i'd just use the original list. I am unsure what you mean about changing the state of an element, but this is a linked list, and traversing this list is very simple:

objButton_C *ptrButton;

for (ptrButton = ButtonList.GetFirst(); ptrButton; ptrButton=ButtonList.GetNext())
{
}

Now I can access each button in my list. I actually don't use linked lists much (i think I may even have removed them all now) in my game engine anymore, I have written a dynamic array class which is much more efficient in most things than a linked list, but this was just a little class that I had laying around that I've actually used and is still useful. Like I said, I only use this with pointers:

GenericList_C<Monster_C*> AliveMonsterList;

Then I could simply add new monsters, traverse the list each frame, remove them, and when the program quits I just call SelfCleanup and I have no worries about memory missing. I have no reason to make a second copy of my AliveMonsterList so I didn't worry overloading the equal operator for the class.

Share this post


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

  • Advertisement