Linked list in C++

What is a linked list?

In any programming language, you can create something called a linked list. This is one of many essential data structures. Other structures are stacks, queues and deques. These will be discussed later on in the other tutorials.
Lets look at the term linked list and break it down. The word list is obvious in the respect of having a list of data. For example, you may have a list like this:

Fruits:
1. Apples
2. Oranges
3. Pears
4. Mangos
5. Peaches

etc ...

Now the term linked. This means that the list will be tied together. In some respects, it may look like this:

Apples --> Oranges --> Pears --> Mangos --> Peaches

Each item in the list is linked to another.

Nodes

These are the elements that make it possible to have a linked list. Without them, there would be no listing.
Each node contains two parts; a part for the data and a part for the address of the next element. As you can see, this will use pointers.
Here is the class for the nodes. An explination will follow.

template
class node{

private:
 T Data;
 node* Link;

public:
 //constructor
 node(){Link = 0;}
 node(T d) { Data = d; Link = 0; }

 //accessors
 T& data(){ return Data; }
 node*& link(){ return Link; }

};

A short class indeed but a lot has happened.
First, the private section. These will contain the elements for the data and the link to the next node. They are both a template of type T which can allow more than one data type. This was discussed in the templates tutorial. The reason the Link variable is of type node is because it will be pointing to another node in memory.
Now, the constructor. The default constructor will simply put the Link to 0 (or NULL) since you have not placed any other nodes in the list yet.
The other constructor will set the Data to the parameter d in addition to the Link to NULL. Again, you have not linked to another node yet.
Now the accessors and mutators. The two functions you see will act as both. First, the data() function will return the data (acting as the get function) in addition to allow you to change the Data (acting as the set) since you are referencing.
Second, the link() function will return the link to you but allow you to change the link. For example you may need to remove or insert something in a list and therefore change the link to that node.

Putting it together

Here is a small example that shows a linked list of characters. This will print each element of the list.

Example 1:
Simple Linked List

Download source code here (Right click - Save Tagret As...)

#include 
using namespace std;

template
class node{

private:
 T Data;
 node* Link;

public:
 //constructor
 node(){Link = 0;}
 node(T d) { Data = d; Link = 0; }

 //accessors
 T& data(){ return Data; }
 node*& link(){ return Link; }

};

int main(){

 node a('a'), b('b'), c('c');

        //give the address to the link:
 a.link() = &b;
 b.link() = &c;

        //print each element:
 cout << a.data() << endl;
 cout << b.data() << endl;
 cout << c.data() << endl;

        //the list looks like this:
        //a --> b --> c

return 0;
}

Transversing the list

When you transverse a linked list, it means that you are looking at each element in the list. With the list example above, you are starting at the beginning of the list with the cout statements.
We can write a function that handles the printing instead of using an x number of cout statements in the main(). The function is below:

template 
void print (node* p){

     //as long as the list is not empty:
     while(p){
 cout << p -> data();
 p = p -> link();
     }

}

The argument is a pointer that will begin at some point in the list. You can decide where it begins. The while loop will keep going until the pointer is 0 (or NULL). Remember, a while loop will run with any number so long as it is not 0.
Now, let's append the above program and see the function at work:

Example 2:
Simple Linked List II

Download source code here (Right click - Save Tagret As...)

#include 
using namespace std;

template
class node{

private:
 T Data;
 node* Link;

public:
 //constructor
 node(){Link = 0;}
 node(T d) { Data = d; Link = 0; }

 //accessors
 T& data(){ return Data; }
 node*& link(){ return Link; }

};

template 
void print (node* p){

     //as long as the list is not empty:
     while(p){
 cout << p -> data();
 p = p -> link();
     }

};

int main(){

 node a('a'), b('b'), c('c');

        //give the address to the link:
 a.link() = &b;
 b.link() = &c;

        //start at beginning:
        print(&a);

        //the list looks like this:
        //a --> b --> c

return 0;
}

The function will begin printing from the first node. Had you given the print function a NULL node, it would not even print anything based on the while statement.