7.2.2 Basic Linked List

Linked Lists are a common custom data structure. As the name implies, they are a list of nodes linked together. Each node has two basic parts, data and a link to the next node.

Here is an example of a basic linked list that holds an integer.

Source: By Lasindi - Own work, Public Domain, https://commons.wikimedia.org/w/index.php?curid=2245162

Notice that each node has the two parts described above, an integer and a pointer to the next node. Starting at the head (first node) of the list, you can traverse through each value by tracing it through the linked node.

One limitation though is that you cannot find an element in the middle. You must start at the head and traverse through the list.

Linked List Implementation

Implementing a linked list is the same concept regardless of what data the list will hold. In this example, you will have a chance to explore how linked lists are set up and traversed.

Head - Each list must contain a head. The head is essentially how you access the list and is represented as the entry point for any list traversal. The head element is a pointer and it is initially pointing to a null pointer.

Inserting into the list - To add nodes into the linked list, you follow a few basic steps:

• Create a new node element and add the data to that element

• Link the pointer in the new node element to point to the existing head

• Update the head to point to the new node element.

Example and Walkthrough

Let’s create an example. In this example, the node element will be a struct:

struct item {
    int data;
    item *next;
};

The head item will be a pointer to an item and initially set to NULL.

item *head = NULL;

You can use a loop to populate data for this example. Inside the loop, you can see the 3 basic steps outlined above:

Create the new node:

item *newItem = new item;
newItem->data = newData;

Link the pointer of the new node to the existing head:

newItem->next = head;

Update the head item to point to the new node.

head = newItem;

Altogether, the loop looks like this:

for (int i = 0; i < 4; i++) {
    int newData = i;

    item *newItem = new item;
    newItem->data = newData;
    newItem->next = head;
    head = newItem;
}

You can go review the walkthrough yourself here:

C++ Tutor - Visualize C++ code execution to learn C++ online

As the loop executes, you can see how the linked list is built. Partway through the loop, you will notice that newItem is created and points to an item object in the heap. Remember, att his point the head variable points to a NULL item.

Once the first loop is complete, the head variable is updated to point to the new item that was just created and that new item next field now is NULL since it was updated from the head when it was NULL. This new item is esssentially the end of our list. Each item we add will be added before this item.

As you progress in the second loop, you can see the next item getting created in the heap. The new data gets populated.

At the end of the second loop, notice how the next field of the new item has been updated to point to the old head, which was your first item. The head pointer has been updated to now point to the new item.

Each loop, the process continues. A new item is created. The next field points to the old head and the head is then updated to point to the new item.

Traversing a Linked List

To traverse a linked list you use a loop. Your only access point is the head element, so you start there, access the data, then access the next element. You can repeat until your next element is null, which is the end of the list, or the tail.

Here is an example using the item node above:

item *nextItem = head;

while(nextItem != NULL){
    cout << nextItem->data << endl;
    nextItem = nextItem->next;
}

Printing the data this way ends up being a Last-In, First-Out order like you see in a stack. What if you wanted to print it in a First-In, First-Out order like a queue? This is not easy to do using a while loop since you would want to start at the tail of the linked list and work backward, but the nodes don’t have any link to the previous element.

Try This Example