Book Image

C++ Data Structures and Algorithms

By : Wisnu Anggoro
5 (1)
Book Image

C++ Data Structures and Algorithms

5 (1)
By: Wisnu Anggoro

Overview of this book

C++ is a general-purpose programming language which has evolved over the years and is used to develop software for many different sectors. This book will be your companion as it takes you through implementing classic data structures and algorithms to help you get up and running as a confident C++ programmer. We begin with an introduction to C++ data structures and algorithms while also covering essential language constructs. Next, we will see how to store data using linked lists, arrays, stacks, and queues. Then, we will learn how to implement different sorting algorithms, such as quick sort and heap sort. Along with these, we will dive into searching algorithms such as linear search, binary search and more. Our next mission will be to attain high performance by implementing algorithms to string datatypes and implementing hash structures in algorithm design. We'll also analyze Brute Force algorithms, Greedy algorithms, and more. By the end of the book, you'll know how to build components that are easy to understand, debug, and use in different applications.
Table of Contents (16 chapters)
Title Page
Copyright and Credits
Packt Upsell
Contributors
Preface
Index

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