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

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

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. 

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

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...

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...

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.

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

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.

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