Skip to content

Instantly share code, notes, and snippets.

@kazmura11
Last active January 21, 2020 16:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kazmura11/a3079a5dd7babdfc7568 to your computer and use it in GitHub Desktop.
Save kazmura11/a3079a5dd7babdfc7568 to your computer and use it in GitHub Desktop.
DoublyLinkedList implementation (C++)
#include <iostream>
#include <string>
#include <stdexcept>
using namespace std;
template <typename T>
struct Node
{
T value_;
Node *prev_;
Node *next_;
Node()
{
prev_ = this;
next_ = this;
}
Node(T value, Node *prev, Node *next)
{
value_ = value;
prev_ = prev;
next_ = next;
}
};
template <typename T>
class DoublyLinkedList
{
private:
Node<T> *dummy_;
int size_;
public:
DoublyLinkedList()
{
dummy_ = new Node<T>();
size_ = 0;
}
~DoublyLinkedList()
{
clear();
}
void add(T v, Node<T> *node)
{
// insert a new node between the current node and the next of current node
Node<T> *newNode = new Node<T>(v, node, node->next_);
node->next_->prev_ = newNode;
node->next_ = newNode;
// update the current node
node = newNode;
size_++;
}
void push_front(T value)
{
Node<T> *cur = dummy_;
add(value, cur);
}
void push_back(T value)
{
Node<T> *cur = dummy_->prev_;
add(value, cur);
}
bool empty()
{
return dummy_->next_ == dummy_;
}
T remove(Node<T> *node)
{
if (empty())
{
throw std::logic_error("node is empty!");
}
T ret = node->value_;
node->prev_->next_ = node->next_;
node->next_->prev_ = node->prev_;
delete node;
node = node->prev_;
size_--;
return ret;
}
T pop_front()
{
Node<T> *cur = dummy_->next_;
return remove(cur);
}
T pop_back()
{
Node<T> *cur = dummy_->prev_;
return remove(cur);
}
void dump()
{
Node<T> *ptr = dummy_->next_;
while (ptr != dummy_)
{
cout << ptr->value_ << ' ';
ptr = ptr->next_;
}
cout << '\n';
}
void clear()
{
while(!empty())
{
pop_front();
}
}
int size()
{
return size_;
}
};
int main()
{
DoublyLinkedList<int> list;
list.push_front(13);
list.push_front(7);
list.push_front(10);
cout << "size: " << list.size() << '\n';
list.dump();
list.push_back(11);
cout << "size: " << list.size() << '\n';
list.dump();
cout << "remove: " << list.pop_back() << '\n';
cout << "size: " << list.size() << '\n';
list.dump();
cout << "remove: " << list.pop_front() << '\n';
cout << "size: " << list.size() << '\n';
list.dump();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment