List的简单模拟实现

什么是list？

在C++中，list 是一种双向链表（doubly linked list）数据结构，它属于标准模板库（STL）的一部分。

添加元素

push_back(const T& value): 在链表末尾添加一个元素。
push_front(const T& value): 在链表开头添加一个元素。
insert(iterator pos, const T& value): 在指定位置插入一个元素。

删除元素

pop_back(): 删除链表末尾的元素。
pop_front(): 删除链表开头的元素。
erase(iterator pos): 删除指定位置的元素。
erase(iterator first, iterator last): 删除指定范围内的元素。
remove(const T& value): 删除所有等于指定值的元素。

访问元素

begin(): 返回指向链表第一个元素的迭代器。
end(): 返回指向链表末尾之后位置的迭代器（哨兵迭代器，不指向有效元素）。
rbegin(): 返回指向链表最后一个元素的反向迭代器。
rend(): 返回指向链表开头之前位置的反向迭代器。

获取链表大小

size(): 返回链表中元素的数量。

判断链表是否为空

empty(): 如果链表为空，则返回true；否则返回false。

清空链表

clear(): 删除链表中的所有元素，使链表变为空。

简单示例：

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
#include <iostream>
#include <list>
 
int main() {
    std::list<int> myList;
 
    // 添加元素
    myList.push_back(10);
    myList.push_front(5);
    myList.insert(myList.begin() + 1, 15); // 在第二个位置插入15
 
    // 输出链表内容
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
 
    // 删除元素
    myList.pop_back(); // 删除末尾元素
    myList.erase(myList.begin()); // 删除开头元素
 
    // 再次输出链表内容
    for (int num : myList) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
 
    // 判断链表是否为空并清空链表
    if (!myList.empty()) {
        myList.clear();
    }
 
    std::cout << "链表是否为空: " << (myList.empty() ? "是" : "否") << std::endl;
 
    return 0;
}

模拟实现

listnode类和list类

注意，listnode和list都是一个模板类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<typename T>
class listnode {
	typedef listnode<T> node;
public:
	listnode(const T & value):l_value(value),prev(nullptr),next(nullptr){};
	~listnode(){};
    //这里为了方便直接把node的成员公开给list和iterator使用，也可以放弃class写法改用结构体
	T l_value;
	node* prev; //每个节点都有自己的value，指向前后节点的指针
	node* next;
};

template<typename T>
class list {
    typedef listnode<T> node;
    public:
	list():l_head(nullptr),l_tail(nullptr),l_size(0){};
	~list() { clear(); };
    private:
	node* l_head;
	node* l_tail;  //l_head和l_tail分别指向第一个和最后一个node
	int l_size;
};

push和pop

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
void push_front(const T& value) {
		auto newnode = new node(value); //要插入就得先new一个node
		if (l_size == 0) {
			l_head = l_tail = newnode;
			l_size++;
			return;
		}           //指针的变换比较绕，建议初学在纸上画一画
		l_head->prev = newnode;  
		newnode->next = l_head;
		l_head = newnode;
		l_size++;
	};
	void pop_front() {
		if (l_size == 0)
			return;
		if (l_size == 1) {
			delete l_head;
			l_head = l_tail = nullptr;
		}
		auto head = l_head->next; //要提前保存l_head的下个节点，不然删掉l_head所指的node后就找不到头
		head->prev = nullptr;
		delete l_head;
		l_head = head;
		l_size--;
	};
	void push_back(const T& value) {
		auto newnode = new node(value);
		if (l_size == 0) {
			l_head = l_tail = newnode;
			l_size++;
			return;
		}
		l_tail->next = newnode;
		newnode->prev = l_tail;
		l_tail = newnode;
		l_size++;
	};
	void pop_back() {
		if (l_size == 0)
			return;
		if (l_size == 1) {
			delete l_tail;
			l_tail = l_head = nullptr;
			l_size--;
			return;
		}
		auto tail = l_tail->prev;
		tail->next = nullptr;
		delete l_tail;
		l_tail = tail;
		l_size--;

	};
```   

## 迭代器

因为list是双向链表，想要实现list的+或者-等操作就必须借助迭代器的实现。

>正向迭代器

```cpp
template<typename T>
class listiterator {
	friend class list<T>;  //因为list会访问该类私有成员，所以做了友元的处理。
	typedef listnode<T> node;
	typedef listiterator iterator;
public:
	listiterator() :l_pointer(nullptr) {};
	listiterator(node* pointer) :l_pointer(pointer) {};
	~listiterator() {};
	bool operator ==(const iterator& other) {
		return l_pointer == other.l_pointer;
	}
	bool operator !=(const iterator& other) {
		return l_pointer != other.l_pointer;

	}
	iterator& operator =(const iterator& other) {
		if (this == &other)
			return;
		l_pointer = other.l_pointer;
		return *this;
	}
	iterator& operator ++() {  //前置++
		l_pointer = l_pointer->next;  //先加了再用
		return *this;
	}
	iterator& operator ++(int) {  //后置++
		iterator it = *this; 
		++(*this);   
		return it;  //返回的是没加的那个，先用了再加
	}
	iterator operator +(int n) {
		iterator it = *this;
		for (int i = 0; i < n; i++)
			++it;    //先实现++，在实现+就可以复用++
		return it;
	}
	iterator operator += (int n) {
		for (int i = 0; i < n; i++)
			++(*this);
		return *this;
	}
	iterator operator -- () {
		l_pointer = l_pointer->prev;
		return *this;

	}
	iterator operator --(int) {
		iterator it = *this;
		--(*this);
		return it;
	}
	iterator operator -(int n) {
		iterator it = *this;
		for (int i = 0; i < n; i++) {
			--it;
		}
		return it;
	}
	iterator operator -=(int n) {
		for (int i = 0; i < n; i++) {
			--(*this);
		}
		return *this;
	}
	T& operator *() {
		return l_pointer->l_value;
	}
	T* operator ->() {
		return &(l_pointer->l_value);
	}
private:
	node* l_pointer; //迭代器包含一个指向node的指针
};

反向迭代器

照着正向的修改几个地方就行。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
template<typename T>
class listreverseiterator {
	typedef listnode<T> node;
	typedef listreverseiterator iterator;
public:
	listreverseiterator() :l_pointer(nullptr) {};
	listreverseiterator(node* pointer) :l_pointer(pointer) {};
	~listreverseiterator() {};
	bool operator ==(const iterator& other) {
		return l_pointer == other.l_pointer;
	}
	bool operator !=(const iterator& other) {
		return l_pointer != other.l_pointer;

	}
	iterator& operator =(const iterator& other) {
		if (this == &other)
			return;
		l_pointer = other.l_pointer;
		return *this;
	}
	iterator& operator ++() {
		l_pointer = l_pointer->prev;
		return *this;
	}
	iterator& operator ++(int) {
		iterator it = *this;
		++(*this);
		return it;
	}
	iterator operator +(int n) {
		iterator it = *this;
		for (int i = 0; i < n; i++)
			++it;
		return it;
	}
	iterator operator += (int n) {
		for (int i = 0; i < n; i++)
			++(*this);
		return *this;
	}
	iterator operator -- () {
		l_pointer = l_pointer->next;
		return *this;

	}
	iterator operator --(int) {
		iterator it = *this;
		--(*this);
		return it;
	}
	iterator operator -(int n) {
		iterator it = *this;
		for (int i = 0; i < n; i++) {
			--it;
		}
		return it;
	}
	iterator operator -=(int n) {
		for (int i = 0; i < n; i++) {
			--(*this);
		}
		return *this;
	}
	T& operator *() {
		return l_pointer->l_value;
	}
	T* operator ->() {
		return &(l_pointer->l_value);
	}
private:
	node* l_pointer;
};

接下来完善list：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
class list {
	typedef listnode<T> node;
	typedef listiterator<T> iterator;  //加入迭代器
	typedef listreverseiterator<T> rverseiterator;

public:
  iterator begin() {    
		return iterator(l_head);
	};
	iterator end() {
		return iterator(nullptr);  //end指向list最后一个元素的后一个，也就是空，更严谨的写应该是l_tail->next
        //rbegin和rend就不再赘述
	};

find，insert和erase函数

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
iterator find(const T& value) {
	auto newnode = l_head;
	while (newnode != nullptr) {
		if (newnode->l_value == value)
			break;
	}
	return iterator(newnode);
}
iterator insert(iterator pos, const T& value) {
	insert(pos, 1, value); //直接复用插入n个相同值的insert，见下面
}
iterator insert(iterator pos, int n,const T& value) {
	if (pos == begin()) {
		for (int i = 0; i < n; i++)
			push_front(value);
		return begin();
	}
	else if (pos == end()) {
		auto tail = l_tail;
		for (int i = 0; i < n; i++)
			push_back(value);
		return iterator(tail->next);
	}
	else {
		for (int i = 0; i < n; i++) {
			auto newnode = new node(value);
			auto tmpprev = pos.l_pointer->prev;
			newnode->prev = tmpprev;
			tmpprev->next = newnode;
			newnode->next = pos.l_pointer;
			pos.l_pointer->prev = newnode;
			pos.l_pointer = newnode;
		}
		l_size += n;
		return pos;
	}
}
iterator erase(iterator pos) {
	if (pos == begin()) {
		auto node = l_head;
		if (l_size > 1) {
			l_head = l_head->next;
			l_head->prev = nullptr;
			delete node;

		}
		else {
			delete l_head;
			l_head = l_tail = nullptr;
		}
		l_size--;
		return begin();
	}
	if (pos == end()) { //本来就是无效位置
		return pos;
	}
	auto newnode = pos.l_pointer;
	if (newnode->prev != nullptr)
		newnode->prev->next = newnode->next;
	if (newnode->next != nullptr)
		newnode->next->prev = newnode->prev;
	auto tmp = newnode->next;
	delete newnode;
	l_size--;
	return iterator(tmp);
}
iterator erase(iterator first,iterator last) {
	for (auto it = first; it != last; it++) {
		erase(it);
	}
	return last;
}


补充函数

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
    bool empty() const {
		return l_size == 0;
	};
	int size() const {
		return l_size;
	};
	T& front() {
		if (l_size == 0)
			throw std::out_of_range("list is empty");
		return l_head->l_value;
	};
	const T& front()const {
		if (l_size == 0)
			throw std::out_of_range("list is empty");
		return l_head->l_value;
	};
	T& back() {
		if (l_size == 0)
			throw std::out_of_range("list is empty");
		return l_tail->l_value;
	};
	const T& back()const {
		if (l_size == 0)
			throw std::out_of_range("list is empty");
		return l_tail->l_value;
	};
	void clear() {
		while (l_size > 0) {
			pop_back();
		};
	}
	void assign(int n, const T& value) {
		clear();
		for (int i = 0; i < n; i++)
			push_back(value);
	}
	void remove(const T& value) {
    auto current = l_head;
    while (current != nullptr) {
        if (current->l_value == value) {
            // 如果当前节点是头节点
            if (current == l_head) {
                pop_front();
            }
            // 如果当前节点是尾节点
            else if (current == l_tail) {
                pop_back();
            }
            // 当前节点在中间
            else {
                auto prev = current->prev;
                auto next = current->next;
                prev->next = next;
                next->prev = prev;
                delete current;
                l_size--;
                current = next; // 更新当前节点为下一个节点，因为上一个已被删除
            }
        } else {
            current = current->next;
        }
    }
}
	void resize(int size) {
		if (size < l_size) {
			for (int i = 0; i < l_size - size; i++)
				pop_back();
		}
		else if (size > l_size) {
			for (int i = 0; i < size - l_size; i++)
				push_back(T());
		}
	}
	void merge(list<T>& other) {
		l_tail->next = other.l_head;
		other.l_head->prev = l_tail;
		l_tail = other.l_tail;
		l_size += other.l_size;
		other.l_head = other.l_tail = nullptr;
		other.l_size = 0;
	}
	void swap(list<T>& other) {
		if (this == &other)
			return;
		auto head = other.l_head;
		auto tail = other.l_tail;
		auto size = other.l_size;
		other.l_head = l_head;
		other.l_tail = l_tail;
		other.l_size = l_size;
		l_head = head;
		l_tail = tail;
		l_size = size;
	}
	void reverse() {
		if (l_size == 0 || l_size == 1)
			return;
		auto head = l_head;
		auto tail = l_tail;
		auto node = l_tail;
		while (node != nullptr) {
			auto tmpprev = node->prev;
			auto tmpnext = node->next;
			node->next = tmpprev;
			node->prev = tmpnext;
			node = tmpprev;
		}
		l_head = tail;
		l_tail = head;
	}