数据结构 c++ list模拟实现

list介绍

list 是 C++ 标准库中的双向链表容器类模板，提供了动态链表的功能。它能够在运行时根据需要自动调整大小，并且支持快速的插入和删除操作。

list 的特点包括：

双向链表： list 使用双向链表来存储元素，每个节点包含一个指向前一个节点和后一个节点的指针。这种结构使得在任意位置进行插入和删除操作的时间复杂度都是常数时间。动态大小： list 能够自动调整大小以容纳存储的元素。当元素数量增加时，list 会自动分配新的节点来存储新的元素。无需连续内存： 由于 list 使用链表结构存储元素，不需要连续的内存块，因此可以灵活地插入和删除元素，而不涉及内存的重新分配和复制。快速插入和删除： 在 list 中插入和删除元素的操作具有较低的时间复杂度，无论是在头部、尾部还是中间位置。双向迭代器支持： list 提供了双向迭代器来遍历容器中的元素，可以沿着链表的前进方向和后退方向进行遍历。内存管理： list 负责管理存储元素的内存，可以自动分配和释放节点内存。使用 list 可以方便地存储和操作一组元素，特别适用于频繁进行插入和删除操作的场景。由于 list 使用链表结构存储元素，不需要移动其他元素，因此插入和删除操作的性能相对较高。但是，由于链表中的节点不是连续存储的，访问元素时需要遍历链表，因此随机访问的性能较差。与 vector 不同，list 的元素无法通过索引直接访问，需要使用迭代器进行遍历和访问。此外，由于链表的特性，list 不支持通过下标运算符（[]）来访问元素。需要注意的是，由于 list 使用链表结构存储元素，相对于 vector 和 deque 等基于数组的容器，它在内存使用和迭代器操作方面可能会产生额外的开销。因此，在选择容器类型时，需要根据具体的需求和性能要求进行权衡。

实现思路

首先需要定义一个 list_node 结构体，表示链表的节点。每个节点包含一个数据 _data，以及指向前一个节点 _prev 和后一个节点 _next 的指针。

还要定义 __list_iterator 迭代器结构体，用于遍历链表。它包含一个指向节点的指针 _node，以及一系列重载的操作符，如自增自减操作符、解引用操作符等。

然后就是定义 list 类，作为双向链表容器的实现。它包含一个指向头节点的指针 _head 和记录链表大小的 _size。

提供了迭代器的类型别名，包括 iterator 和 const_iterator。其中，iterator 可以修改节点的值，const_iterator 不可以修改节点的值。

具体函数：

typedef：定义迭代器类型别名 iterator 和 const_iterator。 begin()：返回链表的起始迭代器，用于指向第一个节点。 end()：返回链表的结束迭代器，用于指向链表末尾的标志节点。 empty_init()：初始化空链表，创建头节点，并将头节点的 _next 和 _prev 指针都指向自身。 list()：构造函数，创建一个空链表。 list(const list& lt)：拷贝构造函数，将传入的链表拷贝给当前链表。 swap(list& lt)：交换当前链表和另一个链表的内容。 operator=：赋值运算符重载，将传入链表的内容赋值给当前链表。 ~list()：析构函数，释放链表的内存空间。 clear()：清空链表，删除所有节点。 push_back(const T& x)：在链表末尾插入一个元素。 push_front(const T& x)：在链表头部插入一个元素。 pop_front()：删除链表头部的元素。 pop_back()：删除链表末尾的元素。 insert(iterator pos, const T& x)：在指定位置插入一个元素。 erase(iterator pos)：删除指定位置的元素。 size()：返回链表的大小。

代码

#pragma once

namespace hsl

{

template

struct list_node

{

T _data;

list_node* _next;

list_node* _prev;

list_node(const T& x = T())

:_data(x)

,_next(nullptr)

,_prev(nullptr)

{}

};

// T T& T*

// T cosnt T& const T*

template

struct __list_iterator

{

typedef list_node Node;

typedef __list_iterator self;

Node* _node;

__list_iterator(Node* node)

:_node(node)

{}

self& operator++()

{

_node = _node->_next;

return *this;

}

self& operator--()

{

_node = _node->_prev;

return *this;

}

self operator++(int)

{

self tmp(*this);

_node = _node->_next;

return tmp;

}

self operator--(int)

{

self tmp(*this);

_node = _node->_prev;

return tmp;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

bool operator!=(const self& s)

{

return _node != s._node;

}

bool operator==(const self& s)

{

return _node == s._node;

}

};

template

class list

{

typedef list_node Node;

public:

typedef __list_iterator iterator;

typedef __list_iterator const_iterator;

//typedef __list_const_iterator const_iterator;

const_iterator begin() const

{

return const_iterator(_head->_next);

}

const_iterator end() const

{

return const_iterator(_head);

}

iterator begin()

{

//return iterator(_head->_next);

return _head->_next;

}

iterator end()

{

//return iterator(_head->_next);

return _head;

}

void empty_init()

{

_head = new Node;

_head->_next = _head;

_head->_prev = _head;

_size = 0;

}

list()

{

empty_init();

}

// lt2(lt1)

list(const list& lt)

{

empty_init();

for (auto e : lt)

{

push_back(e);

}

}

void swap(list& lt)

{

std::swap(_head, lt._head);

std::swap(_size, lt._size);

}

// lt3 = lt1

list& operator=(list lt)

{

swap(lt);

return *this;

}

~list()

{

clear();

delete _head;

_head = nullptr;

}

void clear()

{

iterator it = begin();

while (it != end())

{

it = erase(it);

}

}

void push_back(const T& x)

{

insert(end(), x);

}

void push_front(const T& x)

{

insert(begin(), x);

}

void pop_front()

{

erase(begin());

}

void pop_back()

{

erase(--end());

}

iterator insert(iterator pos, const T& x)

{

Node* cur = pos._node;

Node* newnode = new Node(x);

Node* prev = cur->_prev;

// prev newnode cur

prev->_next = newnode;

newnode->_prev = prev;

newnode->_next = cur;

cur->_prev = newnode;

++_size;

return iterator(newnode);

}

iterator erase(iterator pos)

{

Node* cur = pos._node;

Node* prev = cur->_prev;

Node* next = cur->_next;

delete cur;

prev->_next = next;

next->_prev = prev;

--_size;

return iterator(next);

}

size_t size()

{

return _size;

}

private:

Node* _head;

size_t _size;

};

/

/

//测试函数

void test_list1()

{

list lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

lt.push_back(5);

// 封装屏蔽底层差异和实现细节

// 提供统一的访问修改遍历方式

list::iterator it = lt.begin();

while (it != lt.end())

{

*it += 20;

cout << *it << " ";

++it;

}

cout << endl;

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;

/*set s;

s.insert(1);

s.insert(3);

s.insert(2);

s.insert(4);

set::iterator sit = s.begin();

while (sit != s.end())

{

cout << *sit << " ";

++sit;

}

cout << endl;*/

}

void test_list2()

{

list lt;

lt.push_back(1);

lt.push_back(2);

lt.push_back(3);

lt.push_back(4);

lt.push_back(5);

list lt1(lt);

for (auto e : lt)

{

cout << e << " ";

}

cout << endl;

for (auto e : lt1)

{

cout << e << " ";

}

cout << endl;

list lt2;

lt2.push_back(10);

lt2.push_back(200);

lt2.push_back(30);

lt2.push_back(40);

lt2.push_back(50);

lt1 = lt2;

for (auto e : lt1)

{

cout << e << " ";

}

cout << endl;

for (auto e : lt2)

{

cout << e << " ";

}

cout << endl;

}

struct AA

{

AA(int a1 = 0, int a2 = 0)

:_a1(a1)

,_a2(a2)

{}

int _a1;

int _a2;

};

void test_list3()

{

list lt;

lt.push_back(AA(1, 1));

lt.push_back(AA(2, 2));

lt.push_back(AA(3, 3));

list::iterator it = lt.begin();

while (it != lt.end())

{

//cout << (*it)._a1<<" "<<(*it)._a2 << endl;

cout << it->_a1 << " " << it->_a2 << endl;

cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;

++it;

}

cout << endl;

int* p = new int;

*p = 1;

AA* ptr = new AA;

ptr->_a1 = 1;

}

//void print_list(const list& lt)

//{

// list::const_iterator it = lt.begin();

// while (it != lt.end())

// {

// //*it = 10;

// cout << *it << " ";

// ++it;

// }

// cout << endl;

///* for (auto e : lt)

// {

// cout << e << " ";

// }

// cout << endl;*/

//}

// 实例化

//template

template

//void print_list(const list& lt)

//{

// // list未实例化的类模板，编译器不能去他里面去找

// // 编译器就无法list::const_iterator是内嵌类型，还是静态成员变量

// // 前面加一个typename就是告诉编译器，这里是一个类型，等list实例化

// // 再去类里面去取

// typename list::const_iterator it = lt.begin();

// while (it != lt.end())

// {

// cout << *it << " ";

// ++it;

// }

// cout << endl;

//}

// 模板(泛型编程)本质，本来应该由我们干的活交给编译器

template

void print_container(const Container& con)

{

typename Container::const_iterator it = con.begin();

while (it != con.end())

{

cout << *it << " ";

++it;

}

cout << endl;

}

}

推荐文章