C++ Linked Lists

A very common data structure in programming is the linked list. A linked list is a linear data structure that uses pointers to link together objects or nodes in this case. Each node in a linked list holds user defined data such as name, age, dob, etc. Along with this data a node must have a pointer variable that points to the next node. In this demonstration that pointer variable is called 'next'. The name 'next' makes sense because the pointer 'next' points to the next node in the linked list thus keeping it linked. Here is a helpful visual representation of a linked list.

In this particular representation of a linked list there are four nodes. Each node holds two variables, an integer and a pointer named 'next'. The arrows are to help show that each nodes 'next' points to the its neighbor node. In an analogy, imagine nodes as envelopes and inside each envelope is information about a person such as their name, age, favorite color, and last a note that tells the person opening the envelopes the exact location where another envelope is which holds another persons name, age, favorite color, and yet another note that gives a location to another envelope. The person opening up the envelopes knows when they have opened the last envelope because the note in the last envelope will not have another location but instead say nowhere. In this analogy the envelopes are nodes, the name, age, favorite color, is the information you as the programmer will decide what to put into each node, the notes in each envelope is the 'next' pointer, and the final note that says nowhere is NULL.

In a more technical explanation of a linked lists each node is an object of the Node class. Just to point out, node is something that this object is commonly named it is not a keyword. The Node class of the above analogy would look something like this.

class Node
        string name;
        int age;
        string fav_color;
        Node *next;

This class is straight forward, the name of the class is Node, each object or instance of the Node class holds a name, age, favorite color, and next pointer just like in the envelope analogy. Notice how the next pointer points to a Node type, remember a class is just a user defined data type, once a class is made it can be used just as a normal data type such as int or double. For example, int *p; is a pointer named 'p' that points to an address that holds data of integer type. Node *next; is no different, 'next' is a pointer that points to an address that holds data of Node type.