People always make their own linked lists because the STL is invariably taught last, and people need the use of variable length arrays far before then [generally around the time they learn how to use pointers]
Personally, learning how to make linked lists was a leap in getting to know pointers.
Anyways, a small summary of my linked list code.
Note: I do not make the linked-list the class. I make the list elements the class. This way 'head', and mybool isn't needed to handle the odd case of the first list entry.
#include <iostream>struct List{ int data; List *next; List(){ data=0; next=0; } List(int inint){ data=inint; next=0; } void push(List **); void display();};void List::push(List **head){//// Push this onto the top of *head////// Common usage:// List *foo=0;// List *bar=0;//// bar=new List(10);// bar->push(&foo);//if (*head){ this->next=*head;}*head=this;}void List::display(){//// Display this and all List objects linked to it // delimited by newlines.//if (!this){ return;}cout << data << endl;next->display();}void main(){List *foo=0;List *bar=0;bar=new List(10);bar->push(&foo);bar=new List(-2);bar->push(&foo);bar=new List(200);bar->push(&foo);foo->display();}
Class:
The class consists of a data element and a 'link' element [in this case ->next] which is a pointer to the next element. A simple linked list.
It also has a default constructor, and a constructor that takes an int as a param to initialize the structure. [remember, structures are just classes with everything public]
Now for the slightly tricky stuff in my implimentation.
First is the push(List **) function. The funny List ** is essentially a pointer to a pointer.
So a List object contains data for a list.
A *List points to that data and allows it to be changed when passed into a function.
A **List points to that pointer, and allows it to be changed when passed into a function.
Because we want the head of the list to be able to be changed, we have the programmer pass it into the function.
The push() function simply checks if the head of the list has data, and sets this->next to be the current top of the list. Since the top of the list now isn't the top of the list anymore, it changes that pointer to become the "new" top of the list.
Note that if the top of the list doesn't point to anything, the push function is nice enough to place it at the top of our new list for us.
Second is the diplay() function. The only tricky thing here is a little simple recursion. The display function prints the current data, and then tells itself to go to the next element and print that. It will continue on until this==0 [otherwise known as past the end of the list] at which point it will stop.
This little test code works for me using gcc, and should compile pretty much anywhere without issue.
The test output should be:
200
-2
10
(remember, putting things at the top will reverse their order!)