一、官方源码的探究

在实现list的底层前，我们先看下官方的核心成员变量，link_type node，其中link_type是list_node*，也就是说是节点的指针

在这里插入图片描述

下面我们看下其的初始化，在空初始化中，链表为空并不是把节点的指针给成空，而是给了个节点，让其的前驱指针和后继指针均指向自己，在C语言阶段的数据结构中我们便知道这个节点是哨兵位头节点

注意： 这里创捷新的节点不是new的，而是使用get_node出来的，这里是由于内存池的原因，后续再介绍

在这里插入图片描述

二、list底层的构建及其尾插

2.1 list底层探索

实现链表首先需要实现节点，即其的前驱指针，后继指针，和其保存的数据

代码语言：javascript

AI代码解释

namespace hxx
{
   template<class T>
   class list_node
   {
         T _data;
         list_node* _prev;
         list_node* _next;
list_node(const T& data)
:_data(data)
,_next(nuppptr)
,_prev(nullptr)
{}
    }:
    }

链表是一个个节点组成的结构，在实现完节点后，我们便可以轻松实现list了的初始化结构，我们仿照官方实现的结构来实现,由于我们并没有实现内存池，因此这里创建新节点依旧是new

注意： 这里我们多定义了个size变量是为了方便计算节点的数量，每次增加节点或者删除节点，直接让size++/- - 更加方便，不需要在遍历链表

为什么官方在初始化list时，使用的方法是头结点的next和prev指针均指向自己，是为了防止后面实现的end和begin接口在空节点的特殊情况下的处理

代码语言：javascript

AI代码解释

template <class T>
class list
{
   typedef list_node<T> Node;
public:
    list()
    {
      _head=new Node;
      _head->next=_head;
      _head->prev=_head;
      _size=0;
    }

private:
    Node*_head;
    size_t size;
} 

2.2 push_back

在实现尾插前我们需要找到链表的尾部， 哨兵位头结点的前驱指针便是尾节点tail，再让tail的后继指针指向要尾插的新节点newnode，newnode的前驱指针指向tail，最后别忘让newtail成为新的尾节点，因此需要让newtail的后继指针指向哨兵位头结点，哨兵位头结点指向newnode即可

代码语言：javascript

AI代码解释

void push_back()
{
  //newd对象后需要调用构造函数，因此还需要再节点类型里定义构造函数
    Node*newnode=new Node(x);
    Node*tail=_head->prev;
    tail->next=newnode;
    newnode->prev=tail;
    newnode->next=_head;
    _head->prev=newnode;
    ++size;
   }

三、实现普通迭代器的遍历

list相对于vector和string来说，难实现的是迭代器，因为vector和string的结构有着先天的优势——地址是连续的，使用原生指针可以直接访问。因此list的迭代器需要类型对节点的指针进行封装

在上面我们完成了list的基本底层结构和尾插，为了判断我们实现的代码是否有问题，那么我们打印一遍就知道了，这里必然要用到迭代器去遍历链表，因此实现list版本的迭代器是不可或缺的重点

我们只需要将如下的代码跑通便代表迭代器实现了

代码语言：javascript

AI代码解释

void test()
{
  list<int> lt;，
  lt.push_back(1);
  lt.push_back(2);
  lt.push_back(3);
  lt.push_back(4);
  
  list<int>::iterator it=lt.begin();
  while(it!=lt.end())
  {
     cout<<*it<<" ";
     ++it;
   }
   cout<<endl;
}

3.1运算符*/++/–的重载

那么这里的迭代器我们需要如何实现其底层结构？我们要去遍历节点，我们使用节点的指针是搞不定的，因为list的地址是不连续的，++指针是不能找到下一个节点。但是节点力存放了下一个节点的地址，因此我们考虑用类进行封装通过重载运算符实现迭代器，由于直接解引用得到的不是data数据，因此我们可以重载operator*来实现，同理也可以重载++来找到下一个节点

代码语言：javascript

AI代码解释

//由于链表的类型不确定，因此需要使用模板
template <class T>
//这里使用struct是因为其默认是公有，可以直接给list提供公共接口
struct list_iterator
{
   typedef list_node<T>  Node;
   //重载++就是迭代器++，也就是迭代器的类型，这里可以typedef下
   typedef list_iterator<T> Self;
    Node* _node;
   
   //构造函数
   list_iterator(Node* node)
   :_node(node)
   {
   }
   T&  operator*()
   {  
    
    return _node->_data;
   }
   
  Self& operator++()
   {
    _node=node->_next;
    return *this;
   }
    
    //两个迭代器的比较
   bool operator!=(const Self& s)
    {
        return _node!=s._node;
    }

};

实现完前置++/- -，我们再实现下后置++/- -，后置是返回++/- -之前的值，但是其在实现的时候还是需要++/- -

代码语言：javascript

AI代码解释

//后置++
Self& operator++(int)
{
    Self tmp(*this);
    _node=_node->next;   
    return *this;
}

//后置- -
Self& operator--(int)
{   
   //在这里我们用到了拷贝，但是我们自己却没有实现拷贝构造函数，而是让编译器自己生成的，这里仅是值拷贝，因为我们希望迭代器    
   //iterator也指向该节点，这里就是浅拷贝，而不是深拷贝，注意并不是有指针就是深拷贝，而是要看指针所指向的资源是否属于自己，属于自己需要深拷贝，而迭代器中的指针指向的资源不属于它的，因此仅为浅拷贝

    Self tmp(*this);
    _node=_node->prev;   
    return *this;
}

总结：资源不属于当前对象，只是 “借用” 或 “引用” 资源，资源的生命周期由其他对象管理，那么拷贝时只需要浅拷贝，因为即使多个指针指向同一份资源，也不会有冲突（资源的释放由真正的所有者负责）

，我们解引用不再使用对象+点来访问，而是通过->l来进行，因c还需要运算符重载下->

3.2 自定义类型下的运算符重载

如若list的类型不再是内置类型而是自定义类型如struct时,下面我们来看个struct类型的例子，看是否可以遍历list

代码语言：javascript

AI代码解释

struct AA
{
   int a1=1;
   int a2=1;


};


void test1()
{
   list<AA> lt;
   lt.push_back(AA());
   lt.push_back(AA());
   lt.push_back(AA());
   lt.push_back(AA());
   
   list<AA>::iteerator it=lt.begin();
   while(it!=lt.end())
   {   
   cout<<*it<<" ";
   ++it;

   }
   cout<<endl;
}

结果演示：

在这里插入图片描述

很显然我们运行错误，因为lt解引用后是自定义类型，<<不支持自定义类型的使用，因此在这里有三种方法

1.在struct里面重载流插入 2.通过(*lt)._a1,(*lt)_a2来访问 3.通过重载operator->