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 andDoublyLinkedList using node chaining
• Applying the Standard Template Library to implement the list and linked list

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

Anarray 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 from0. 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++,...

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 ListADT, 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 thev 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 thei index. 

Now, by using the array data type we discussed earlier, let's build a new...

Thenode 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 theValue of node. The second function is its connectivity between another node and itself, using an object reference pointer, also known as theNext pointer. Based on this explanation, we can create aNode 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 newNode data type. The nodes will contain the values 7,14, and21 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...

TheSingly 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 aHead and aTail pointer. TheHead informs the first item and theTail informs the last item in the linked list. Similar to the List ADT, we discussed earlier, the linked list hasGet(),Insert(),Search(), andRemove() operations, where all of the operations have the same functionality compared to List. However, since we now haveHead andTail pointers, we will also create others operations, and these areInsertHead(),InsertTail...

TheDoubly 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 thePrevious pointer will make the Doubly Linked List possible to move backwards fromTail toHead. As a result, we can reduce the complexity of the RemoveTail() operation toO(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 newNode data type.

Before we build a Doubly Linked List, we need to add aPrevious pointer...

C++ has three data types which we can use to store specific items such as List,SinglyLinkedList, andDoublyLinkedList.std::vector can be used asList ,std::forward_list can be used asSinglyLinkedList, andstd::list can be used asDoublyLinkedList. 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 andstd::list only, since std::forward_list is similar tostd:: list.

Avector, which is like an array, is a container to store a bunch of items contiguously...