The alternate implementation of a list that we will explore is known as a linked list. A linked list is made up of a series of nodes. Each node contains a value and a pointer to the next node in the list. To make a list, we will chain together a series of nodes, with each node pointing to the next one.
In a memory diagram, each node is a box containing two parts: the data and the next pointer. The next pointer stores the address of the next node in the list, or nullptr if it is the last node.
Each node is a separate object in memory. And we make no assumptions that the nodes are stored contiguously, or even in any particular order, in memory. The only connection between the nodes, what makes them into a list, are the pointers from one node to the next.
struct ListNode {
// Value stored in this node
int data = 0;
// Next node in list (nullptr == end of list)
ListNode* next = nullptr;
// Constructor
ListNode(int value) {
data = value;
}
};
Note that each node (implemented as a struct to avoid public/private access control) has a constructor that initializes its value. The next pointer is initialized to nullptr by default. Which means the node is not connected to anything.
To make a list node, we can use the constructor to create a new node with a given value. When we do so, we will always allocate the node on the heap using new, which means we need to use a pointer to keep track of where the node is stored. Here is how we could create three nodes to store the values 12, 6, and 10:
ListNode* node1 = new ListNode(12);
ListNode* node2 = new ListNode(6);
ListNode* node3 = new ListNode(10);
Warning27.2.3.
If we wanted to, we could allocate a node on the stack instead of the heap. However, doing so would limit the node’s lifetime to the scope in which it was created, which is usually not what we want for linked lists.
The nodes are not yet connected into a list. To do that, we need to set the next pointer of each node to point to the next node in the list. We can do that like this:
Note that node1 is not storing a node. It stores the memory address of a node. To access the next pointer of the node that node1 points to, we use the arrow operator to say “go to the thing node1 points at and access the next member there”. We want to set node1->next to point to the node that has the value 6, which is the node that node2 points to. So we set node1->next = node2;, which says “go to the node that node1 points to and set its next pointer to the memory address stored in node2”.
When we do something like node1->next = node2;, we are not copying a node. We are only copying the memory address stored in node2 into the next pointer of the node that node1 points to.
At this point, we have a very simply linked list made up of three nodes storing the list {12, 6, 10}. The list starts at the node that node1 points to. From there, we can follow the next pointers to get to the other nodes in the list. Here is a program that prints out the values in the list by following the pointers from one node to the next:
Notice that to access the data we are only relying on the node1 pointer variable. From there, we follow the next pointers to get to the other nodes in the list. node1->next->next->data says something like:
Do you notice something we have not taken care of yet? We allocated three nodes on the heap using new, but we have not deleted them. (The program above was set to run without the address sanitizer introduced in Section 22.7.) So our program has memory leaks. To fix that, we need to make sure to delete each node when we are done with it. Our program should end with something like:
...
delete node1; // delete the node that node1 points to
delete node2; // delete the node that node2 points to
delete node3; // delete the node that node3 points to
} //end of main
Because a linked list allocates each node as a separate allocation on the heap, we need to also delete each node individually.
