Linked Lists

1. Introduction

A linked list can store a lot of data. Once the data is in the list, more data can be easily added. Linked lists are very useful when we do not know the size of data in advance. The size of the list can be determined and updated repeatedly by the user during the program execution.

Here is an example of a problem that is easiest to solve using linked lists.

Problem 1.

The user enters integers one by one. The input is over when the user decides to enter -9. After this number -9, the user gives one more positive integer q. The program needs to add q to each of the integers and then print the new updated integers in the same order in which they were received.

Before we can create programs that use linked lists, we have to learn about structures in C++.

2. Structures

We will now learn how to create more complex data types that have multiple components. We have already made some programs with basic data types such as int, long, double, and std::string.

The keyword struct enables us to define custom types of data and then use this new type in our program.

One example of such structure is Mountain. The structure will have three components: name, height, and location. The declaration is done like this:

struct Mountain{
   std::string name;
   double height;
   std::string location;
};

Remark: The declaration must end with ;.

If the declaration is placed before the function main() and before all other functions, then we are allowed to use the following command

Mountain x;

The command will ask the computer to give us sufficient memory for one mountain and allow us to call it x. We can access the individual components name, height, and location by typing x.name, x.height, and x.location.

This is one example of a program that uses the newly created structure Mountain.

#include<iostream>
struct Mountain{
   std::string name;
   double height;
   std::string location;
};
void printData(Mountain m){
   std::cout << m.name << " on ";
   std::cout << m.location << " has height ";
   std::cout<< m.height << " meters.\n";
}
int main(){
   Mountain x; 
   Mountain y;
   x.name="Mount Everest"; x.height=8848.13; x.location="Earth";
   y.name="Olympus Mons"; y.height=21287.4; y.location="Mars";
   printData(x);
   printData(y);
   return 0;
}

2.1. Structures: practice problems

Problem 2.

Create the function tallerMountain that has two arguments a and b of type Mountain. The function should return the height of the taller of the two mountains.

You should only write the code that replaces the text // ??? //.

double tallerMountain(Mountain a, Mountain b){
   // ??? //
}

Problem 3.

Create the function tallerMountain that has two arguments a and b of type Mountain. The function should return the name of the taller of the two mountains.

You should only write the code that replaces the text // ??? //.

std::string tallerMountain(Mountain a, Mountain b){
   // ??? //
}

3. List node

The main ingredient is an object of the structure ListNode. The list node consists of two pieces of data: content and a pointer aNext that keeps the address of the next element of the list.

\[\begin{array}{|c|}\hline \mbox{content}\\ \hline \mbox{aNext}\\ \hline \end{array}\]

The declaration of the structure is

struct ListNode{
   long content;
   ListNode *aNext;
};

When the user enters the integers we will keep them in a linked list. The list will be identified by the pointer to its first element. This pointer will be called aHead. The last node in the list will have a special value, nullptr, assigned to its component aNext. The value nullptr points nowhere and it will signify to us that we are at the end of the list. The ListNode is declared with

ListNode *aHead;

4. Visual representation

The algorithms with linked lists require careful drawing of memory diagrams. Very often the tiny mistakes can result in pointers containing wrong addresses. Accessing a wrong address will cause programs to behive in unexpected ways, or to crash.

The two components of each node are quite different. The first one is a content, and that component does not require special drawing skills. We just write the value. The second component of a node is a pointer. The pointer contains an address. The address is a very big number that looks quite random. So, instead of writing those big numbers we will draw arrows.

aHead 11 12 13 14 15 16

The picture above shows one linked list that contains the nodes whose contents are 11, 12, 13, 14, 15, and 16.

The first element in our drawing is the variable aHead. This variable is a pointer. The pointer contains the address of the first node - the node that contains 11. The variable aHead is drawn as a box. The arrow goes from the box to the node of the list.

The second element is nour drawing is the first node. The node has the content 11. The second component is the address of the node that contains 12. We draw the arrow from this second component to the node that contains 12.

Similar rules are used when drawing the remaining nodes with contents 12, 13, 14, and 15.

The last node, whose content is 16, is somewhat different. It is the last node in the list. It also has two components as every other node. However, the second component has the special value. The value is called nullptr. This value signifies the end of the list. We draw a thick dot to represent nullptr.

If addressOfANode is a pointer to a node in the list, then we can check if the node is the last node in the list with the following way:

if( (*addressOfANode).aNext == nullptr ){
   std::cout<<"The last node\n";
}
else{
   std::cout<<"Not the last node\n";
}

5. Simple problems

Any program with linked lists requires us to construct the list. The code that creates the list is a bit longer. In this section the auto-grader will take care of the construction of the list. The problems will ask us to complete the code for very simple functions. The functions will receive the pointers to the heads of the lists. The lists will be created and properly filled with the data.

Problem 4.

Create a function contentOfTheHead that returns the content of the head of the linked list. The argument of the function is aHead. It is the pointer that contains the address of the head. If the function receives the nullptr, then the function should return -777. However, if the function receives a pointer to the head of a real linked list, then it should return the content. Your code should replace the text // ??? // below.

long contentOfTheHead(ListNode* aHead){
   if(aHead==nullptr){return -777;}
   // ??? //
}

Problem 5.

Create a function contentOfTheSecondNode that returns the content of the second node of the linked list. The argument of the function is aHead. It is the pointer that contains the address of the head. If the function receives the nullptr, then the function should return -777. However, if the function receives a pointer to the head of a real linked list, then it should check whether the list has another node. If it does not, then the function should return -555. If has at least two nodes, then the function should return the content of the second node. Your code should replace the text // ??? // below.

long contentOfTheSecondNode(ListNode* aHead){ 
   // ??? //
}

Problem 6.

Create a function contentOfTheHeadIfItIsTheLastNode that returns the content of the head, if the head is also the last node of the linked list. The argument of the function is aHead. It is the pointer that contains the address of the head. If the function receives the nullptr, then the function should return -777. However, if the function receives a pointer to the head of a real linked list, then it should check whether the head of the list is the last node as well. If it is, then the function should return the content of the head. If the head is not the last node, i.e. the list has at least two nodes, then the function should return -222. Your code should replace the text // ??? // below.

long contentOfTheHeadIfItIsTheLastNode(ListNode* aHead){ 
   // ??? //
}

Problem 7.

Create a function contentOfTheLastNode that returns the content of the last node of the linked list. The argument of the function is aHead. It is the pointer that contains the address of the head. If the function receives the nullptr, then the function should return -777. However, if the function receives a pointer to the head of a real linked list, then it should find the last node and return its content. Your code should replace the text // ??? // below.

long contentOfTheLastNode(ListNode* aHead){ 
   // ??? //
}

6. Creating list from user input

We will now solve the problem 1.

Problem 1.

The user enters integers one by one. The input is over when the user decides to enter -9. After this number -9, the user gives one more positive integer q. The program needs to add q to each of the integers and then print the new updated integers in the same order in which they were received.

In the main function we will declare a variable aHead of type ListNode*.

ListNode* aHead;

After the declaration above, the pointer aHead is not initialized. When the user enters the first number (that we will call input) we will allocate the memory for the first ListNode and set its content to input. We will set the aNext component of this node to contain the value nullptr because in the very beginning this first list element is also its last element. The following code accomplishes the input of the first element of the list.

int userInput;
ListNode* aHead;
std::cout << "Insert the first element of the list: ";
std::cin>>userInput;
aHead=new ListNode;
(*aHead).content=userInput;
(*aHead).aNext=nullptr;

The user needs to supply the remaining elements of the list. Since we must keep the address of the first element of the list, we need a new variable, other than aHead to facilitate the creation of the list. We will use the name runner to call this new pointer. The pointer runner will keep track of the last element of the list that is entered. Some people like to call it tail. In the beginning runner needs to point at the exact same location as aHead. This is accomplished with

ListNode *runner;
runner=aHead;

When the user gives us the next value in userInput we first check whether it is \(-9\). If it is, we will not put this in our list. Instead, we will finish the data entry. If the userInput is a value other than \(-9\), we need to create a new node whose content is userInput. We also need to link this new node to the end of the current list. Since runner points to the tail of the list, our while loop has to look like this

while(userInput!=-9){
   std::cout << "Insert an element of the list (-9 for the end): ";
   std::cin>>userInput;
   if(userInput!=-9){
      // *runner is the last node in the list (tail)
      // (*runner).aNext is currently nullptr
      // We now allocate new memory for ListNode and make
      // (*runner).aNext to contain the address
      // of this new ListNode
      (*runner).aNext=new ListNode;

      // runner is no more pointing to the tail
      // The next line updates the runner to point
      // to the newly created tail
      runner=(*runner).aNext;
            
      // We now set the content of the tail
      (*runner).content=userInput;
      // and make sure that the tail‘s pointer
      // to the the next is set to nullptr
      (*runner).aNext=nullptr;
   }
}

Once the list is created we will read another integer q, start from aHead, add q to each term and print the result on standard input.

long q;
std::cout<<"Insert q\n";
std::cin>>q;
std::cout << "List printout: " << std::endl;
runner=aHead;
while(runner!=nullptr){
    std::cout << q+(*runner).content << " ";
    runner=(*runner).aNext;
}
std::cout << std::endl;

The final task is to free the memory occupied by our list. This time we have to start from the back of the list and delete the terms. This is elegantly accomplished using recursion. In each step we perform two steps in this precise order

Step 1. clean the tail
Step 2. delete the memory occupied by the current head.

Notice how tricky the Step 1 is. It will recursively first call the cleaning of the tail of tail. We will create the function freeTheMemory and apply it to head. The function looks like this

void freeTheMemory(ListNode *runner){
   if( runner!=nullptr){
      freeTheMemory((*runner).aNext);
      delete runner;
   }
}

The entire code is given below. You may notice that the compilation of the code requires the addition of compiler flag -std=c++11. The reason is that we are using nullptr that is supported only in C++11 standard. More explanation is provided below.

Remark: The keyword nullptr was introduced in C++11. In traditional C++ the number 0 was used instead. Those who wanted the clear syntax were allowed to use the word NULL which was essentially replaced by 0 during the pre-processing by the compiler. Since we are learning best programming practices, we will not use NULL nor 0 for pointers. Instead we will insist on nullptr. The trouble is that we now must invoke the C++11 compiler flag in order for code to be compiled. Thus we will notice a slight change in our compiler directive.

// linkedList.cpp
// compile with
// c++ linkedList.cpp -o lList -std=c++11
// execute with
// ./lList
#include <iostream>
struct ListNode{
   long content;
   ListNode* aNext;
};
void freeTheMemory(ListNode *runner){
   if( runner!=nullptr){
      freeTheMemory((*runner).aNext);
      delete runner;
   }
}
int main(){
   int userInput;
   ListNode* aHead;
   std::cout << "Insert the first element of the list: ";
   std::cin>>userInput;
   aHead=new ListNode;
   (*aHead).content=userInput;
   (*aHead).aNext=nullptr;
   ListNode* runner;
   runner=aHead;
   while(userInput!=-9){
      std::cout << "Insert an element of the list (-9 for the end): ";
      std::cin>>userInput;
      if(userInput!=-9){
         (*runner).aNext=new ListNode; 
         runner=(*runner).aNext;
         (*runner).content=userInput;
         (*runner).aNext=nullptr;
      }
   } 
   long q;
   std::cout<<"Insert q\n";
   std::cin>>q;
   std::cout << "List printout: " << std::endl;
   runner=aHead;
   while(runner!=nullptr){
      std::cout << q+(*runner).content << " ";
      runner=(*runner).aNext;
   }
   std::cout << std::endl;
   // FREEING THE MEMORY
   freeTheMemory(aHead);
   return 0;
}

Note. Equivalent form of (*runner).content is runner->content.

The first version, (*runner).code is considered less elegant. However, it is preferred while learning the language and this website will have a lot of (*runner).code commands. Once you become a more advanced user of C++, you may decide that switching to runner->content is necessary due to peer pressure.

Problem 8.

The user input consists of integers. The input -9 is the end, and unless it is the first integer, it is not to be considered the part of the input. Create a linked list from the numbers that the user has entered. The user enters another integer. If this integer is in the list, delete its first occurrence from the list and print the remaining list. If it is not in the list, print the original list.

7. Practice problems

Problem 9.

The user enters the integers though the standard input. The input -9 is the end, and unless it is the first integer, it is not to be considered the part of the input. Create a linked list from the numbers that the user has entered. The user enters another integer. If this integer is in the list, delete its last occurrence from the list and print the remaining list. If it is not in the list, print the original list.

Problem 10.

Create a function that reverses the nodes in the linked list.