双链表的的基本结构
从 STL 源码抽出的基本双链表结构
代码
#ifndef _GRAVER_GLIB_LIST_H_
#define _GRAVER_GLIB_LIST_H_
#include <cstddef>
#include "graver/util/log_util.h"
namespace graver {
// 内部结构与方法放在 detail
namespace detail {
/**
* @brief 链表结点
*
* @tparam T 数据类型
*/
template <typename T>
class ListNode {
public:
ListNode() {
prev = nullptr;
next = nullptr;
}
ListNode(T value) {
prev = nullptr;
next = nullptr;
data = value;
}
public:
/**
* @brief 前一个结点指针
*/
ListNode<T>* prev;
/**
* @brief 后一个结点指针
*/
ListNode<T>* next;
/**
* @brief 数据
*/
T data;
};
/**
* @brief 迭代器
*
* @tparam T 数据类型
*/
template <typename T>
class ListIterator {
public:
ListIterator(ListNode<T>* ptr = nullptr) : _ptr(ptr){};
T& operator*() const {
return *static_cast<T*>(static_cast<void*>(&_ptr->data));
};
T* operator->() const {
return static_cast<T*>(static_cast<void*>(&_ptr->data));
}
ListIterator& operator++() {
_ptr = _ptr->next;
return *this;
}
ListIterator operator++(int) {
auto tmp = *this;
_ptr = _ptr->next;
return tmp;
}
bool operator==(const ListIterator& it) const {
return _ptr == it._ptr;
}
bool operator!=(const ListIterator& it) const {
return _ptr != it._ptr;
}
private:
ListNode<T>* _ptr;
};
} // namespace detail
/**
* @brief 链表
*
* @tparam T 数据类型
*/
template <typename T>
class List {
private:
typedef detail::ListNode<T> _Node;
public:
typedef detail::ListIterator<T> iterator;
public:
List() {
dzlog_info("List constructor");
_head = new _Node();
_tail = new _Node();
_head->prev = nullptr;
_head->next = _tail;
_tail->prev = _head;
_tail->next = nullptr;
_length = 0;
}
~List() {
dzlog_info("List destructor");
clear();
delete _head;
delete _tail;
}
public:
// 返回指向起始的迭代器
iterator begin() noexcept {
return iterator(_head->next);
}
// 返回指向末尾的迭代器
iterator end() {
return iterator(_tail);
}
public:
// 是否为空
bool empty() {
return 0 == size();
}
// 元素数量
size_t size() const {
return _length;
}
public:
// 清空链表
void clear() {
while (!empty()) {
pop_back();
}
}
// 尾部追加元素
void push_back(const T& value) {
detail::ListNode<T>* node = new _Node();
node->data = value;
_tail->prev->next = node;
node->prev = _tail->prev;
node->next = _tail;
_tail->prev = node;
_length++;
}
// 尾部移除
void pop_back() {
if (empty()) {
return;
}
auto removeNode = _tail->prev;
_tail->prev = removeNode->prev;
delete removeNode;
_length--;
}
private:
/**
* @brief 头结点
*/
_Node* _head;
/**
* @brief 尾结点
*/
_Node* _tail;
/**
* @brief 链表长度
*/
size_t _length;
};
} // namespace graver
#endif
测试
测试数据定义
#ifndef _GRAVER_TEST_TEST_TYPE_H_
#define _GRAVER_TEST_TEST_TYPE_H_
#include <string>
#include "fmt/core.h"
#include "graver/util/log_util.h"
struct Person {
std::string name;
int age;
void print() const {
dzlog_info(fmt::format("name:{}\tage:{}", name, age).c_str());
}
};
#endif
STL list 测试
#include <list>
#include <memory>
#include "doctest/doctest.h"
#include "fmt/core.h"
#include "graver/util/log_util.h"
#include "test_type.hpp"
TEST_SUITE("test_common") {
TEST_CASE("test_common_one") {
auto list = std::make_unique<std::list<Person>>();
dzlog_info("it++");
list->push_back({"Thresh", 18});
list->push_back({"Syndra", 16});
list->push_back({"Maokai", 35});
list->push_back({"Shaco", 25});
for (auto it = list->begin(); it != list->end(); it++) {
(*it).print();
}
dzlog_info("++it");
for (auto it = list->begin(); it != list->end(); ++it) {
it->print();
}
dzlog_info("foreach");
for (const auto& p : *list) {
p.print();
}
}
}
自定义双链表测试
#include <memory>
#include "doctest/doctest.h"
#include "fmt/core.h"
#include "graver/glib/glib.h"
#include "graver/util/log_util.h"
#include "test_type.hpp"
TEST_SUITE("test_list") {
TEST_CASE("test_list_one") {
auto list = std::make_unique<graver::List<Person>>();
dzlog_info("it++");
list->push_back({"Thresh", 18});
list->push_back({"Syndra", 16});
list->push_back({"Maokai", 35});
list->push_back({"Shaco", 25});
for (auto it = list->begin(); it != list->end(); it++) {
(*it).print();
}
dzlog_info("++it");
for (auto it = list->begin(); it != list->end(); ++it) {
it->print();
}
dzlog_info("foreach");
for (const auto& p : *list) {
p.print();
}
}
}
输出结果
2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Thresh age:18
2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Syndra age:16
2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Maokai age:35
2023-06-28 07:21:24.978 6716 INFO [test_type.hpp:14] - name:Shaco age:25
2023-06-28 07:21:24.979 6716 INFO [test_list.cpp:20] - ++it
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Thresh age:18
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Syndra age:16
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Maokai age:35
2023-06-28 07:21:24.979 6716 INFO [test_type.hpp:14] - name:Shaco age:25
2023-06-28 07:21:24.980 6716 INFO [test_list.cpp:24] - foreach
2023-06-28 07:21:24.980 6716 INFO [test_type.hpp:14] - name:Thresh age:18
2023-06-28 07:21:24.980 6716 INFO [test_type.hpp:14] - name:Syndra age:16
2023-06-28 07:21:24.980 6716 INFO [test_type.hpp:14] - name:Maokai age:35
2023-06-28 07:21:24.981 6716 INFO [test_type.hpp:14] - name:Shaco age:25
leetcode 链表题目
21. 合并两个有序链表
解题过程记录: 【leetcode】【21】【合并两个有序链表】