How to create a doubly linked list with helper methods in C++

Overview

A doubly linked list is basically the same as a normal Linked List. The only difference is that nodes have a pointer, commonly called prev, that point to the previous node in the list. Also, doubly linked lists often have a tail pointer.

The differences between a normal and a Doubly Linked List

Code

We'll make our doubly linked list, making functions to add and delete nodes from the ends of the list, and a utility function to print its contents.

We'll use templates for our implementation to make doubly linked lists that can hold (most) any data type as long as the list is consistent. Our implementation will also be in separate files, so the job is easier to manage. Let's get started.

The header file

We'll first define our doubly linked list's structure in linked_list.h. We'll have a struct, list_item, to act as a singular node in our list and a linked_list class that will be our doubly linked list.

#ifndef __LIST_H // These two lines and the last line ensure
#define __LIST_H // So that this file can be imported in other files.
#include <cstdlib> // For memory management.
// This struct just holds a single data item, i.e., a node.
template <class T>
struct list_item {
    T value;
    list_item<T> *next;
    list_item<T> *prev;
    // Constructor.
    list_item(T the_value) {
        this->value = the_value;
        this->next = NULL;
        this->prev = NULL;
    }
};
// The generic Linked List class.
template <class T>
class linked_list {
    list_item<T> *head;
    list_item<T> *tail;
public:
    // Constructor.
    linked_list();
    // Destructor.
    ~linked_list();
    // Insertion functions.
    void insert_head(T item);
    void insert_tail(T item);
    // Lookup functions.
    list_item<T> *get_head();
    list_item<T> *get_tail();
    // Deletion functions.
    void delete_head();
    void delete_tail();
    // Utility functions.
    void print();
};
#endif

The class methods

We'll now make each method of the class, including the constructor and the destructor, in a new file called linked_list.cpp. Make sure to include the header file we just created.

Note: While we can make the destructor now, we'll do so later. We'll first make our deletion methods.

linked_list()

This linked_list() is the constructor. We just need to ensure that head and tail are set to NULL whenever we make a new object of the linked_list class.

// Constructor; set both head and tail to NULL.
template <class T>
linked_list<T>::linked_list() {
	head = NULL;
	tail = NULL;
}

insert_head()

We'll now create a method to add a new element to the head (left-most side) of the doubly linked list:

  • First, check whether the doubly linked list is empty or not. If it is empty, we make the new element both the head and the tail and then stop.
  • Then create a new node, as seen below in line 9.
  • Set head's prev to this new node.
  • Set the new node's next to the head.
  • Make the head point to the new node.

Note: The insert_tail() function is also given in the code below. It follows the same process as shown above, but at the end of the doubly linked list.

// Insert elements to the head (left) of the list.
template <class T>
void linked_list<T>::insert_head(T item) {
	if(head == NULL) {
        head = new list_item<T>(item);
        tail = head;
        return;
    }
    list_item<T> *Node = new list_item<T>(item);
    head->prev = Node;
    Node->next = head;
    head = Node;
}
// Insert elements to the tail (right) of the list.
template <class T>
void linked_list<T>::insert_tail(T item) {
	if(tail == NULL) {
        tail = new list_item<T>(item);
        head = tail;
        return;
    }
    list_item<T> *Node = new list_item<T>(item);
    tail->next = Node;
    Node->prev = tail;
    tail = Node;
}

delete_head()

We'll now create a method to delete an element from the head (left-most side) of the doubly linked List:

  • First, check whether the doubly linked list is empty or not. If it is empty, we then do nothing.
  • Second, check whether the doubly linked List has just one node. If it does, we just delete that node and set the head and tail pointers to NULL.
  • Create a new node, current, which is the second node in the list.
  • delete the first node.
  • Make head point to the second node, i.e., current.
  • Set this node's prev to NULL.

Basically, we'll reverse of what we do in insert_head(). Consult the code below to see the presented logic in action.

Note: The delete_tail() function is also given in the code below. It follows the same process as discussed above, but at the end of the doubly linked list.

// Delete element from the head (left) of the list.
template <class T>
void linked_list<T>::delete_head() {
	if(head == NULL) {
        return;
    }
    else if(head->next == NULL) {
    	delete head;
        head = NULL;
        tail = NULL;
    }
    else {
        list_item<T> *current = head->next;
        delete head;
        head = current;
        head->prev = NULL;
    }
}
// Delete element from the tail (right) of the list.
template <class T>
void linked_list<T>::delete_tail() {
	if(head == NULL) {
        return;
    }
    else if(head->next == NULL) {
    	delete head;
        head = NULL;
        tail = NULL;
    }
    else {
        list_item<T> *current = tail->prev;
        delete tail;
        tail = current;
        tail->next = NULL;
    }
}

~linked_list()

This ~linked_list() is the destructor. It is vital for a linked list so that memory is freed up after the executable file is run. Anyway, all we have to do is just delete every single node in the doubly linked list.

// Destructor; memory management. VERY IMPORTANT.
template <class T>
linked_list<T>::~linked_list() {
    for(int i = 0; i < length(); i++) {
        delete_head();
    }
}
// To find the length of the list.
// The explanation for this method is very similar
// to the print() method, which will be explained
// later.
template <class T>
int linked_list<T>::length() {
	int count = 0;
    if(head == NULL) {
        return count;
    }
    else {
        list_item<T> *current = head;
        while(current != NULL) {
            count++;
            current = current->next;
        }
        return count;
    }
}

print()

Lastly, we'll print the contents of our doubly linked list so we know it works. This is pretty simple. All we have to do is:

  • Check whether the doubly linked list has no nodes. If so, just print that the list is empty.
  • Traverse through the list and print every node we come across.
    • Create a new node, current, and have it be the first node of the list.
    • If there are more nodes after current, we print current's value and a separator.
    • We then move on to that node after current.
    • If there are no more nodes after current, we print its value and call it a day.
template <class T>
void linked_list<T>::print() {
    if(head == NULL) {
        cout << "empty list";
    } else {
        list_item<T> *current = head;
        while(current != NULL) {
            if(current->next != NULL) {
                cout << current->value << " <=> ";
            } else {
                cout << current->value;
            }
            current = current->next;
        }
    }
}

Put it all together

Look at the code below to see how the doubly linked list works. We've also made a main.cpp file so we can run the code and see how to use the doubly linked list.

main.cpp
linked_list.h
linked_list.cpp
#ifndef __LIST_CPP
#define __LIST_CPP
#include "linked_list.h"
#include <cstdlib> // Allows use of memory management functions.
#include <iostream> // Allows use of cout.
using namespace std; // Makes writing code easier for this example.
// Constructor; set both head and tail to NULL.
template <class T>
linked_list<T>::linked_list() {
	head = NULL;
	tail = NULL;
}
// Destructor; memory management. VERY IMPORTANT.
template <class T>
linked_list<T>::~linked_list() {
    for(int i = 0; i < length(); i++) {
        delete_head();
    }
}
// Insert elements to the head (left) of the list.
template <class T>
void linked_list<T>::insert_head(T item) {
	if(head == NULL) {
        head = new list_item<T>(item);
        tail = head;
        return;
    }
    list_item<T> *Node = new list_item<T>(item);
    head->prev = Node;
    Node->next = head;
    head = Node;
}
// Insert elements to the tail (right) of the list.
template <class T>
void linked_list<T>::insert_tail(T item) {
	if(tail == NULL) {
        tail = new list_item<T>(item);
        head = tail;
        return;
    }
    list_item<T> *Node = new list_item<T>(item);
    tail->next = Node;
    Node->prev = tail;
    tail = Node;
}
// Used for checking purposes.
template <class T>
list_item<T>* linked_list<T>::get_head() {
	return head;
}
// Used for checking purposes.
template <class T>
list_item<T>* linked_list<T>::get_tail() {
	return tail;
}
// Used for the destructor.
template <class T>
void linked_list<T>::delete_head() {
	if(head == NULL) {
        return;
    }
    else if(head->next == NULL) {
    	delete head;
        head = NULL;
        tail = NULL;
    }
    else {
        list_item<T> *current = head->next;
        delete head;
        head = current;
        head->prev = NULL;
    }
}
// Good to have.
template <class T>
void linked_list<T>::delete_tail() {
	if(head == NULL) {
        return;
    }
    else if(head->next == NULL) {
    	delete head;
        head = NULL;
        tail = NULL;
    }
    else {
        list_item<T> *current = tail->prev;
        delete tail;
        tail = current;
        tail->next = NULL;
    }
}
// For the destructor.
template <class T>
int linked_list<T>::length() {
	int count = 0;
    if(head == NULL) {
        return count;
    }
    else {
        list_item<T> *current = head;
        while(current != NULL) {
            count++;
            current = current->next;
        }
        return count;
    }
}
// For demonstration purposes.
template <class T>
void linked_list<T>::print() {
    if(head == NULL) {
        cout << "empty list";
    } else {
        list_item<T> *current = head;
        while(current != NULL) {
            if(current->next != NULL) {
                cout << current->value << " <=> ";
            } else {
                cout << current->value;
            }
            current = current->next;
        }
    }
}
#endif

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved