C++实现一个尽可能优雅的双向链表

这是「数据结构与算法」课程的一部分. 在这门课中, 我们将接触各种常见的数据结构, 并了解它们各种基本操作的实现方式.

这门课的第一章为顺序表, 其中包括一种数据结构“链表”. 我产生了一种想法, 为什么不借助C++强大的类封装能力, 实现一个自己的链表呢?

我的目标是想让这个链表尽可能的“优雅”. 这要求在使用这个链表时, 各种操作应尽可能的简洁直观. 我的目标是做的比C++ STL模版库的链表易用(虽然性能可能略低), 并且尽可能靠近python的列表.

注意: STL模版库的list是双向链表,但python的list, 据资料, 是基于变长顺序表. 这里说的靠近不是利用python list的底层逻辑, 而是实现和python list尽可能相似的调用方式.

使用例

话不多说, 先看使用例:

/* 本程序需要引用的外部库仅iostream */

/* 例子1 简单的添加数据、打印数据 */
list<int> list1;
for (int i = 1; i <= 10; ++i)
{
	list1.append(i);
}
cout << list1 << endl;

/* 例子2 列表嵌套 */
list<list<int>> list2;
int num = 1;
for (int i = 1; i <= 10; ++i)
{
	list<int> templist;
	for (int j = 0; j < i; ++j,++num)
	{
		templist.append(num);
	}
	list2.append(templist);
}
for (int i = 0; i < 10; ++i)
{
	for (int j = 0; j < list2[i].size(); ++j)
	{
		cout << list2[i][j] << " ";
	}
	cout << endl;
}

结果:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
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 
程序执行完成, 用时63微秒.

使用过python的人, 应该能看出我对python列表的借鉴(比如append()); 使用过C++ STL模版库的list的人, 应该能看出它比STL list在使用(尤其是遍历)上要简单一些.

类定义

列表的UML类图如下:

classDiagram 
    class node{
        +T data
        +node* next
        +node* prev
    }
    class list{
        -node* head
        -node* tail
        -int _size
        -node* temp
        -int tempindex
        
        +copy() list
        +slice(i1,i2,i3) list
        +size() int
        +append(data) int
        +insert(index,data) void
        +swap(i1,i2) void
        +pop(i=-1) T
        +remove(data) void
        +clear() void
        +operator[](index) T
        +operator=(data) list
        +operator+(data) list
        +operator+=(data) list
        #get(index) node*
        #swap(node,node) void
    }

在完善这个数据类型的过程中, 遇到了很多有趣的问题, 也学习到了很多C++语法特性, 比如模版类、析构函数、运算符重载、引用符&等等. 之后也许会慢慢整理遇到的各种问题以及经验.

实现方式

这里只是放上完整代码. 之后有机会新建帖子进行相关的解释.

#ifndef MYLIST
#define MYLIST
#include <iostream>

namespace my {


#define LOG(args) printf(args);


template <typename T>
class list{
private:
	class node{
	public:
		node(){}
		node(const T& dta){data = dta;}
		T data;
		node* next=nullptr;
		node* prev=nullptr;
	};
	class iterator_base{
	protected:
		node* ptr;
	public:
		iterator_base(node* p):ptr(p){}
		bool operator!=(const iterator_base& it)const{return ptr!=it.ptr;}
		void operator++(){ptr=ptr->next;}void operator++(int){ptr=ptr->next;}
	};
	class iterator:public iterator_base{
	public:
		using iterator_base::iterator_base,iterator_base::ptr;
		T& operator*(){return ptr->data;}
	};
	class const_iterator:public iterator_base{
	public:
		using iterator_base::iterator_base,iterator_base::ptr;
		const T& operator*(){return ptr->data;}
	};
	node* head;
	node* tail;
	int _size;
	node* temp;
	int tempindex = 0;
public:

	iterator begin(){return iterator(head->next);}
	iterator end(){return iterator(tail);}
	const_iterator begin()const{return const_iterator(head->next);}
	const_iterator end()const{return const_iterator(tail);}



	list();/* 构造函数 */

	list(const list<T>&);/* 拷贝重载，
	做了一些区分：用这个重载是做一个影子链表，用等号重载是做一个完整地拷贝。 */
	/* 如此，在初始化和函数传递时默认时 */

	~list();/* 析构函数 */

	list<T> copy();/* 复制 */

	list<T> slice(const int,const int,const int)const;/* 切片 */

	int size()const{return _size;}/* 得到长度 */

	int append(const T&);/* 追加 */

	list<T>& insert(const int,const T&);/* 插入 */

	void swap(const int,const int);/* 交换 */

	T pop(const int i=-1);/* 弹出并删除 */

	void remove(const T&);/* 删除所有和参数相同的元素 */

	void clear();/* 清空 */

	T& operator[](const int);/* 索引[]运算 */

	list<T>& operator=(const list<T>&);/* 赋值=运算 */

	list<T> operator+(const list<T>&);/* 加+运算 */

	void operator+=(list<T>&);/* 自增+=运算 */
	
	void operator+=(const T&);/* 自增+=运算 */


protected:
	node* gethead()const{return head;}
	node* gettail()const{return tail;}
	node* get(int i);/* 索引，得到节点指针 */
	void swap(node*,node*);/* 交换 */
	node* getFromHead(int);
	node* getFromTail(int);
	node* getFromTemp(int);
	void resetTemp(){temp=head;tempindex = 0;}/* 重置temp指针保证它指向链中的某个项。 */
	/* fun fact：虽然重置tempindex=0，但是现在temp指向head而不是第一个“元素”。
	但这无伤大雅。由于距离的最小值判定的逻辑，查找时会优先从head向后查找，而不是用temp查找。 */
	int dis(int a,int b){return a>=b?a-b:b-a;}
};

template <typename T>
std::ostream& operator<<(std::ostream& out,const list<T>& L){
	/* 运算符：重载cout输出 */
	out << "[";
	bool flag = false;
	for(auto i:L){
		if(flag){
			out << ", ";
		}
		else{
			flag = true;
		}
		out << i;
	}
	out << "]";
	return out;
}

template <typename T>
T& list<T>::operator[](const int i){
	/* 运算符：索引 */
	return get(i)->data;
}
template <typename T>
list<T>& list<T>::operator=(const list<T> &li){
	if(this==&li)return *this;
	/* 运算符：赋值 */
	clear();
	node* t = li.head->next;
	while(t!=li.tail){
		append(t->data);
		t = t->next;
	}
	return *this;
}
template <typename T>
list<T> list<T>::operator+(const list<T>& li){
	auto rl = this->copy();

	node* t = li.head->next;
	while(t!=li.tail){
		rl.append(t->data);
		t = t->next;
	}
	return rl;
}
template <typename T>
void list<T>::operator+=(list<T>& li){
	if(&li == this){
		std::cout << "ERROR: self += detected. plz use + instead.";
		exit(1);
		return;
	}
	/* O1,但是引用的li会清空 */
	/* 把中间接上 */
	tail->prev->next = li.head->next;
	li.head->next->prev = tail->prev;
	/* 把结尾接上 */
	tail->prev = li.tail->prev;
	tail->prev->next = tail;
	/* 更新size */
	_size+=li.size();
	/* 让li首尾相接置空,但是不删除里面的元素(里面的元素归this了.) */
	li.head->next = li.tail;
	li.tail->prev = li.head;
	li._size = 0;
}
template <typename T>
void list<T>::operator+=(const T& dta){
	append(dta);
}
// list<T> list<T>::operator()(const int,const int,con s){}
template <typename T>
list<T> list<T>::copy(){
	list<T> returnlist;
	for (int i = 0; i < _size; ++i)
	{
		returnlist.append((*this)[i]);
	}
	return returnlist;
}

template <typename T>
list<T> list<T>::slice(int p1, int p2, int p3) const{
	list<T> returnlist;
	if(p3>0){
		for (int i = p1; i < p2; i+=p3)
		{
			returnlist.append((*this)[i]);
		}
	}
	else if(p3<0){
		for (int i = p1; i > p2; i+=p3)
		{
			returnlist.append((*this)[i]);
		}
	}
	return returnlist;
}

template <typename T>
list<T>::list(){
	// cout << "list() called"<<endl;
	head = new node;
	tail = new node;

	resetTemp();

	head->next = tail;
	tail->prev = head;
	_size = 0;
}
template <typename T>
list<T>::list(const list<T>& li):list(){
	operator=(li);
}
template <typename T>
void list<T>::clear(){
	node *t = head->next;
	while(t!=tail){
		t = t->next;
		delete t->prev;
	}
	head->next = tail;
	tail->prev = head;
	resetTemp();
	_size=0;
}
template <typename T>
list<T>::~list(){
	// cout << "~list called for:"<<*this<<endl;
	clear();
	delete head;
	delete tail;
	head = nullptr;tail = nullptr;temp = nullptr;
}
template <typename T>
int list<T>::append(const T& dta){
	temp = new node(dta);
	tempindex = _size;
	
	tail->prev->next = temp;
	temp->prev = tail->prev;
	temp->next = tail;
	tail->prev = temp;
	_size++;
	return 0;
}
template <typename T>
typename list<T>::node* list<T>::get(int i){
	if(i>=_size||i<-_size){
		LOG("index out range");
		exit(-1);
		return 0;//这是个无效值
	}
	int mindis = 0x7fffffff;
	int minway = 0;
	if(dis(i,0)<mindis)
		{mindis = dis(i, 0);minway = 1;}
	if(dis(i, -_size)<mindis)
		{mindis = dis(i, -_size);minway = 2;}
	if(dis(i, _size-1)<mindis)
		{mindis = dis(i, _size-1);minway = 3;}
	if(dis(i, -1)<mindis)
		{mindis = dis(i, -1);minway = 4;}
	if(dis(i,tempindex)<mindis)
		{mindis = dis(i,tempindex);minway = 5;}
	if(dis(i+_size,tempindex)<mindis)
		{mindis = dis(i,tempindex);minway = 6;}
	switch (minway) {
	case 1:return getFromHead(i);
	case 2:return getFromHead(i+_size);
	case 3:return getFromTail(i-_size);
	case 4:return getFromTail(i);
	case 5:return getFromTemp(i);
	default:return getFromTemp(i+_size);
	}

}
template <typename T>
typename list<T>::node* list<T>::getFromHead(int targeti){
	// LOG("GFH called\n");
	temp = head->next;
	int i=0;
	while(i!=targeti){
		temp = temp->next;
		i++;
	}
	tempindex = targeti;
	return temp;
}
template <typename T>
typename list<T>::node* list<T>::getFromTail(int negativeTargeti){
	// LOG("GFT called\n");
	temp = tail->prev;
	int i=-1;
	while(i!=negativeTargeti){
		temp = temp->prev;
		i--;
	}
	tempindex = negativeTargeti+_size;
	return temp;
}
template <typename T>
typename list<T>::node* list<T>::getFromTemp(int targeti){
	// LOG("GFTMP called\n");
	while(targeti>tempindex)
	{
		temp = temp->next;
		tempindex++;
	}
	while(targeti<tempindex){
		temp = temp->prev;
		tempindex--;
	}
	return temp;
}
template <typename T>
void list<T>::swap(int ia,int ib){
	node* a = get(ia);
	node* b = get(ib);
	swap(a,b);
	tempindex = ia;//temp指向b,b的下标变为了ia.
}
template <typename T>
void list<T>::swap(node *a,node *b){
	node *anext = a->next;
	node *bnext = b->next;
	node *aprev = a->prev;
	node *bprev = b->prev;
	if(a->next==b){
		b->prev = aprev;
		a->next = bnext;
		b->next = a;
		a->prev = b;
		bnext->prev = a;
		aprev->next = b;
	}
	else if(a->prev==b){
		b->next = anext;
		a->prev = bprev;
		a->next = b;
		b->prev = a;
		anext->prev = b;
		bprev->next = a;
	}
	else{
		a->next = bnext;
		b->next = anext;
		a->prev = bprev;
		b->prev = aprev;
		anext->prev = b;
		aprev->next = b;
		bnext->prev = a;
		bprev->next = a;
	}
}
template <typename T>
list<T>& list<T>::insert(int i, const T& value){
	node *t;
	if(i>=_size){
		//如果用户做了这样的输入，多半是想插入到末尾，而不是在最后一个位置的前面插入。故直接调用append
		append(value);
		return *this;
	}
	if(i<-_size){
		i = 0;
	}
	t = get(i);
	if(!t)return *this;
	temp = new node(value);
	t->prev->next = temp;
	temp->prev = t->prev;
	temp->next = t;
	t->prev = temp;
	_size++;
	return *this;
}
template <typename T>
T list<T>::pop(int i){
	node *t = get(i);
	t->prev->next = t->next;
	t->next->prev = t->prev;

	T dta = t->data;

	temp = t->next;//删除元素时，要把那个指向链表中间的temp指针指到一个在链上的节点。
	_size--;
	delete t;
	return dta;
}
template <typename T>
void list<T>::remove(const T& target){
	for (int i = 0; i < _size;)
	{
		if(get(i)->data==target){
			pop(i);
		}
		else{
			i++;
		}
	}
}

}

#endif