数据结构与算法详解——链表篇（附c++实现代码）

• 链表与数组的内存布局
• 链表与数组的优缺点比较
• 数组的插入和删除
• 链表的插入删除
• c++代码示例
• • list类的定义
  • 构造函数
  • 顺序访问（遍历）
  • 插入
  • 删除
  • 析构
  • 完整代码
  • 简单测试代码
  • 几个语法问题

  这里假设是在int为4字节的系统上，数组存储在一段连续的内存上，例如图中从地址1000开始，每个格子存放一个4字节的int，就可以通过简单的加法计算出要访问的某一项的地址了，因此数组可以做到随机访问(random-access)，也就是任意访问数组某一项a[x]时，可以通过(a的地址+x*sizeof(int))计算得到a[x]地址，时间复杂度是O(1)。
  相反，链表的内存是不连续的，代价就是要存储多一个next指针，指向下一个结点的地址，通过这个地址找到链表的下一个结点，因此链表支持顺序访问(sequential access)，也就是当我要访问链表的第x个结点时，我要从头结点开始按顺序遍历next指针才能找到这个结点，时间复杂度是O(n)。

  数组进行插入操作时，要把插入的位置打后的所有元素往后移，把插入的位置腾出来，所以需要O(n)的时间复杂度，代码表示：

void insert(int index,int data){
//size表示数组中存储的元素数量，capacity表示容量即new的时候申请的空间大小
	if(size==capacity)	
		resize();
	for(int i=size-1;i>=index;i--)
		array[i+1]=array[i];
	array[index]=data;
	++size;
}

  同理，数组进行删除时，需要把删除的位置打后的所有元素往前移，同样是需要O(n)的时间复杂度。
  访问在上面内存布局中已经讲述，这里不再复述。
  这里还有个扩容的操作，也就是当申请的空间不够用时，需要重新申请一块新的空间，然后将旧空间的元素拷贝到新空间上去，然后释放掉旧空间的内存，也是需要O(n)的时间复杂度。

  链表的插入和删除就是指针的替换，下面我用伪代码表示

//插入，newNode表示要插入的结点(上图中2的结点)，在preNode(上图中1的结点)后面插入
Node* newNode=new Node(data);	
newNode->next=preNode->next;	//上图2指向4的那个箭头
preNode->next=newNode;			//上图1指向2的那个箭头

  但是这里有几个问题：
  1、preNode如何得到？
  答：preNode就是一开始我们在内存布局中说到的从头结点开始顺序访问next得到的，比如要在第2个元素后插入，那么就遍历到第二个真正存储数据结点，所以如果单纯只是算这几个指针替换的时间复杂度的话就是O(1)，但是要完成整个删除操作需要顺序访问，时间复杂度是O(n)。
  2、如果一开始链表没有任何结点为空时，上述插入逻辑就行不通了，所以要打个补丁：

if(head==nullptr)
	head=newNode;

  3、那如果我想在头结点前插入呢，也就是让插入的结点成为新的头结点，还要再打个补丁：

Node* oldhead=head;
head=newNode;
head->next=oldhead;

  针对问题2和3，我们可以通过加入一个哨兵解决，让插入的逻辑都统一成第一段插入代码那样。
  我们可以让头结点变成一个哨兵，不存储数据，真正存储数据的第一个结点是head->next，也就是初始化时head不赋值为nullptr，而是创建一个新结点，这样就能让我们的插入和删除操作逻辑统一起来，后面有实例代码。

  删除也是同理，这里就不再过多描述，伪代码：

//删除，delNode表示要插入的结点(上图中2的结点)，在preNode(上图中1的结点)后面删除
preNode->next=delNode->next;	//上图1指向4的那个箭头
delete delNode;

  至于扩容，链表天然就支持扩容，不用像数组一样预先申请一大段空间，而是需要时才申请一个结点的空间，链表的扩容已经融合在插入操作中了。

  在这里我实现了一个带头结点（哨兵）和尾结点（非哨兵）的双向列表，相对来说比较全面一点，如果你只需要单向列表，就把prev指针的逻辑删除掉就好，不需要尾结点就把tail的逻辑删除掉就好。

// list:双向链表
template
class list {
private:
	struct Node {		//struct默认是public,class默认是private，可以用class和friend，也可以class Node元素掌握设置为public
		DataType data;
		Node* prev;
		Node* next;
		Node() {}
		Node(const DataType& d) :data{ d }, prev{ nullptr }, next{nullptr} {}
		//这里不需要delete prev和next因为它们不是new出来的，否则会无限循环调用~Node()，这里可以不用写这个析构函数
		//~Node() { std::cout << "~Node()" << std::endl;}
	};

private:
	Node* head;	//哨兵，不存储值
	Node* tail;		//尾部，非哨兵
	int size;

public:
	list();
	list(const list& ls);
	list(std::initializer_list init_list);
	~list();
	const list& operator=(const list& ls);
	DataType& operator[](int index);	//返回DataType&，那么ls[n]可以赋值，比如ls[2]=xxx
	DataType operator[](int index) const;	//返回DataType，那么ls[n]不可以赋值，后面带const让const list对象有一个可以调用的版本
	void insert(const DataType data, int pos);
	void remove(const DataType data);
	void remove_at(int index);
	void append(DataType data);		//链表尾部追加
	void printList() const;
	bool empty();
	void clear();
	int length() const;

private:
	Node* get(int index) const;	//因为operator[]() const里会调用get，所以get后面也要有const
	Node* search(DataType data);
	void append(Node* node);
	void remove(Node* node);
};

template
list::list() {
	head = new Node();
	head->prev = head->next = nullptr;
	tail = head;
	size = 0;
}

  上面说哨兵时也有说到，head在初始化时就会创建，但是不存储值，注意tail不是哨兵，但是初始化时也将head赋值给tail，为后面写插入删除等操作时方便。

template
list::list(std::initializer_list init_list) :list() {//委托list()初始化
	for (auto e : init_list) 
		append(e);
}

  这里使用了c++11的初始化列表std::initializer_list，那么在使用时就可以用list ls = { 1,2,3,4 }这种方式进行初始化。

  这儿有两个版本，一个是根据index进行顺序访问，一个根据数据进行顺序访问（或者说查找）

template
 typename list::Node* list::get(int index) const{	//注意这里Node也要带类作用域符，而且前面要加typename
	 if (index >= size || index < 0) {
		 std::cerr << "index out of boundn";
		 exit(1);
	 }
	int count;
	Node* node;
	//这里小优化一下，如果是小于等于size/2的，就从前往后数，否则从后往前数
	if (index <= size / 2) {
		count = 0;		//count表示head->next那个结点的index
		node = head->next;
		while (count++ < index)	//循环退出条件是count==index（注意count也是从0开始,这里是后置++，那么count的含义和index一样了，也可以写成++count<=index）
			node = node->next;
	}
	else {
		count = size - 1;		//count表示tail那个结点的index,这里要注意size是从1开始，所以要-1
		node = tail;
		while (count-- > index)	//循环退出条件是countindex
			node = node->prev;
	}
	return node;
}

  这里进行了小优化，如果要访问前一半的结点，那么就从头开始遍历，如果要访问后一半的结点，就从尾往前遍历。

 template
 typename list::Node* list::search(DataType data) {
	Node* node = head->next;
	while (node != nullptr) {
		if (node->data == data)
			return node;
		node = node->next;
	}
		
	return nullptr;
 }

  这儿也就是两个版本，一个是指定第pos个位置插入，一个是直接插入到尾部。

template
void list::insert(const DataType data, int pos) {	//pos从0开始
	if (pos > size ||pos < 0) {
		std::cerr << "index out of boundn";
		exit(1);
	}
	if (pos == size) {		//在尾插入，直接调用append在尾部追加,如果合并到下面的话get(pos)会越界
		append(data);
	}
	else {		
		Node* node = get(pos);
		Node* insert_node = new Node(data);
		insert_node->next = node;
		insert_node->prev = node->prev;
		node->prev->next = insert_node;
		node->prev = insert_node;
		
		++size;
	}
}

  看到这儿可能会有疑惑，上面不是说用了哨兵能让逻辑统一吗，为什么这儿还是有if else情况分类，没能统一成else的那段代码？
  因为我这段代码加了个尾结点，头结点是哨兵，但是尾结点不是哨兵，那么当我要在尾结点插入的时候就会要打补丁，和我们上面说的插入到头结点的情况是类似的，不矛盾，这里也可以让尾结点成为哨兵，代码也能统一逻辑。

template
void list::append(DataType data) {//在尾部插入
	Node* node = new Node(data);
	append(node);
}

template
void list::append(Node* node) {
	if (head->next == nullptr) {	
		head->next = node;
		node->prev = head;
		tail = node;
	}
	else {	//如果head->next !=nullptr也意味着tail !=nullptr
		node->prev = tail;
		tail->next = node;
		tail = node;
	}
	++size;
}

  这儿也就是两个版本，一个是删除指定data的结点，一个是删除指定位置的结点。

template
void list::remove(const DataType data) {
	Node* node = search(data);
	remove(node);
}

template
void list::remove_at(int index) {
	remove(get(index));
}

template
void  list::remove(Node* node) {
	if (node == nullptr)return;
	if (node == tail) {
		node->prev->next = nullptr;
		tail = node->prev;
	}
	else {
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}
	delete node;
	--size;
}

template
list::~list() {
	std::cout << "~list()" << std::endl;
	clear();
	delete head;
	//注意这里不用delete tail，因为tail在clear()里已经被delete过了，否则会出现同一块内存delete了两次，会出错
}

template
void list::clear() {
	Node* node = head->next;
	while (node != nullptr) {
		Node* tmp = node;
		node = node->next;
		delete tmp;
	}
	head->prev = head->next = nullptr;
	size = 0;
}

#ifndef LIST_H
#define LIST_H

#include 
#include 

// list:双向链表
template
class list {
private:
	struct Node {		//struct默认是public,class默认是private，可以用class和friend，也可以class Node元素掌握设置为public
		DataType data;
		Node* prev;
		Node* next;
		Node() {}
		Node(const DataType& d) :data{ d }, prev{ nullptr }, next{nullptr} {}
		//这里不需要delete prev和next因为它们不是new出来的，否则会无限循环调用~Node()，这里可以不用写这个析构函数
		//~Node() { std::cout << "~Node()" << std::endl;}
	};

private:
	Node* head;	//哨兵，不存储值
	Node* tail;		//尾部，非哨兵
	int size;

public:
	list();
	list(const list& ls);
	list(std::initializer_list init_list);
	~list();
	const list& operator=(const list& ls);
	DataType& operator[](int index);				//返回DataType&，那么ls[n]可以赋值，比如ls[2]=xxx
	DataType operator[](int index) const;		//返回DataType，那么ls[n]不可以赋值，后面带const让const list对象有一个可以调用的版本
	void insert(const DataType data, int pos);
	void remove(const DataType data);
	void remove_at(int index);
	void append(DataType data);		//链表尾部追加
	void printList() const;
	bool empty();
	void clear();
	int length() const;

private:
	Node* get(int index) const;		//因为operator[]() const里会调用get，所以get后面也要有const
	Node* search(DataType data);
	void append(Node* node);
	void remove(Node* node);
};

template
list::list() {
	head = new Node();
	head->prev = head->next = nullptr;
	tail = head;
	size = 0;
}

template
list::list(const list& ls):list() {	//委托list()初始化
	std::cout << "拷贝构造n" << std::endl;
	Node* node = ls.head->next;
	while (node != nullptr) {
		//注意这里不能调用append(node)，因为append(node)是将形参ls里的node添加到链表，而append(node->data)是会新建一个node添加到链表上
		append(node->data);
		node = node->next;
	}
}

template
list::list(std::initializer_list init_list) :list() {
	for (auto e : init_list) 
		append(e);
}

template
list::~list() {
	std::cout << "~list()" << std::endl;
	clear();
	delete head;
	//注意这里不用delete tail，因为tail在clear()里已经被delete过了，否则会出现同一块内存delete了两次，会出错
}

template
const list& list::operator=(const list& ls) {
	std::cout << "=n";
	if (&ls == this)return *this;
	clear();
	Node* node = ls.head->next;
	while (node != nullptr) {
		//注意这里不能调用append(node)，因为append(node)是将形参ls里的node添加到链表，而append(node->data)是会新建一个node添加到链表上
		append(node->data);
		node = node->next;
	}
	return *this;
}

template
DataType& list::operator[](int index) {
	return get(index)->data;
}

template
DataType list::operator[](int index) const{
	return get(index)->data;
}

template
void list::insert(const DataType data, int pos) {	//pos从0开始
	if (pos > size ||pos < 0) {
		std::cerr << "index out of boundn";
		exit(1);
	}
	if (pos == size) {		//在尾插入，直接调用append在尾部追加,如果合并到下面的话get(pos)会越界
		append(data);
	}
	else {		
		Node* node = get(pos);
		Node* insert_node = new Node(data);
		insert_node->next = node;
		insert_node->prev = node->prev;
		node->prev->next = insert_node;
		node->prev = insert_node;
		
		++size;
	}
}


template
void list::remove(const DataType data) {
	Node* node = search(data);
	remove(node);
}

template
void list::remove_at(int index) {
	remove(get(index));
}

template
void  list::remove(Node* node) {
	if (node == nullptr)return;
	if (node == tail) {
		node->prev->next = nullptr;
		tail = node->prev;
	}
	else {
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}
	delete node;
	--size;
}


template
void list::append(DataType data) {
	Node* node = new Node(data);
	append(node);
}

template
void list::append(Node* node) {
	if (head->next == nullptr) {	
		head->next = node;
		node->prev = head;
		tail = node;
	}
	else {	//如果head->next !=nullptr也意味着tail !=nullptr
		node->prev = tail;
		tail->next = node;
		tail = node;
	}
	++size;
}
template
 typename list::Node* list::get(int index) const{	//注意这里Node也要带类作用域符，而且前面要加typename
	 if (index >= size || index < 0) {
		 std::cerr << "index out of boundn";
		 exit(1);
	 }
	int count;
	Node* node;
	//这里小优化一下，如果是小于等于size/2的，就从前往后数，否则从后往前数
	if (index <= size / 2) {
		count = 0;		//count表示head->next那个结点的index
		node = head->next;
		while (count++ < index)	//循环退出条件是count==index（注意count也是从0开始,这里是后置++，那么count的含义和index一样了，也可以写成++count<=index）
			node = node->next;
	}
	else {
		count = size - 1;		//count表示tail那个结点的index,这里要注意size是从1开始，所以要-1
		node = tail;
		while (count-- > index)	//循环退出条件是countindex
			node = node->prev;
	}
	return node;
}

 template
 typename list::Node* list::search(DataType data) {
	Node* node = head->next;
	while (node != nullptr) {
		if (node->data == data)
			return node;
		node = node->next;
	}
		
	return nullptr;
 }

template
void list::printList() const {
	if (size<=0)return;
	Node* node = head->next;
	while (node != nullptr) {
		std::cout << node->data << " ";
		node = node->next;
	}
	std::cout << "         length:" << length() << std::endl;
}

template
bool  list ::empty() {
	return size == 0;
}

template
void list::clear() {
	Node* node = head->next;
	while (node != nullptr) {
		Node* tmp = node;
		node = node->next;
		delete tmp;
	}
	head->prev = head->next = nullptr;
	size = 0;
}

template
int  list::length() const {
	return size;
}

#endif

#include "list.h"
#include 

int main() {
	list ls = { 1,2,3,4 };
	ls.printList();
	ls.append(5);
	ls.printList();
	ls.insert(0, 0);
	ls.insert(ls.length(), 6);
	ls.printList();
	ls.remove(0);
	ls.printList();
	ls.remove_at(0);
	ls.printList();
	ls.remove_at(ls.length()-1);
	ls.printList();
	ls[2] = 1;
	ls.printList();
	const list const_ls = { 1,2,3 };
	std::cout << const_ls[2] << std::endl;
	const_ls.printList();
	
	list ls1 = ls;		//调用拷贝构造
	ls1.printList();
	list ls2;
	ls2 = ls;				//调用operator=
	ls2.printList();
	return 0;
}

  1、为什么析构函数中不能delete tail？
  答：因为tail不是哨兵，tail在clear中已经delete过一次了，如果在再单独delete一次，会导致同一块内存被delete两次的错误。
  2、为什么operator[]有两个版本，一个版本返回值是引用，一个版本返回值是数据类型且尾部加了const？
  答：返回引用的版本是为了能以ls[n]=x进行赋值。返回数据类型且尾部加了const是为了让const对象有一个能调用版本进行访问，但是不能进行赋值（因为是const对象）因此不需要返回引用类型。
  3、为什么operator=返回值带const，有什么作用？
  答：首先要知道：

list ls1 = ls;		//调用拷贝构造，并不是operator=
list ls2;
ls2 = ls;				//调用operator=

  operator=只是对ls2进行操作，取得的并不是operator=的返回值，所以ls2也不是const。

//(ls2 = ls) = ls1; // operator=的返回值带const是为了防止这样的赋值

  这里实际上是 (ls2.operator=(ls)).operator=(ls1)，而(ls2.operator=(ls))返回的是const，所以第二个operator=调用错误。