Chapter 2. Storing Data in Lists and Linked Lists

In the previous chapter, we discussed basic C++ programming, so that now we can build a program and run it. We also tried to find out the complexity of the code flow using algorithm analysis. In this chapter, we are going to learn about building the list and linked list data structures and find out the complexity of each data structure. To understand all of the concepts in these data structures, these are the topics we are going to discuss:

• Understanding the array data type and how to use it
• Building the list data structure using the array data type
• Understanding the concept of node and node chaining
• Building SinglyLinkedList and DoublyLinkedList using node chaining
• Applying the Standard Template Library to implement the list and linked list

Technical requirements

To follow along with this chapter including the source code, we require the following:

• A desktop PC or Notebook with Windows, Linux, or macOS
• GNU GCC v5.4.0 or above
• Code::Block IDE v17.12 (for Windows and Linux OS) or Code::Block IDE v13.12 (for macOS)
• You will find the code files on GitHub at https://github.com/PacktPublishing/CPP-Data-Structures-and-Algorithms

Getting closer to an array

An array is a series of elements with the same data type that is placed in contiguous memory locations. This means that the memory allocation is assigned in consecutive memory blocks. Since it implements contiguous memory locations, the elements of the array can be individually accessed by the index. Let's take a look at the following array illustration:

As we can see in the preceding illustration, we have an array containing five elements. Since the array uses zero-based indexing, the index starts from 0. This index is used to access the element value and to also replace the element value. The memory address stated in the illustration is for example purposes only. In reality, the memory address might be different. However, it illustrates that the memory allocation is contiguous. 

Now, if we want to create the preceding array in C++, here is the code:

// Project: Array.cbp
// File   : Array.cpp

#include <iostream>

using namespace std;

int main()
{
    //...

Building a List ADT

A list is a sequence of items with similar data types, where the order of the item's position matters.There are several common operations that are available in a List ADT, and they are:

• Get(i), which will return the value of selected index, i. If the i index is out of bounds, it will simply return -1.
• Insert(i, v), which will insert the v value at the position of index i.
• Search(v), which will return the index of the first occurrence of v (if the v value doesn't exist, the return value is -1).
• Remove(i), which will remove the item in the i index. 

Note

For simplicity, we are going to build a List ADT that accepts int data only, from zero (0) and higher. 

Now, by using the array data type we discussed earlier, let's build a new ADT named List which contains the preceding operations. We need two variables to hold the list of items (m_items) and the number of items in the list (m_count). We will make them private so that it cannot be accessed from the outside class. All four operations...

Introduction to node

The node is the basic building block of many data structures which we will discuss in this book. Node has two functions. Its first function is that it holds a piece of data, also known as the Value of node. The second function is its connectivity between another node and itself, using an object reference pointer, also known as the Next pointer. Based on this explanation, we can create a Node data type in C++, as follows:

class Node
{
public:
    int Value;
    Node * Next;
};

We will also use the following diagram to represent a single node:

Now, let's create three single nodes using our new Node data type. The nodes will contain the values 7, 14, and 21 for each node. The code should be as follows:

Node * node1 = new Node;
node1->Value = 7;

Node * node2 = new Node;
node2->Value = 14;

Node * node3 = new Node;
node3->Value = 21;

Note that, since we don't initialize the Next pointer for all nodes, it will be automatically filled with the null pointer (NULL). The...

Building a Singly Linked List ADT

The Singly Linked List (also known as the linked list) is a sequence of items linked with each other. It's actually a chaining of nodes, where each node contains the item's value and the next pointer. In other words, each item in the linked list has a link to its next item in the sequence. The thing that differs between the linked list and the node chain is that the linked list has a Head and a Tail pointer. The Head informs the first item and the Tail informs the last item in the linked list. Similar to the List ADT, we discussed earlier, the linked list has Get(), Insert(), Search(), and Remove() operations, where all of the operations have the same functionality compared to List. However, since we now have Head and Tail pointers, we will also create others operations, and these are InsertHead(), InsertTail(), RemoveHead(), and RemoveTail(). The declaration of the LinkedList class should be as follows:

template <typename T>
class LinkedList
{
private...

Building the Doubly Linked List ADT

The Doubly Linked List is almost the same as the Singly Linked List, except the Node used by Doubly Linked List has a Previous pointer instead of only having the Next pointer. The existence of the Previous pointer will make the Doubly Linked List possible to move backwards from Tail to Head. As a result, we can reduce the complexity of the RemoveTail() operation to O(1) instead of O(N), like we have in the Singly Linked List data type. We are going to discuss this further later in this section. As of now, let's prepare the new Node data type.

Refactoring the Node<T> data type

Before we build a Doubly Linked List, we need to add a Previous pointer to the existing Node data type. To avoid any confusion, we will create a new data type named DoublyNode with the following declaration:

template <typename T>
class DoublyNode
{
    public:
        T Value;
DoublyNode<T> * Previous;
        DoublyNode<T> * Next;

        DoublyNode(T value...

Applying List and LinkedList using STL

C++ has three data types which we can use to store specific items such as List, SinglyLinkedList, and DoublyLinkedList. std::vector can be used as List , std::forward_list can be used as SinglyLinkedList, and std::list can be used as DoublyLinkedList. They both have fetching, inserting, searching, and removing operations. However, the method names they have are different with our developed data type, and we are going to discuss this in this section. In this section, we are going to discuss std::vector and std::list only, since std::forward_list is similar to std:: list.

std::vector

A vector, which is like an array, is a container to store a bunch of items contiguously. However, the vector can double its size automatically if we insert a new item when its capacity has been reached. Also, vectors have many member functions that arrays don't have, and provide iterators that act like pointers but aren't.

Don't forget to include the vector header at the beginning...

Summary

We have successfully built our own data structures in C++ and have found out the time complexity of each data structure. As we have discussed, each data structure has its own strengths and drawbacks. For instance, by using List, we can access the last element faster than LinkedList. However, in the List, removing the first element will take even more time, since we remove the first element since it needs to re-struct the array inside the List.

In the next chapter, we are going to learn how to build other data structures based on the data structures we have discussed in this chapter. These are stack, queue, and dequeue.

QA section

• What does zero-based indexing mean in an array?
• How do we find out how many elements an array has?
• What does a pointer in C++ do?
• Suppose we have a pointer named ptr. How do we get the value of the address that the ptr points to?
• Specify four common operations in List ADT.
• A node has two functions, please specify.
• What is the difference between a Singly Linked List and a Doubly Linked List?
• What is the STL function that we can use for list and linked list in C++?

Further reading

For a complete summary of time complexity for each data structure that we have discussed in this chapter, please take a look the following table:

Other reading sources you may find useful:

• https://www.geeksforgeeks.org/list-cpp-stl/
• http://www.cplusplus.com/reference/list/list/
• http://www.cplusplus.com/reference/vector/vector/