A Simple Linked List

Section 27.3 A Simple Linked List

Now we have the building blocks to create a simple linked list. But managing nodes by hand is tedious and error-prone. So, much like we created an ArrayList to manage a dynamic array for us, we will create a LinkedList class to manage a linked list of nodes for us. The class will be responsible for creating, linking, and deleting the nodes as needed.

🔗

An absolutely minimal implementation of a SimpleLinkedList will just have one member variable: a pointer to keep track of the first node in the list. We typically call this node the head of the list. When the list is empty, the head pointer will be nullptr.

🔗

The SimpleLinkedList objects themselves will be variables we create on the stack using something like SimpleLinkedList<int> myList1;. Any nodes they are keeping track of will be allocated on the heap.

🔗

Two linked lists allocated on the stack, myList1 and myList2. myList1 has null stored in its head pointer, indicating it is empty. myList2 has a head pointer pointing to a node containing the value 6.🔗 — Figure 27.3.1. Two simple linked lists. `myList1` is empty and thus it has a `nullptr` head pointer. `myList2` is managing a linked list that starts at the node containing the value 6. So myList2’s head pointer points to the node containing 6.
🔗

Note 27.3.1.

We could have a SimpleLinkedList object that was allocated on the heap, but that is less common. The whole point of the linked list is to manage dynamic memory for us so we don’t have to. Allocating the list object itself on the heap would just add unnecessary complexity.

🔗

We will always allocate lists on the stack.

🔗

We want to be able to store any type of value in our linked list, so we will make the SimpleLinkedList a class template. We will also need to change our ListNode to be a template so that it can store any type of value. First, here is how we could define a templated ListNode:

🔗

Listing 27.3.2. Templated ListNode

🔗

template<typename T>
struct Node {
    T element;
    Node* next = nullptr;

    Node(T value) { 
      element = value; 
    }
};

An absolutely minimal implementation of a SimpleLinkedList will just have one member variable: a pointer to keep track of the first node in the list. We typically call this node the head of the list. We will also need a few behaviors to manage and test the list:

A constructor to initialize an empty list

🔗
A destructor to delete all the nodes in the list when the list is destroyed

🔗
An insertStart function to add a new item to the start of the list

🔗
A print function to print all the items in the list

🔗

🔗

Listing 27.3.3.

🔗

class SimpleLinkedList {
private:
    ListNode<T>* head = nullptr; // Pointer to the first node in the list
public:
    // Construct an empty linked list
    SimpleLinkedList();

    // Destructor to clean up the list
    ~SimpleLinkedList();

    // Add a new element to the front of the list
    void insertStart(T value);

    // Print all elements in the list
    void print() const;
};

The constructor is easy. Because the list starts out empty, we just set the head pointer to nullptr. That is already done in the member variable declaration, so the constructor body can be empty.

🔗

SimpleLinkedList<T>::SimpleLinkedList() {
  // head is already initialized to nullptr
}

We will tackle the rest of the implementation in the following sections.

🔗

Checkpoint 27.3.1.

Consider Figure 27.3.1 and Listing 27.3.2. Which job seems like it would be easiest to implement?

🔗

Checking to see if the list is empty
To check if the list is empty, we just need to check if the head pointer is null.
Checking the size of the list
To check the size of the list, we would need to traverse the entire list and count the nodes.
Destruct the list
To delete all the items in the list, we would need to traverse the entire list and delete each node.
Print the list
To print the items in the list, we would need to traverse the entire list and output each node’s data.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next