Linked List Confusion..
Author
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]
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.
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.
Author
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.
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.
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;}
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.
Author
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? ;)
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? ;)
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]
This is what I wrote for linked lists for my game engine:
//Used in win32, otherwise just use inline :)#define MyInline __forceinlinetemplate <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(); };};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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
