Doubly Linked List in C++ using OOP and Template

Table of contents:

1. Introduction
2. What is a Doubly Linked List?
3. OOP Basics
4. Template
5. Useful Applications
6. Implementing a Doubly Linked List Using OOP and Template
7. Questions

Reading time: 15 minutes

Introduction

A doubly linked list is an extremely useful data structure that can permit forward and backward traversal of a list. This method of traversal is what makes it very unique and desirable in many situations.

In this article at OpenGenus, we will review how we can utilize OOP and templates to create a versatile and efficient implementation of a doubly linked list in C++.

What is a Doubly Linked List?

First of all, a doubly linked list is a list in which each data value or node contains a pointer to the previous and next element in the list. These pointers allow for traversal in the forward and backward directions. This behavior is desirable for operations such as insertion and deletion.

OOP Basics

Object-oriented Programming or OOP is a programming model that primarily focuses on the implementation of objects and their interactions with each other. Each object in the program encapsulates data and behaviors for using the data. OOP consists of many principles that make it desirable such as:

• Encapsulation
• Inheritance
• Polymorphism
• Abstraction

Encapsulation is the implementation of controlled access to the internal components of an object, which establishes boundaries that ensure data is only manipulated through specific, pre-defined methods and functions. The separation between external usage of data and internal implementation protects the data, hides implementation details, and organizes the code, making it easier to reuse or change any of the code.

Inheritance is when a base class inherits properties and implementations from another class called a parent class.

Polymorphism involves code that works with objects of different data types while still yielding the same results. This results in implementations that are extremely flexible.

Abstraction consists of focusing on important details of a program while hiding the unnecessary ones. Defining abstract classes that implement the framework of a common subclass creates a very organized and manageable code structure that makes code easier to maintain.

Template

Template allows users to create generic code that works with many data types. To use templates, you must follow the below syntax where T is the name of the type parameter that must be used as a placeholder for the data type:

    template <typename T>

A situation where templates can become essential is when working with different types of numbers. In the code below, we use a template to define a function that can find the minimum value of any two numbers, including both integers and floats:

    template <typename T>
    T findMin(T a, T b) {
    if (a < b) {
        return a;
    } else {
        return b;
    }
}

Useful Applications

• Browser History: Given the nature of a doubly linked list and its two-way traversal, it can be perfectly utilized to traverse forward and backward through browser pages. Each node would contain a pointer to the previously visited and next page.
• Text Editor: A doubly linked list can be used to implement undo/redo in a text editor since it can keep track of previously or newly added text.
• Deque: A deque or a double-ended queue is a data structure that supports insertion and deletion at both ends of the queue. Due to its double-ended nature, a doubly linked list is perfect for its implementation.

Implementing a Doubly Linked List Using OOP and Template

Now that we've covered the basics of OOP and templates, let's discuss how we can use these two concepts together to create a flexible implementation of a doubly linked list.

We can use OOP to define the structure of the doubly linked list in an organized manner and templates to ensure the list can consist of any valid data type.

We will use inheritance to create a derived doubly linked list class that inherits and extends the definition of the already defined linked list class:

template <typename T>
class Node {
public:
    Node<T> *prev;
    Node<T> *next;
    T data;
    Node(const T &value) {
        data = value;
        prev = nullptr;
        next = nullptr;
    }
};

template <typename T>
class LinkedList {
public:  
    LinkedList() {
        head = nullptr;
        tail = nullptr;
        }
};
    
template <typename T>
class DoublyLinkedList: public LinkedList {
public:
    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
       }
};

Now that we have defined the structure of the Node, LinkedList, and DoublyLinkedList classes, we can begin to define a few behaviors. First, we will implement a function that adds a new node to the beginning of the linked list:

void insertFront(const T &value) {
    Node<T> *newNode = new Node<T>(value);
    if (head == nullptr) {
        head = newNode;
        tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

Similarly, below is the implementation of a function that instead inserts a new node at the end of the linked list:

void insertEnd(const T &value) {
    Node<T> *newNode = new Node<T>(value);
    if (this->head == nullptr) {
        this->head = newNode;
        this->tail = newNode;
    } else {
        newNode->prev = this->tail;
        this->tail->next = newNode;
        this->tail = newNode;
    }
}

To instead delete a node in a given linked list, we can define the following function:

void deleteNode(const T &value) {
    Node<T> *current = this->head;
    while (current != nullptr) {
        if (current->data == value) {
            if (current->prev != nullptr)
                current->prev->next = current->next;
            else
                this->head = current->next;
                
            if (current->next != nullptr)
                current->next->prev = current->prev;
            else
                this->tail = current->prev;
                
            delete current;
            break;
        }
        current = current->next;
    }
}

We can also define a function that searches for a specific node inside the doubly linked list. If the node doesn't exist, return false. If it does exist, return true:

bool findValue(const T &value) const {
    Node<T> *current = this->head;
    while (current != nullptr) {
        if (current->data == value) {
            return true;  // Found the value, return true
        }
        current = current->next;
    }
    return false;  // Otherwise, the value was not found. Return false
}

Lastly, we can get the current size of the doubly linked list with the following function:

    int getSize() { 
        return size; 
    }

Questions