双链表

双链表的意义

单链表相对于顺序表，确实在某些场景下解决了一些重要的问题，例如在需要插入或者删除大量元素的时候，它并不需要像顺序表一样移动很多元素，只需要修改指针的指向就可以了，其时间复杂度为 O(1) 但是这可是有前提的，那就是这一切都基于确定节点后，纯粹考虑删除和插入的情况下，但是如果我们仍未确定节点的位置，那么单链表就会出现一些问题了，例如我们来看一下删除这个操作

删除操作

单链表:

对应图中的节点，想要删除第2个节点 a1 只需要将首元结点的指针指向到第三个节点的地址去

但是问题就在于我们如何得到待删除节点的前驱，也就是我们图中的首元结点，我们给出两种方法

A：定位待删除节点的同时，一直顺便保存当前节点的前驱
B：删除节点后，重新回到单链表表头，定位到其指定前驱

但是无论我们选择哪一种方法，指针的总移动数都会是 2n 次，而双链表却在这一类型问题上做出了很好的处理

双链表:

单链表中之所以出现问题，就是因为各个节点只有一个指向后继的指针域 next，只能向后移动查找，一旦我们想要查询前一节点，就变得很麻烦，所以双链表就在每个节点前面增加一个指向前驱的指针域 prior，这样我们就可以直接定位到我们的前一个节点了，这也就是双链表

注意：为了统一运算，避免特殊情况的出现，我们也常常在尾部设置一个 “尾部头结点” 其 next 指针域为空

线性表的抽象数据类型定义

我们在给出双链表的定义之前我们还是需要先引入我们线性表的抽象数据类型定义

#ifndef _LIST_H_

#define _LIST_H_

#include<iostream>

using namespace std;

class outOfRange{};

class badSize{};

template<class T>

class List {

public:

    // 清空线性表

	virtual void clear()=0;

    // 判空，表空返回true，非空返回false

	virtual bool empty()const=0;

    // 求线性表的长度

	virtual int size()const=0;

    // 在线性表中，位序为i[0..n]的位置插入元素value

	virtual void insert(int i,const T &value)=0;

    // 在线性表中，位序为i[0..n-1]的位置删除元素

	virtual void remove(int i)=0;

    // 在线性表中，查找值为value的元素第一次出现的位序

	virtual int search(const T&value)const=0;

    // 在线性表中，查找位序为i的元素并返回其值

	virtual T visit(int i)const=0;

    // 遍历线性表

	virtual void traverse()const=0;

    // 逆置线性表

	virtual void inverse()=0;

	virtual ~List(){};

};

/*自定义异常处理类*/ 

class outOfRange :public exception {  //用于检查范围的有效性

public:

	const char* what() const throw() {

		return "ERROR! OUT OF RANGE.\n";

	}

};

class badSize :public exception {   //用于检查长度的有效性

public:

	const char* what() const throw() {

		return "ERROR! BAD SIZE.\n";

	}

};

#endif

双链表类型的定义

#ifndef _SEQLIST_H_

#define _SEQLIST_H_

#include "List.h"

#include<iostream>

using namespace std;

template<class elemType>

//elemType为双链表存储元素类型

class doubleLinkList:public List<elemType> {

private:

	//节点类型定义

	struct Node {

		//节点的数据域

		elemType data;

		//节点的两个指针域

		Node *prior, *next;

		//两个构造函数

		Node(const elemType &value, Node *p = NULL, Node *n = NULL) {

			data = value;

			prior = p;

			next = n;

		}

		Node():next(NULL), prior(NULL) {}

		~Node(){}

	};

	//单链表的头指针

	Node *head;

	//单链表的尾指针

	Node *tail;

	//单链表的当前长度

	int curLength;

	//返回指向位序为i的节点的指针

	Node *getPosition(int i)const; 

public:

	doubleLinkList();

	~doubleLinkList();

	//清空单链表，使其成为空表

	void clear();

	//带头结点的单链表，判空

	bool empty()const {return head -> next == NULL;}

	//返回单链表的当前实际长度

	int size()const {return curLength;}

	//在位序i处插入值为value的节点表长增1

	void insert(int i, const elemType &value);

	//删除位序为i的节点的值，表长减1

	void remove(int i);

	//查找值为value的节点的第一次出现的位置

	int search(const elemType &value)const;

	//查找值为value的节点的前驱的位序

	int prior(const elemType&value)const;

	//访问位序为i的节点的值，0定位到首元结点

	elemType visit(int i)const;

	//遍历单链表

	void traverse()const;

	//逆置单链表

	void inverse();

	//合并单链表

};

双链表基本运算的实现

(一) 构造与析构函数

template <class elemType>

doubleLinkList<elemType>::doubleLinkList() {

	//头尾节点分别指向 头结点和尾部头结点

	head = new Node;

	tail = new Node;

	head -> next = tail;

	tail -> prior = head;

} 

template <class elemType>

doubleLinkList<elemType>::~doubleLinkList() {

	Node *p = head -> next, *tmp;

	//头结点的后继是尾部头结点

	head -> next = tail;

	//尾部头结点的前驱是头结点

	tail -> prior = tail;

	while(p != tail) {

		tmp = p -> next;

		delete p;

		p = tmp;

	}

	curLength = 0;

}

(二) 查找位序为i的节点的地址

template <class elemType>

typename doubleLinkList<elemType>::Node *doubleLinkList<elemType>::getPosition(int i) const {

	Node *p = head;

	int count = 0;

	if(i < -1 || i > curLength)

		return NULL;

	while(count <= -1) {

		p = p -> next;

		count++;

	}

	return p;

}

(三) 查找值为value的节点的位序

template <class elemType>

int doubleLinkList<elemType>::search(const elemType &value) const {

	Node *p = head -> next;

	int i = 0;

	while(p != tail && p -> data != value) {

		p = p -> next;

		i++;

	}

	if(p == tail)

		return -1;

	else

		return i;

}

(四) 插入元素

template <class elemType>

void doubleLinkList<elemType>::insert(int i, const elemType &value) {

	Node *p, * tmp;

	if(i < 0 || i > curLength)

		throw outOfRange();

	p = getPosition(i);

	tmp = new Node(value, p -> prior, p);

	//p原先的前驱的后继指向tmp

	p -> prior -> next = tmp;

	//修改p的前驱为tmp

	p -> prior = tmp;

	++curLength;

}

(五) 删除位序为i的节点

template <class elemType>

void doubleLinkList<elemType>::remove(int i) {

	Node *p;

	if(i < 0 || i > curLength)

		throw outOfRange();

	p = getPosition(i);

	p -> prior -> next = p -> next;

	p -> next -> prior = p -> prior;

	delete p;

	--curLength;

}

(六) 访问位序为 i的节点的值

template <class elemType>

elemType doubleLinkList<elemType>::visit(int i) const {

	//visit 不嫩直接用getPosition判断范围是否合法，因为其范围为[-1,curLength]

	if(i < 0 || i > curLength -1)

		throw outOfRange();

	//合法以后

	Node *p = getPosition(i);

	return p -> data;

}

(七) 遍历双链表

template <class elemType>

void doubleLinkList<elemType>::traverse() const {

	Node *p = head -> next;

	cout << "traverse: ";

	while(p != tail) {

		cout << p -> data << " ";

		p = p -> next;

	}

	cout << endl;

}

(八) 遍历双链表

template <class elemType>

void doubleLinkList<elemType>::inverse() {

	Node *tmp, *p = head -> next;

	//构成双空链表

	head -> next = tail;

	tail -> prior = head;

	while(p != tail) {

		tmp = p -> next;

		p -> next = head -> next;

		p -> prior = head;

		head -> next -> prior = p;

		head -> next = p;

		p = tmp;

	}

}

结尾：

如果文章中有什么不足，或者错误的地方，欢迎大家留言分享想法，感谢朋友们的支持！

如果能帮到你的话，那就来关注我吧！如果您更喜欢微信文章的阅读方式，可以关注我的公众号

在这里的我们素不相识，却都在为了自己的梦而努力 ❤

一个坚持推送原创开发技术文章的公众号：理想二旬不止

巴特西

双链表的基本实现与讲解（C++描述）

双链表