list的使用和模拟实现

💓博主个人主页:不是笨小孩👀
⏩专栏分类:数据结构与算法👀 C++👀 刷题专栏👀 C语言👀
🚚代码仓库:笨小孩的代码库👀
⏩社区：不是笨小孩👀
🌹欢迎大家三连关注，一起学习，一起进步！！💓

list的使用

list的底层是我们所说的双向带头循环链表，因此它的空间分配和vector不一样，它在内存中不是连续存放的。我们只讲常用的。

构造函数

我们现阶段可以不用管那个alloc，我们可以看到，可以用n个val来初始化list，也可以用一段迭代器区间来初始化，也可以用一个list来拷贝构造。

void test()
{
	list<int> ls(10, 1);
	list<int> ls1(ls);
	list<int> ls2(ls1.begin(),ls1.end());
}
1
2
3
4
5
6

迭代器

我们可以看到list也是支持迭代器的，所以我们可以用迭代器进行访问。

void test()
{
	list<int> ls(10, 1);
	list<int>::iterator it = ls.begin();

	while (it != ls.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12

插入删除数据

1. push_back

尾插一个数据。
2. pop_back

尾删一个数据。

3. push_front

头插一个数据。

4. pop_front

头删一个数据。

5. insert

在某个迭代器的位置的前面插入一个数据，这个有个返回值，返回的是插入后的那个数据的迭代器。在某个迭代器的位置前面插入n个val，在某个迭代器的位置的前面插入一段迭代器区间。insert不会导致迭代器失效。

6. erase

删除某个迭代器位置的值，删除一段迭代器区间，erase会导致迭代器失效，因此删除后需要返回删除后，那个位置的数据的迭代器。

void test()
{
	list<int> ls;
	//尾插
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	//头插
	ls.push_front(2);
	ls.push_front(3);
	//头删
	ls.pop_front();
	//尾删
	ls.pop_back();

	ls.insert(ls.begin(), 5);

	ls.erase(--ls.end());
	list<int>::iterator it = ls.begin();

	while (it != ls.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

reverse和sort

1. reverse

逆置链表。

2. sort

因为库里面的sort只能用来排序一段连续的空间的数据，所以链表就不能用，所以针对链表有一个专门的sort，但是比较慢，不推荐使用。

void test()
{
	list<int> ls;
	//尾插
	ls.push_back(1);
	ls.push_back(2);
	ls.push_back(3);
	
	ls.reverse();
	ls.sort();
	list<int>::iterator it = ls.begin();
	while (it != ls.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

list模拟实现

我们说list是双向带头循环链表，所以它的结构接很清晰了。

结构

template <class T>
	struct ListNode
	{
		T _date;
		ListNode<T>* _next;
		ListNode<T>* _prev;

		ListNode(const T& x = T())
			: _date(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13

因为我们在申请节点的时候会用一个初始值来初始化，所以我们可以给ListNode来一个构造函数。

list构造函数

为了修改方便我们会把结构typedef一下。
typedef ListNode Node;

我们开始需要申请一个节点，让他的前后指针都指向它自己。这里我们为了记录数量，我们添加了一个_size来记录容器中的数量。

list()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
    _size = 0;
}
1
2
3
4
5
6
7

迭代器

我们说迭代器是一种类似指针的东西，对于vector来说，它的底层是数组，可以++和–，但是对于我们链表来说，他是不支持++和–的，所以，我们的迭代器可以说是一个全新的类，我们要对这个类加入运算符重载，然后让他实现我们想要的操作。

但是我们迭代器分为迭代器和const迭代器，所以我们可以加两个模板参数，这样可以减少代码的冗余。

然后我们在list中定义的时候可以直接传T&和const T&就可以了。

这样我们就可以减少代码的冗余。

template <class T,class Ref,class Ptr>
struct __list_iterator
{
       typedef ListNode<T> Node;
       //重命名方便以后修改
       typedef __list_iterator<T,Ref,Ptr> self;
       Node* _node;
       //构造函数
       __list_iterator(Node* node = nullptr)
           :_node(node)
       {}
       bool operator!=(const self& s )
       {
           return _node != s._node;
       }
       bool operator==(const self& s)
       {
           return _node == s._node;
       }
       //解引用
       Ref operator*()
       {
           return _node->_date;
       }
       //为了以后对自定义类型使用
       Ptr operator->()
       {
           return &(_node->_date);
       }
       //前置++
       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;
       }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

有了这个以后我们就可以在list里面开始完成迭代器相关的接口了。

  iterator begin()
  {
      return _head->_next;
  }

  iterator end()
  {
      return _head;
  }

  const_iterator begin() const
  {
      return _head->_next;
  }

  const_iterator end() const
  {
      return _head;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

插入和删除数据

插入和删除我们又6个接口，但是我们实现一个insert和erase后上下来直接来复用这两个接口就可以了。

1. insert

我们需要申请一个新节点，从迭代器中拿到需要插入的节点，然后记录一下前一个节点，然后改变链接关系，最后返回插入后的那个节点就可以了。

iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._node;
    Node* newnode = new Node(x);

    Node* prev = cur->_prev;

    prev->_next = newnode;
    newnode->_prev = prev;

    newnode->_next = cur;
    cur->_prev = newnode;
    _size++;

    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. erase

我们拿到迭代器中的当前节点，然后拿到前一个节点和后一个节点，释放当前节点，改变链接关系，返回下一个节点就可以了。

iterator erase(iterator pos)
 {
     Node* cur = pos._node;

     Node* prev = cur->_prev;
     Node* next = cur->_next;

     delete cur;
     _size--;
     prev->_next = next;
     next->_prev = prev;

     return next;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

头插头删尾插尾删

头插就是在_head节点前插入，头删就是删除_head的下一个节点，尾删就是删除_head的前一个节点，尾插就是在_head的前面插入。

void pop_back()
{
    erase(--end());
}

void push_front(const T& x)
{
    insert(begin(), x);
}

void pop_front()
{
    erase(begin());
}
void push_back(const T& x)
{
    insert(end(), x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

clear

clser可以用迭代器来清，遍历的同时删除。

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
}
1
2
3
4
5
6
7
8

拷贝构造析构和赋值重载

拷贝构造先初始化一下，然后遍历需要拷贝的list，依次尾插。

list(const list& ls)
{
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
    for (auto e : ls)
    {
        push_back(e);
    }
}
1
2
3
4
5
6
7
8
9
10
11

析构可以先clear一下，然后把哨兵位的头结点释放了就可以了。

~list()
{
    clear();
    delete _head;
}
1
2
3
4
5

赋值拷贝

我们可以直接让原数据拷贝给tmp，然后和this交换，就可以了，等这个函数结束，编译器会帮我们调用析构。

 void swap(list& s)
 {
     std::swap(_head, s._head);
     std::swap(_size, s._size);
 }
 list& operator=(list ls)
 {
     swap(ls);

     return *this;
 }
1
2
3
4
5
6
7
8
9
10
11

今天的分享就到这里，感谢大家的关注和支持。