目錄
1.list的概述
2.list的節點
3.list的迭代器
4.list的資料結構
a.插入節點
b.洗掉節點
1.list的概述
list的底層是
雙向鏈表結構
，雙向鏈表中每個元素存盤在互不相關的獨立節點中，在節點中通過指
針指向其前一個元素和后一個元素，它的優點是每次插入或洗掉一個元素，就配置或釋放一個元素的空間，所以對于空間的管理比較精準，一點也不浪費，而且對于任何的元素插入或洗掉，它的
時間復雜度為O（1）
，非常高效，
2.list的節點
list本身與list的節點是不同的結構，需要分開設計，
template<class T>
struct _list_node//定義節點
{
_list_node(const T& val=T())
:_val(val)
,_prev(nullptr)
,_next(nullptr)
{
}
T _val;//存盤資料
_list_node<T>* _next;//存盤下一個節點的地址
_list_node<T>* _prev;//存盤上一個節點的地址
};
顯然這是一個雙向鏈表
3.list的迭代器
list不能夠像vector一樣以普通指標作為迭代器，因為它的節點不能保證在空間上的地址是連續存在的，迭代器的特點是需要能夠像指標一樣遞增，遞減，取值等操作，所以我們設計list迭代器需要用一個類來進行包裝設計，
以下是list迭代器的主要設計：
//定義三個模板引數是為了讓下面的list鏈表對const和非const實體化出兩種不同型別的迭代器
template<class T,class Ref,class Ptr>
struct _list_iterator
{
typedef _list_node<T>node;//將_list_node<T>型別起一個node的名字
typedef _list_iterator<T,Ref,Ptr> self;
node* _pnode;//指向list節點的指標
_list_iterator(node* pnode)//迭代器的建構式
:_pnode(pnode)
{
}
//拷貝構造、operator、析構我們不寫，編譯器生成可以用
Ref operator* ()//迭代器取值，取得是節點內的值
{
return _pnode->_val;
}
Ptr operator->()
{
return &_pnode->_val;
}
bool operator !=(const self& s)const//判斷節點的地址不相等
{
return _pnode != s._pnode;
}
bool operator ==(const self& s)const//判斷節點的地址相等
{
return _pnode == s._pnode;
}
self operator++()//對迭代器進行加1，前進一個節點
{
_pnode = _pnode->_next;
return _pnode;
}
self operator++(int)//后置加加
{
self tmp(this->_pnode);
_pnode = _pnode->_next;
return tmp;
}
self operator--()//對迭代器進行減1，后退一個節點
{
_pnode = _pnode->_prev;
return _pnode;
}
self operator--(int)//后置減減
{
self tmp(this->_pnode);
_pnode = _pnode->_prev;
return tmp;
}
};4.list的資料結構
接下來我要設計的list結構不僅是雙向鏈表，而且是帶頭雙向回圈鏈表
什么是帶頭雙向回圈鏈表？
首先鏈表分為：單/雙， 回圈不回圈，帶頭/不帶頭，上面可以兩兩組合，所以總共有8種鏈表，所以我們來看每種特殊鏈表是怎樣的，
雙向鏈表：每個節點可以存盤兩個地址，使鏈表看起來具有雙向結構
回圈鏈表：最后一個節點存盤第一個節點的地址，使鏈表成一個回圈結構
帶頭鏈表：
帶頭節點就是多一個哨兵位節點，這個節點不是用來存盤資料，是用來存盤第一個節點的地址，
帶頭雙向回圈鏈表：
結合上面的節點和迭代器的設計，list的實作如下：
template<class T>
class list
{
public:
typedef _list_iterator<T,T&,T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;//命名
typedef _list_node<T> node;
list()//鏈表的建構式，創建一個哨兵位節點出來
{
//_head = new node(T());
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list(const list<T>& lt)//拷貝建構式
{
_head = new node;//創建一個新的哨兵為節點
_head->_next = _head;
_head->_prev = _head;
for (auto& e : lt)//取出lt鏈表中的值,然后插入到新鏈表中
{
push_back(e);
}
}
//鏈表t是由拷貝建構式構造出來的臨時變數，
//與原本鏈表的哨兵位節點進行交換即交換整個鏈表
//離開函式后，t的生命周期就結束，就會去呼叫解構式銷毀掉
list<T> operator=(list<T> t)
{
swap(_head, t._head);
return *this;
}
iterator begin() //回傳的鏈表中第一個節點的地址
{
return iterator(_head->_next);
}
const_iterator begin()const //const型別的迭代器
{
return const_iterator(_head->_next);
}
iterator end()//回傳哨兵位節點的地址
{
return iterator(_head);
}
const_iterator end()const//const型別的迭代器
{
return const_iterator(_head);
}
void clear()//清掉所有節點，除了哨兵位節點
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
}
~list()
{
clear();//先清掉所有節點
delete _head;//再清掉哨兵位節點
_head = nullptr;
}
size_t size()//回傳鏈表中有多少個值
{
iterator it = begin();
size_t sz = 0;
while (it != end())
{
sz++;
it++;
}
}
private:
node* _head;
};
注意：const型別list會自動呼叫const型別的迭代器，非const型別的list會自動呼叫非cosnt的迭代器，
鏈表中的end（）和begin（）的位置：如下
a.插入節點
void insert(iterator pos, const T& x)//在pos位置插入一個節點
{
node* newnode = new node(x);//創建一個新節點，會呼叫node的建構式
//調整雙向指標，使newnode到鏈表里去
node* prev = pos._pnode->_prev;
newnode->_prev = prev;
prev->_next = newnode;
newnode->_next = pos._pnode;
pos._pnode->_prev = newnode;
}在pos位置之前插入一個4的節點：
保存pos位置的上一個節點地址，將新節點與pos位置的節點和上一個節點進行互相連接即可，
void push_back(const T& x)//在鏈表的最后一個位置插入節點
{
insert(end(), x);
}
void push_Front(const T& x)//在鏈表的第一個位置插入節點
{
insert(_head->_next,x);
}b.洗掉節點
iterator erase(iterator pos)//在pop位置洗掉掉一個節點
{
assert(pos._pnode );
assert(pos != end());
node* prev = pos._pnode->_prev;//保存上一個節點的地址
node* next = pos._pnode->_next;//保存上一個節點的地址
delete pos._pnode;//洗掉節點
//互相連接
prev->_next = next;
next->_prev = prev;
return iterator(next);//在回傳下一個節點的地址
}洗掉pos位置的節點，先保存pos位置的上一個節點和下一個節點地址，然后洗掉掉pos位置的節點，再把上一個節點和下一個節點連接起來， 為了防止迭代器失效，在回傳下一個節點的地址，
void pop_front()//洗掉第一個節點
{
erase(_head->_next);
}
void pop_back()//洗掉最后一個節點的值
{
erase(_head->_prev);
}
void clear()//清掉所有節點，除了哨兵位節點
{
iterator it = begin();
while (it != end())
{
it=erase(it);
}
}
~list()
{
clear();//先清掉所有節點
delete _head;//再清掉哨兵位節點
_head = nullptr;
}
點個贊唄~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/294211.html
標籤：其他
上一篇：C++--模板&STL