How to Implement a Doubly Linked List in C++
-
Use
structto Implement Doubly Linked List in C++ -
Use the
std::listContainer as Doubly Linked List in C++
This article will demonstrate multiple methods about how to implement a doubly linked list in C++.
Use struct to Implement Doubly Linked List in C++
Linked lists are considered one of the most common data structures you can encounter in programming. These structures are linked in the sense that each node contains the address of another. Linked lists have two types: singly-linked lists and doubly linked lists. A singly-linked list contains nodes that only point to the next node in the list; thus, it makes the traversal of the structure one-directional. On the other hand, doubly linked lists provide two-directional access from each node in the list.
In this case, we implement a doubly linked list using the struct command, making all its data members public and defining the element manipulation functions separately. Note that one may prefer an object-oriented version with member functions providing the element manipulation routines and some record-keeping data members.
The following example code includes the driver code in the main function that tests the basic usage scenario, where the string vector elements are inserted into a list, and then the list is deallocated. We utilize the new operator to dynamically allocated each node, and consequently, the freeNodes function iterates through the list to call delete on each Node.
The method of separately allocating each Node could be inefficient if the user wants to design a relatively high-performance linked-list structure. One might consider a bulk allocation of memory resources to add new nodes quickly and, when not needed, deallocate multiples at the same time. In this design, we start building the list with the valid element representing the first node in the structure. Some implementations may create a dummy element, which denotes the head of the list but does not contain the element data.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
struct Node *prev{};
string data;
};
template <typename T>
struct Node *addNewNode(struct Node *node, T &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->prev = node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodeData(struct Node *node) {
cout << "data: " << node->data << endl;
}
int main() {
struct Node *tmp, *root = nullptr;
struct Node *end = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
root = addNewNode(root, data_set.at(0));
tmp = root;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
if (it == data_set.end() - 1) end = tmp;
}
printNodeData(root);
printNodeData(end);
freeNodes(root);
return EXIT_SUCCESS;
}
Output:
data: Rocket Lake
data: Meteor Lake
You can utilize linked lists as building blocks of more specialized data structures like stacks, deques, queues, or circular lists. The latter is interesting because it’s essentially a doubly linked list where the last node points to the first element as the next node, and correspondingly the first one points to the last element as the previous node. Notice that the following code snippet adds the printNodes function to display the contents of each node in the constructed list.
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct Node {
struct Node *next{};
struct Node *prev{};
string data;
};
struct Node *addNewNode(struct Node *node, string &data) {
auto new_node = new Node;
if (node) node->next = new_node;
new_node->prev = node;
new_node->next = nullptr;
new_node->data = data;
return new_node;
}
void freeNodes(struct Node *node) {
struct Node *tmp = nullptr;
while (node) {
tmp = node;
node = node->next;
delete tmp;
}
}
void printNodes(struct Node *node) {
auto count = 0;
while (node) {
cout << "node " << count << " - data: " << node->data << endl;
node = node->next;
count++;
}
}
int main() {
struct Node *tmp, *root = nullptr;
struct Node *end = nullptr;
vector<string> data_set = {"Rocket Lake", "Alder Lake", "Tiger Lake",
"Meteor Lake"};
root = addNewNode(root, data_set.at(0));
tmp = root;
for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
tmp = addNewNode(tmp, *it);
if (it == data_set.end() - 1) end = tmp;
}
printNodes(root);
freeNodes(root);
return EXIT_SUCCESS;
}
Output:
node 0 - data: Rocket Lake
node 1 - data: Alder Lake
node 2 - data: Tiger Lake
node 3 - data: Meteor Lake
Use the std::list Container as Doubly Linked List in C++
Alternatively, one can utilize the std::list container from C++ STL, which is usually implemented as the doubly linked list and provides various element manipulation functions. Additionally, the std::list container is implemented to support quite powerful algorithms included in the standard library so the user can save time on development if some very special performance characteristics are not required.
#include <iostream>
#include <list>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::list;
using std::string;
template <typename T>
void printList(std::list<T> l) {
for (const auto &item : l) {
cout << item << "; ";
}
cout << endl;
}
int main() {
std::list<int> l = {1, 2, 3, 4};
l.push_back(5);
l.push_front(0);
printList(l);
auto it = std::find(l.begin(), l.end(), 3);
if (it != l.end()) {
l.insert(it, 99);
}
printList(l);
return EXIT_SUCCESS;
}
Output:
0; 1; 2; 3; 4; 5;
0; 1; 2; 99; 3; 4; 5;
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook