Last active
July 1, 2024 09:58
-
-
Save lry127/cf5c311a2fc2a4acbe7127e6210a4627 to your computer and use it in GitHub Desktop.
LinkedList implementation in C++ for educational purpose
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
// | |
// 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 |
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 <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