Doubly Linked List
Doubly Linked List is a special type of list where each node contains two pointer. A prev and a next pointer to the previous and the next node. In addition a node includes a data field holding the value.
As the figure shows the List has three major pointer. A head pointer pointing to the head, a tail pointer pointing to the tail and an actual pointer pointing to the recently used node. Navigation in the doubly list is possible in both ways either forward and backward easily.
Our implementation provides an insertLast and a removeFirst method which are same as a single queue. But the list has a general insert and remove method. The insert makes it possible to add a new element in a specified place while using the remove method we can delete an optional node.
#include <atomic>
#include <memory>
namespace DataStructure {
template<typename T>
class DoubleLinkedList {
struct Node {
std::shared_ptr<Node> prev() { if (auto spt = prev_.lock()) return spt; }
std::shared_ptr<Node> next() { return next_; }
std::shared_ptr<const T> data() { return data_; }
void setPrev(std::shared_ptr<Node> tmp) { prev_ = tmp; }
void setNext(std::shared_ptr<Node> tmp) { next_ = tmp; }
Node(const std::shared_ptr<Node>& p, const std::shared_ptr<Node>& n,
const std::shared_ptr<const T> d) : prev_(p), next_(n), data_(d) {}
private:
std::shared_ptr<Node> next_ = nullptr;
std::weak_ptr<Node> prev_ = nullptr;
std::shared_ptr<const T> data_ = nullptr;
};
std::shared_ptr<Node> head_ = nullptr;
std::shared_ptr<Node> tail_ = nullptr;
std::shared_ptr<Node> act_ = nullptr;
auto head() -> decltype(head_) {
return std::atomic_load(&head_);
}
auto tail() -> decltype(tail_) {
return std::atomic_load(&tail_);
}
bool _find(const std::shared_ptr<const T>&);
public:
DoubleLinkedList() = default;
// non-copyable and non-movable
DoubleLinkedList(const DoubleLinkedList&) = delete;
DoubleLinkedList& operator=(const DoubleLinkedList&) = delete;
DoubleLinkedList(const DoubleLinkedList&&) = delete;
DoubleLinkedList& operator=(const DoubleLinkedList&&) = delete;
bool isEmpty() const;
void insertLast(const std::shared_ptr<const T>&);
void insert(const std::shared_ptr<const T>&, const std::shared_ptr<const T>&);
void removeFirst();
void remove(const std::shared_ptr<const T>&);
auto first() -> decltype(head_) {
return head();
}
void print();
};
};
Instead of raw pointers this implementation uses smart pointers for easier and safer memory management. Furthermore inside the remove and insert methods, head, tail and act pointer managing happen as atomic way. Atomic store and load methods provide us that the value of the pointers almost always up to date. In simple cases using atomic operations are more efficient than lock methodology.
Method isEmpty returns back true if head is equal to null pointer.
template<typename T>
bool DataStructure::DoubleLinkedList<T>::isEmpty() const{
return head().get() == nullptr;
}
The find method returns true if the list contains a node with the sought value and set the actual pointer to it. If more node exist with the same value find returns back with the last one.
template<typename T>
bool DataStructure::DoubleLinkedList<T>::_find(const std::shared_ptr<const T>& _item) {
bool found = false;
for (auto i = head(); i != tail(); i = i->next()) {
if (*i->data() == *_item) {
act_ = i;
found = true;
}
}
return found;
}
The insertLast method creates a new node with a given value and added to the tail of the list.
template<typename T>
void DataStructure::DoubleLinkedList<T>::insertLast(const std::shared_ptr<const T>& _item) {
std::shared_ptr<Node> tmp;
if (tail().get() == nullptr) {
tmp = std::make_shared<DataStructure::DoubleLinkedList<T>::Node>(nullptr, nullptr, _item);
head_ = tail_ = act_ = tmp;
}
else {
tmp = std::make_shared<DataStructure::DoubleLinkedList<T>::Node>(tail(), nullptr, _item);
tail_->setNext(tmp);
std::atomic_store(&tail_, tmp);
std::atomic_store(&act_, tmp);
}
tmp = nullptr;
}
The insert method insert the new node after a given value or return back if the value doesn't exist or the list is empty. We have to avoid the circle references so in the inside of the node structure the previous pointer is a weak pointer. In this way only the next pointer (shared) hold the node while the previous pointer doesn't count in the reference counting.
template<typename T>
void DataStructure::DoubleLinkedList<T>::insert(const std::shared_ptr<const T>& _after, const std::shared_ptr<const T>& _item) {
bool found = _find(_after);
if (!found) {
std::cerr << "Cannot find actual element!\n";
return;
}
auto tmp = std::make_shared<DataStructure::DoubleLinkedList<T>::Node>(act_, act_->next(), _item);
act_->setNext(tmp);
act_->next()->setPrev(tmp);
std::atomic_store(&act_, tmp);
tmp = nullptr;
}
The remove methods delete the first or a specified node from the list and linked the remaining node together.
template<typename T>
void DataStructure::DoubleLinkedList<T>::removeFirst() {
auto tmp = head();
if (head() != tail()) {
std::atomic_store(&head_, head_->next());
std::atomic_store(&act_, head_->next());
head_->setPrev(nullptr);
}
else {
head_ = tail_ = act_ = nullptr;
}
tmp = nullptr;
}
template<typename T>
void DataStructure::DoubleLinkedList<T>::remove(const std::shared_ptr<const T>& _after) {
bool found = _find(_after);
if (!found) {
std::cerr << "Cannot find actual element!\n";
return;
}
auto tmp = act_;
act_->prev()->setNext(act_->next());
act_->next()->setPrev(act_->prev());
act_ = act_->next();
tmp = nullptr;
}
The print method is only for showing the data and it is not part of the data structure.
template<typename T>
void DataStructure::DoubleLinkedList<T>::print() {
for (auto i = head(); i != tail()->next(); i = i->next()) {
std::cout << *i->data() << "\n";
}
}
#include <iostream>
#include <random>
#include <functional>
#include <ctime>
#include <string>
std::cout << "Testing data structure Double Linked List ...\n\n";
////////// Using random generator engine //////////
std::default_random_engine gen((unsigned int) std::time(0));
std::uniform_int_distribution<int> distribution(1, 50);
auto randInt = std::bind(distribution, gen); // using randInt() generate integer number between (1-50)
int num = randInt();
DataStructure::DoubleLinkedList<std::string> list;
for (auto i = 0; i < num; ++i) {
list.insertLast(std::make_shared<std::string>("hello_" + std::to_string(i)));
}
list.print();
std::cout << "\n";
list.removeFirst();
list.insert(std::make_shared<std::string>("hello_" + std::to_string(5)), std::make_shared<std::string>("hello_" + std::to_string(10)));
list.remove(std::make_shared<std::string>("hello_" + std::to_string(5)));
list.print();
std::cout << "\n";
auto firstElement = list.first();
std::cout << *firstElement->data();
for (auto i = 0; i < num-1; ++i) {
list.removeFirst();
}