Skip to content

Instantly share code, notes, and snippets.

@lry127
Last active July 1, 2024 09:58
Show Gist options
  • Save lry127/cf5c311a2fc2a4acbe7127e6210a4627 to your computer and use it in GitHub Desktop.
Save lry127/cf5c311a2fc2a4acbe7127e6210a4627 to your computer and use it in GitHub Desktop.
LinkedList implementation in C++ for educational purpose
//
// Created by lry127 on 7/1/24.
//
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <algorithm>
#include <iostream>
template<typename Object>
class LinkedList {
struct ListNode {
Object *data_{};
ListNode *prev_{};
ListNode *next_{};
ListNode() = default;
explicit ListNode(const Object &data) {
data_ = new Object{data};
}
explicit ListNode(Object &&data) {
data_ = new Object{std::move(data)};
}
ListNode(const Object &data, ListNode *prev, ListNode *next): prev_(prev), next_(next) {
data_ = new Object{data};
}
ListNode(Object &&data, ListNode *prev, ListNode *next): prev_(prev), next_(next) {
data_ = new Object{std::move(data)};
}
~ListNode() {
delete data_;
}
};
public:
class ConstIterator {
friend class LinkedList;
public:
const Object &operator*() const {
return get_underlying_data_();
}
[[nodiscard]] bool operator==(ConstIterator rhs) const {
return data_node_ == rhs.data_node_;
}
[[nodiscard]] bool operator!=(ConstIterator rhs) const {
return !operator==(rhs);
}
ConstIterator &operator++() {
data_node_ = data_node_->next_;
return *this;
}
ConstIterator operator++(int) {
ConstIterator old_iter{this};
++*this;
return old_iter;
}
ConstIterator &operator--() {
data_node_ = data_node_->prev_;
return *this;
}
ConstIterator operator--(int) {
ConstIterator old_iter{this};
--*this;
return old_iter;
}
ConstIterator operator+(const int advancement) {
for (int i = 0; i < advancement; ++i) {
++*this;
}
return *this;
}
protected:
explicit ConstIterator(ListNode *node): data_node_(node) {
}
Object &get_underlying_data_() const{ return *data_node_->data_; }
ListNode *data_node_;
};
class Iterator : public ConstIterator {
friend class LinkedList;
public:
Object &operator*() {
return ConstIterator::get_underlying_data_();
}
const Object &operator*() const {
return ConstIterator::get_underlying_data_();
}
protected:
explicit Iterator(ListNode *node): ConstIterator(node) {
};
};
LinkedList() {
init();
}
LinkedList(const LinkedList &rhs) {
init();
for (ConstIterator iter = rhs.begin(); iter != rhs.end(); ++iter) {
insert(--end(), *iter);
}
size_ = rhs.size_;
}
LinkedList(LinkedList &&rhs) noexcept {
init();
std::swap(this->size_, rhs.size_);
std::swap(this->list_head_, rhs.list_head_);
std::swap(this->list_end_, rhs.list_end_);
}
LinkedList &operator=(const LinkedList &rhs) {
if (this == &rhs) {
return *this;
}
LinkedList copy{rhs};
std::swap(*this, rhs);
return *this;
}
LinkedList &operator=(LinkedList &&rhs) noexcept {
if (this == &rhs) {
return *this;
}
LinkedList moved{std::move(rhs)};
std::swap(*this, moved);
return *this;
}
~LinkedList() {
erase(begin(), end());
delete list_head_;
delete list_end_;
}
Object &front() {
return *list_head_->next_->data_;
}
const Object &front() const {
return *list_head_->next_->data_;
}
Object &back() {
return *list_end_->prev_->data_;
}
const Object &back() const {
return *list_end_->prev_->data_;
}
Iterator begin() {
return Iterator{list_head_->next_};
}
ConstIterator begin() const {
return ConstIterator{list_head_->next_};
}
Iterator end() {
return Iterator{list_end_};
}
ConstIterator end() const {
return ConstIterator{list_end_};
}
void push_back(Object &obj) {
insert(end(), obj);
}
void push_back(Object &&obj) {
insert(end(), std::move(obj));
}
void push_front(Object &obj) {
insert(begin(), obj);
}
void push_front(Object &&obj) {
insert(begin(), std::move(obj));
}
Iterator insert(ConstIterator pos, const Object &obj) {
ListNode *new_node{new ListNode{obj, pos.data_node_->prev_, pos.data_node_}};
pos.data_node_->prev_->next_ = new_node;
pos.data_node_->prev_ = new_node;
++size_;
return Iterator{new_node};
}
Iterator insert(ConstIterator pos, Object &&obj) {
ListNode *new_node{new ListNode{std::move(obj), pos.data_node_->prev_, pos.data_node_}};
pos.data_node_->prev_->next_ = new_node;
pos.data_node_->prev_ = new_node;
++size_;
return Iterator{new_node};
}
Iterator erase(ConstIterator pos) {
ListNode *next_node{pos.data_node_->next_};
pos.data_node_->prev_->next_ = pos.data_node_->next_;
pos.data_node_->next_->prev_ = pos.data_node_->prev_;
delete pos.data_node_;
--size_;
return Iterator{next_node};
}
Iterator erase(ConstIterator from, ConstIterator to) {
while (from != to) {
from = erase(from);
}
return Iterator{to.data_node_};
}
void clear() {
erase(begin(), end());
}
std::ostream& pretty_print(std::ostream& os = std::cout) {
os << "[ ";
for (Iterator iter = begin(); iter != end(); ++iter) {
os << *iter << ", ";
}
os << "]";
return os;
}
[[nodiscard]] bool empty() const { return size_ == 0; }
[[nodiscard]] size_t size() const { return size_; }
private:
friend class ConstIterator;
friend class Iterator;
size_t size_{0};
ListNode *list_head_;
ListNode *list_end_;
void init() {
list_head_ = new ListNode{};
list_end_ = new ListNode{};
list_head_->next_ = list_end_;
list_end_->prev_ = list_head_;
}
};
#endif //LINKEDLIST_H
#include <LinkedList.h>
#include <gtest/gtest.h>
TEST(LinkedListTest, BasicPushBack) {
LinkedList<int> ilist{};
ASSERT_EQ(ilist.size(), 0);
std::vector<int> ivec { 1, 2,3 ,4,5,6,7};
for (int i = 0; i < ivec.size(); i++) {
ilist.push_back(ivec[i]);
ASSERT_EQ(ilist.back(), ivec[i]);
ASSERT_EQ(ilist.size(), i + 1);
}
}
TEST(LinkedListTest, BasicPushFront) {
LinkedList<int> ilist{};
ASSERT_EQ(ilist.size(), 0);
std::vector<int> ivec { 1, 2,3 ,4,5,6,7};
for (int i = 0; i < ivec.size(); i++) {
ilist.push_front(ivec[i]);
ASSERT_EQ(ilist.front(), ivec[i]);
ASSERT_EQ(ilist.size(), i + 1);
}
}
TEST(LinkedListTest, EraseFromBegin) {
LinkedList<int> ilist{};
ASSERT_EQ(ilist.size(), 0);
std::vector<int> ivec { 1, 2,3 ,4,5,6,7};
for (int i = 0; i < ivec.size(); i++) {
ilist.push_back(ivec[i]);
ASSERT_EQ(ilist.back(), ivec[i]);
ASSERT_EQ(ilist.size(), i + 1);
}
int i =0;
for (LinkedList<int>::ConstIterator iter = ilist.begin(); iter != ilist.end(); ++i) {
const int val = *iter;
std::cout << "before calling delete " << val << std::endl;
ilist.pretty_print() << std::endl;
iter = ilist.erase(iter);
ASSERT_EQ(ilist.size(), ivec.size() - i -1);
std::cout << "after calling delete " << val << std::endl;
ilist.pretty_print() << std::endl << std::endl;
}
ASSERT_EQ(ilist.size(), 0);
}
TEST(LinkedListTest, EraseFromEnd) {
LinkedList<int> ilist{};
ASSERT_EQ(ilist.size(), 0);
std::vector<int> ivec { 1, 2,3 ,4,5,6,7};
for (int i = 0; i < ivec.size(); i++) {
ilist.push_back(ivec[i]);
ASSERT_EQ(ilist.back(), ivec[i]);
ASSERT_EQ(ilist.size(), i + 1);
}
int i = 0;
for (LinkedList<int>::ConstIterator iter = --ilist.end(); iter != --ilist.begin(); ++i) {
const int val = *iter;
std::cout << "before calling delete " << val << std::endl;
ilist.pretty_print() << std::endl;
iter = ilist.erase(iter);
--iter;
ASSERT_EQ(ilist.size(), ivec.size() - i -1);
std::cout << "after calling delete " << val << std::endl;
ilist.pretty_print() << std::endl << std::endl;
}
ASSERT_EQ(ilist.size(), 0);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment