Lesson 15: Singly linked lists

Linked lists are a way to store data with structures so that the programmer can automatically create a new place to store data whenever necessary. Specifically, the programmer writes a struct or class definition that contains variables holding information about something, and then has a pointer to a struct of its type. Each of these individual struct or classes in the list is known as a node.

Think of it like a train. The programmer always stores the first node of the list. This would be the engine of the train. The pointer is the connector between cars of the train. Every time the train ads a car, it uses the connectors to add a new car. This is like a programmer using the keyword new to create a pointer to a new struct or class.

In memory it is often described as looking like this:

----------        ----------
- Data   -       >- Data   -    
----------     -  ----------   
- Pointer- - -    - Pointer-  
----------        ----------

Each of the big blocks is a struct (or class) that has a pointer to another one. Remember that the pointer only stores the memory location of something, it is not that thing, so the arrow goes to the next one. At the end, there is nothing for the pointer to point to, so it does not point to anything, it should be set to "NULL" to prevent it from accidentally pointing to a totally arbitrary and random location in memory (which is very bad).

So far we know what the node struct should look like:

struct node
{
  int x;
  node *next;
};

int main()
{
  node *root;  //This will be the unchanging first node
  root=new node; //Now root points to a node struct
  root->next=NULL; //The node root points to has its next pointer
                   //set equal to NULL
  root->x=5;   //By using the -> operator, you can modify the node
  return 0;       //a struct (root in this case) points to.
}

This so far is not very useful for doing anything. It is necessary to understand how to traverse (go through) the linked list before going further.

Think back to the train. Lets imagine a conductor who can only enter the train through the engine, and can walk through the train down the line as long as the connector connects to another car. This is how the program will traverse the linked list. The conductor will be a pointer to node, and it will first point to root, and then, if the root's pointer to the next node is pointing to something, the "conductor" (not a technical term) will be set to point to the next node. In this fashion, the list can be traversed. Now, as long as there is a pointer to something, the traversal will continue. Once it reaches a NULL pointer, meaning there are no more nodes (train cars) then it will be at the end of the list, and a new node can subsequently be added if so desired.

Here's what that looks like:

struct node
{
  int x;
  node *next;
};

int main()
{
  node *root; //This won't change, or we would lose the list in memory
  node *conductor; //This will point to each node as it traverses
                   //the list
  root=new node; //Sets it to actually point to something
  root->next=NULL; //Otherwise it would not work well
  root->x=12;
  conductor=root; //The conductor points to the first node
  if(conductor!=NULL)
  {
    while(conductor->next!=NULL)
    {
      conductor=conductor->next;   
    }
  }
  conductor->next=new node; //Creates a node at the end of the list
  conductor=conductor->next; //Points to that node
  conductor->next=NULL; //Prevents it from going any further
  conductor->x=42;
}

That is the basic code for traversing a list. The if statement ensures that there is something to begin with (a first node). In the example it will always be so, but if it was changed, it might not be true. If the if statement is true, then it is okay to try and access the node pointed to by conductor. The while loop will continue as long as there is another pointer in the next. The conductor simply moves along. It changes what it points to by getting the address of conductor->next.

Finally, the code at the end can be used to add a new node to the end. Once the while loop as finished, the conductor will point to the last node in the array. (Remember the conductor of the train will move on until there is nothing to move on to? It works the same way in the while loop.) Therefore, conductor->next is set to null, so it is okay to allocate a new area of memory for it to point to. Then the conductor traverses one more element(like a train conductor moving on the the newly added car) and makes sure that it has its pointer to next set to NULL so that the list has an end. The NULL functions like a period, it means there is no more beyond. Finally, the new node has its x value set. (It can be set through user input. I simply wrote in the '=42' as an example.)

To print a linked list, the traversal function is almost the same. It is necessary to ensure that the last element is printed after the while loop terminates.

For example:

conductor=root;
if(conductor!=NULL) //Makes sure there is a place to start
{
  while(conductor->next!=NULL)
  {
    cout<<conductor->x;
    conductor=conductor->next;
  }
  cout<<conductor->x;
}

The final output is necessary because the while loop will not run once it reaches the last node, but it will still be necessary to output the contents of the next node. Consequently, the last output deals with this.