I've been having problems with linked lists. I can't seem to find the problem, I'm probably overlooking something so obvious I'm trying to create an array of linked lists that are dynamically allocated. Here's most of it:

    
typedef struct T_TYPE
{
	int num;
	int num2;
	T_TYPE *next;
}       T;

T **Heads, // Heads of lists

  **Tails; // Tailes of lists


int x = 6; // some number, doesn't really matter

Heads = new T*[x];
Tails = new T*[x];

for (int index=0;index < x;index++)
{
Heads[index] = NULL;
Tails[index] = NULL;
}

T *item;
item = new T;

for (int index=0;index < x;index++) // go through each list

for (int index2=0; index2 < 5;index2++) // just for example

{
  item->num = index2; // some number

  item->num2 = index2+10;
  item->next = NULL;

if (Heads[index] == NULL)
{
Heads[index] = Tails[index] = item;
}
else if ((Heads[index] != NULL) && (Heads[index] == Tails[index]))
{
Heads[index]->next = item;
Tails[index] = item;
}
else
{
Tails[index]->next = item;
Tails[index] = item;
}
}
delete item;

// Now i want to display the list


for (int index=0;index < x;index++)
{
 if (Heads[index] == NULL)
   continue;
 while (Heads[index] != NULL)
  {
   // display stuff

   Heads[index] = Heads[index]->next;
  }
}

delete [] Heads;
delete [] Tails;
    

The program freezes when I try to display the lists Right at: Heads[index] = Heads[index]->next; I can use dynamic allocation instead of linked lists but I really prefer linked lists because I never used them before and I would like to learn Can anyone help? Sorry if the message is long Thanks for your help. The road to success is always under construction Edited by - Tornado on 9/7/00 7:55:23 AM

Uh.. I might be wrong, but shouldn''t you do new for every item?
As it looks now you just modify the sam item several times, and then delete it... Put the new inside the loops, and don''t do ''delete item''. After you''ve displayed the lists, you go through them and delete each item.

Don''t quote me on this, but I think the line you say is the problem is irrelevant. Actually, if I am reading your code right (I may not be, since I just skimmed it). I admit I don''t fully understand the Head[] and Tail[] arrays... I thought linked lists were supposed to get away from arrays. Anyway, my solution (untested) is to get rid of Heads[index] = Heads[index]->next; and increment index to access it like an array(?) This is a very strange LL IMHO. The stereotypical LL goes somehthing like this:

    template <class T>class LinkedList{    private:        LinkedList *Next;        T *Data;    public:        LinkedList() {Next = NULL;}        ~LinkedList() {delete Data; delete Next;}        void SetNext(LinkedList *NewNext) {Next = NewNext;}        LinkedList * GetNext() {return Next;}        void SetData(T *NewData) {Data = NewData;}        T * GetData() {return Data;}};// use it like thisLinkedList<int> *myList = new LinkedList<int>LinkedList<int> *temp = myList;int Input = 0;while (cin >> Input) // not sure about this line{    temp.SetData(new int(Input));    temp.SetNext(new LinkedList<int>);    temp = temp.GetNext();}// it needs work because there will always be an extra node at the end of the list, but it should work    

--------------------


You are not a real programmer until you end all your sentences with semicolons;

Yanroy@usa.com

Visit the ROAD Programming Website for more programming help.

Check out todays "Code Of The Day" over on www.flipcode.com for my linked list class.

A good place to look for linked list implementation is Robert Sedgewick''s "Algorithms in C++". If you''re using just straight C, then the template class can be substituted with struct and void* for data.

Lightman

Where do I start?

First, you are only allocating one list element. If seems that your intention was to create x lists 5 elements each. That would require 5 * x element. Methinks that new operator belongs somewhere inside nested FORs.

Secondly, you use your item after you delete it. Normally it would crash the app but you are one lucky fellow and memory you''ve deallocated stayed intact. So, we''ll pretend you didn''t delete item and it is still valid. But you really should move delete item after your traversal code. And when you fix new to actually allocate multiple items you''ll need to make sure you delete all of them.

Thirdly, inside nested FORs you are setting all of your Heads and Tails pointer to point to single element you''ve created. And you set that element to point to itself. That''s what is causing infinite loop. Head[any_index]->next points to the item. item->next point to itself. You while loop will never encounter exit condition.

Also you shouldn''t be using your Heads pointer to traverse the list, ''cause it won''t be a Head pointer anymore after you''ve used it that way.

Don''t get discouraged, tho. Get a good book on C programming and read it - most of them have an example on linked lists. Try tracing trough your code. Try "running" code on paper: draw a box for every list element, an arrow pointing to the box for every pointer that points to this list element, etc. Also, it might be easier for you if you started with one linked list first. That should get rid of the outter FORs and make your code a bit easier to understand.

Good luck!

How the hell did I let myself do this:

item = new T;

Heads[index] = item;

delete item;

Why the hell would it work ?!
Thanks for your help anon, Yanroy, Lightman and vladg!

Oh btw, I'll have a look at your class Lightman

Edited by - Tornado on September 7, 2000 11:21:38 AM