C++ linked lists

boyracer87

Hey guys,

I have a mid term exam tomorrow(monday) and im having some problems with linked lists in C++. The lecturer gave use the following program and im having some trouble understanding it. Any help would be greatly appriceated:



[PHP]#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std ;

struct Node {
int Data;
struct Node * Next;
};
typedef struct Node Entry ;

void InsertFirst(int , Entry * &) ;
void DisplayList(Entry * ) ;

main()
{ Entry * Head = NULL ;
int RandomNumber ;
srand(time(0)) ;
RandomNumber = rand() % 50 ;
while(RandomNumber != 0) {
InsertFirst(RandomNumber,Head) ;
RandomNumber = rand() % 50 ;
}
DisplayList(Head) ;
}

void InsertFirst(int R, Entry * &H)
{ Entry *e ;
e = new Entry ;
e->Data = R ;
e->Next = H ;
H = e ;
}

void DisplayList(Entry * H)
{ Entry *Position = H ;
while(Position != NULL) {
cout << Position->Data << '\t' ;
Position = Position->Next ;
}
cout << endl << endl ;
} [/PHP]

boyracer87

Well the bit that is most confusing is this part and how it ties in with main:

void InsertFirst(int R, Entry * &H) 
{    Entry *e ; 
    e = new Entry ; 
    e->Data = R ; 
    e->Next = H ; 
    H = e ; 
} 

Tobias Greeshman

Ok well...

e->Next = H ;
This makes e point to the current head (ie. Head will either be NULL, or a pointer to the entire list, so this line is inserting it before the current Head).

H = e ;
So now that e is pointing to our current head, then we need to fix that, by making e our new head.


Thats all the code does, maybe draw it out on paper and you'll see it a bit better for yourself.

leeroybrown

InsertFirst takes two paramaters:

int R is a new random number to put in the linked list.
Entry * &H is a pointer to a reference to the current head node in the list. The * means you get a pointer. The & means pass by reference - ie. it's the actual Head not a copy. This ensures that you have the actual head node. This is the important point - this means that by changing H inside the function you are actually changing the memory address of the entry that main sees as Head (in other words changing the head entry).

Once you know that you have this information you:

Get a pointer to a new entry e
Assign R as it's data
Assign H as the next entry down from e (ie. second in the list)

Finally you set H to contain the memory address of e. This means that back in main Head will now point to the newly created entry e.

boyracer87

Cheers lads. Thats after clearen up loads.