Last active
January 21, 2020 16:04
-
-
Save kazmura11/a3079a5dd7babdfc7568 to your computer and use it in GitHub Desktop.
DoublyLinkedList implementation (C++)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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