c++:数据结构链表list的模拟实现

---

链表的知识回顾

链表是有一个个节点链接起来的.每一个节点里面存有数据val,下一个节点的地址next,双向循环链表还会有上一个节点的地址.
双向带头循环链表比双向循环链表多了一个头节点.又称哨兵位.在很多时候,多一个头节点能帮我们解决很多事.

下面模拟实现的就是双向带头循环链表,跟c++容器库list里面一样

---

前期工作

写一个自己的命名空间,防止跟库里面函数冲突.我们后面所写的函数都在中国命名空间里面.

namespace shh
{
}
1
2
3

构造节点

因为节点里面要存储很多值,所以我们写一个类把它封装起来.
同时,因为节点里面存储的数据val类型不清楚,写一个模板,让编译器自己根据类型去生成.

	//把节点封装成一个类
	template<class T>
	struct ListNode
	{
		ListNode<T>* prev = nullptr;
		ListNode<T>* next = nullptr;
		T val = T();

		ListNode(const T& tmp = T())
			:prev(nullptr)
			, next(nullptr)
			, val(tmp)
		{
		}
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里写一个构造,为我们后面可以直接用值tmp去生成节点,不用自己写.

迭代器

vector和string里面的迭代器都是原生指针,因为他们存储的物理空间连续.
例如: iterator(int) ,iterator++ 会跳到下一个数字.iterator可以访问数据.
但是链表没有办法做到这一点.所以,我们将链表节点的指针封装成一个类,然后用上运算符重载,自己控制运算符,就能实现vector中T*的功能.

	template<class T,class Ref,class Ptr>
	struct list_iterator
	{
		typedef ListNode<T> Node;
		typedef list_iterator<T,Ref,Ptr> iterator;

		//节点指针
		Node* _node;
	};
1
2
3
4
5
6
7
8
9

这个类里面封装的是节点的指针,所以它唯一的成员变量就是Node.*

注意

这里的模板有三个参数,为什么呢?
首先T是节点数据的类型,这个没问题.
但是其他两个呢?
Ref是引用,Ptr是指针.这样子写是为了能生成多种引用T&,和T.*
当我们需要修改这个数据是我们直接传T&.如果我们不允许别人修改数据时,传const T&,让别人只能读.不能修改.
其实还有另一种解决方法,copy这个类,把这个类改成const版本的.但是这样会造成代码冗余.

构造迭代器

		//
		list_iterator(Node* node)
			:_node(node)
		{
		}
1
2
3
4
5

写了这个,我们就可以传一个节点的指针来构造迭代器

解引用*迭代器

		Ref operator*()
		{
			return _node->val;
		}
1
2
3
4

Ref是T& / const T&
我们这里要模拟的是vector中T*的功能,解引用取得数据,所以返回节点中的数据

迭代器->

		Ptr operator->()
		{
			return &_node->val;
		}
1
2
3
4

Ptr是T / const T
我们这里要模拟的是指针中->的功能,所以要传数据T的地址.

在调用上,我们假设有一个类A,里面有两个值a1和a2,我们用这个类来充当节点中的数据val
it->是调用it.operator->(),返回的是一个T.
it.operator->() ->a1 才能取到a1
为了美观,编译器会帮我们减少一个箭头 变成 it->_a1

	struct A
	{
		int _a1, _a2;

		A(int a1 = 0, int a2 = 0)
			:_a1(a1),
			_a2(a2)
		{}
	};
	void TestList2()
	{
		list<A> lt;
		A a = { 3,3 };
		lt.push_back(a);
		lt.push_back(A{2,2});
		lt.push_back({1,1});

		list<A>::iterator it = lt.begin();
		while (it != lt.end())
		{
			/*cout << *it << " ";*/
			cout << it->_a1 << " "<< it->_a2;
			cout << endl;
			//it.operator->() ->a1
			//val* --> T*
			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
28
29
30

迭代器++

		//前置++  ++i;
		iterator& operator++()
		{
			_node = _node->next;
			return *this;
		}
		//后置++  i++;
		iterator operator++(int)
		{
			iterator tmp(_node);
			_node = _node->next;
			return tmp;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

迭代器- -

		//--i
		iterator& operator--()
		{
			_node = _node->prev;
			return *this;
		}
		//i--
		iterator operator--(int)
		{
			iterator tmp(_node);
			_node = _node->prev;
			return tmp;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13

判断两个迭代器是否相等

		bool operator==(const iterator& it)
		{
			return _node == it._node;
		}

		bool operator!=(const iterator& it)
		{
			return _node != it._node;
		}
1
2
3
4
5
6
7
8
9

链表

template<class T>
	class list
	{
	public:
		//调用可读可写的迭代器
		typedef list_iterator<T,T&,T*> iterator;
		//调用只能读,不能修改的迭代器
		typedef list_iterator<T, const T&,const T*> const_iterator;

		typedef ListNode<T> Node;
		
	private:
		Node* _head;
		size_t _size;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

链表里面有两个成员变量,一个作为头节点,一个计算节点的个数

empty_init

这个函数的功能和构造函数一样,写出来是为了后面进行复用.

		void empty_init()
		{
			_head = new Node;
			_head->next = _head;
			_head->prev = _head;
			_size = 0;
		}
1
2
3
4
5
6
7

构造

复用empty_init

		list()
		{
			empty_init();
		}
1
2
3
4

拷贝构造

list T2(T1)
初始化T2,然后把T1的值都塞到后面

		list(const list<T>& T1)
		{
			empty_init();
			for (auto& e : T1)
			{
				push_back(e);
			}
		}
1
2
3
4
5
6
7
8

swap

T2.swap(T1)
交换两个链表

		void swap(const list<T>& T1)
		{
			std::swap(_head, T1._haed);
			std::swap(_size, T1._size);
		}
1
2
3
4
5

operator=

这里运用了一个很巧妙的写法,把传过来的值拷贝构造list T1,然后将T1和*this交换
直接白嫖编译器的成果(拷贝构造),纯纯资本家

		const list<T>& operator=(list<T> T1)
		{
			swap(T1);
			return *this;
		}
1
2
3
4
5

begin和end

begin返回头节点的下一个,end返回头节点.因为容器底层实现,遍历等都是左闭右开[ )

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

		const_iterator end() const
		{
			return _head;
		}

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

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

insert

注意:在链表中,我们的节点都需要自己new出来,因为链表不是一个连续的空间,没有办法直接开好.要一个个自己搞
pos里面存储的节点指针才是我们需要的

		// prev  tmp  next
		void insert(iterator pos, const T& val)
		{
			//new一个用数据val开辟出来的节点
			Node* tmp = new Node(val);
			Node* prev = pos._node->prev;
			Node* next = pos._node;

			prev->next = tmp;
			tmp->prev = prev;
			tmp->next = next;
			next->prev = tmp;
			_size++;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

push_back

复用insert尾插

		void push_back(const T& val)
		{
			insert(end(), val);
		}
1
2
3
4

push_front

复用insert头插

		void push_front(const T& val)
		{
			insert(begin(), val);
		}
1
2
3
4

erase

注意:delete要删除自定义类型要调用析构函数,我们这里要删除的是节点(指针),而不是迭代器
不能delete pos,迭代器只有访问节点的功能,不能管理节点

		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = pos._node->prev;
			Node* next = pos._node->next;
			prev->next = next;
			next->prev = prev;
			//
			delete cur;
			_size--;

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

pop_back

复用erase,注意要删除的不是头节点,而是头节点的前一个,也就是存储有效数据的最后一个
所以–end(),改好使用我们之前写的迭代器–.

		void pop_back()
		{
			erase(--end());
		}
1
2
3
4

pop_front

		void pop_front()
		{
			erase(begin());
		}
1
2
3
4

size

		size_t size()
		{
			return _size;
		}
1
2
3
4

empty

		bool empty()
		{
			return _size == 0;
		}
1
2
3
4

clear

删除掉除头节点之外的其他节点

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

析构

在clear的前提下删除头节点

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