1、创建 链表结点
namespace JPC
{
//创建 链表结点
template<class T>
struct list_node
{
//成员变量
T _data; //结点的数据
list_node<T>* _next; //结点的尾指针
list_node<T>* _prev; //结点的头指针
// 构造函数(对结点进行初始化)
list_node(const T& x=T())
//本质上:Node(const T& x=T())
:_data(x)
,_next(nullptr)
,_prev(nullptr)
{}
};
2、创建 链表迭代器
//创建 链表迭代器
template<class T,class Ref,class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T,Ref,Ptr> iterator;
//成员变量
Node* _node; //结点指针(结点地址)
//构造函数
__list_iterator(Node* node) //list的迭代器是借助于 结点指针 实现的
:_node(node) //迭代器初始化过程是赋值给各个结点的地址(也就是将结点指针赋值过去)
{}
// !=
bool operator!=(const iterator& it)const
{
return _node != it._node; //这儿相当于: this->_node != it._node;
}
// ==
bool operator==(const iterator& it)const
{
return _node == it._node; //这儿相当于: this->_node != it._node;
}
// *it
//T& operator*()
// const T& operator*()
Ref operator*() //通过模板参数把实例化的过程 泛型化了
{
return _node->_data; //这儿相当于: this->_node->_data;
}
// -> 为:结点指针 直接访问 成员变量的方式
//T* operator->()
//const T* operator->()
Ptr operator->()
{
return &(operator*()); //这儿相当于返回的是:&(_node->_data) 【结点指针】
} // 返回的是地址,也是指针
// ++it;
iterator& operator++()
{
_node = _node->_next; //这儿相当于:this->_node = this->_node->_next;
return *this; //返回的是当前所处结点的地址
}
// --it;
iterator& operator--()
{
_node = _node->_prev; //这儿相当于:this->_node = this->_node->_prev;
return *this; //返回的是当前所处结点的地址
}
//it++
iterator& operator++(int)
{
iterator tmp(*this);
_node = _node->_next;
return tmp;
}
};
3、创建 链表
//创建 链表
template<class T>
class list
{
public:
typedef list_node<T> Node;
typedef __list_iterator<T,T&,T*> iterator;
typedef __list_iterator<T,const T&,const T*> const_iterator;
//构造函数
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
//完成头结点的创建,并且将其头指针、尾指针的指向设置好
}
//迭代器的底层模拟
iterator begin()
{
return iterator(_head->_next); // iterator(_head->_next) 是迭代器的构造函数,相当于 __list_iterator(_head->_next)
} //返回的是 首结点的地址
iterator end()
{
return iterator(_head); // 相当于 __list_iterator(_head)
} //返回的是 哨兵位头结点的地址
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
//尾插
void push_back(const T& x)
{
//Node* tail = _head->_prev; // 找list的尾结点
//Node* newnode = new Node(x); // 创建newnode
再理清结点顺序
_head tail newnode
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(),x);
}
//头插
void push_front(const T& x)
{
insert(begin(),x);
}
//插入
iterator insert(iterator pos, const T& x)
{
//确定 cur结点、prev结点,并且构建新结点
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
// cur prev newnode既可以做各个结点的名字,也可以作为迭代器类的成员变量
// 而 _next 、_prev 分别为:结点的尾指针、头指针
// prev newnode cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode); //这儿返回的是 迭代器构造函数的结果
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
//删除
iterator erase(iterator pos)
{
assert(pos != end()); //不能删除头结点
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// prev cur next
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
private:
Node* _head; //哨兵位的头结点
};
4、测试 模拟实现的list的功能
4.1 测试 iterator
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>::iterator it= lt.begin();
while (it != lt.end())
{
cout<< *it <<" ";
++it;
}
cout << endl;
//范围for
for (auto e:lt)
{
cout<< e <<" ";
}
cout << endl;
}
4.2 测试 ->
struct Pos
{
int _a1;
int _a2;
Pos(int a1=1,int a2=1)
:_a1(a1)
,_a2(a2)
{}
};
// ->
void test_list2()
{
list<Pos> lt;
lt.push_back(Pos(10,20));
lt.push_back(Pos(10, 21));
list<Pos>::iterator it = lt.begin();
while (it != lt.end())
{
//cout<< (*it)._a1 << ":" <<(*it)._a2 <<endl;
cout<< it->_a1 << ":" << it->_a2 <<endl;
//这儿的 it->_a1; 原本是:it->->_a1;
//【第一个 -> 为运算符重载:it.operator->() 】
//【第二个 -> 为 结点指针访问成员变量】
//【为了提升语法的可读性,编译器进行了特殊处理,省略了一个 ->】
++it;
}
cout << endl;
}
4.3 测试 const_iterator
//const_iterator
void Func(const list<int>& l)
{
list<int>::const_iterator it = l.begin();
while (it != l.end())
{
cout<< *it <<" ";
++it;
}
cout << endl;
}
void test_list3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
Func(lt);
}
4.4 测试 头插、尾插、头删、尾删
void test_list4()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.push_front(1);
lt.push_front(1);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_front();
lt.pop_front();
lt.pop_back();
lt.pop_back();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
}