链表

来自NOCOW

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这篇文章是指线性链表，对于非线性的其他链式结构，参见树、图、跳表、指针等。

链表是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

[编辑] 结构

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要储存反向的指针，见下面的双向链表）节点。

相对于下面的双线链表，这种普通的，每个节点只有一个指针的链表也叫单向链表，或者单链表，通常用在每次都只会按顺序遍历这个链表的时候（例如图的邻接表，通常都是按固定顺序访问的）。

链表也有很多种不同的变化：

[编辑] 双向链表

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数组里的情况，也可以直接用这个数组表示链表并用第0个或者第-1个（如果编译器支持）节点固定的表示这个虚拟节点。

[编辑] 循环链表

循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表一般用在第一个节点的位置在哪无所谓，或者根本不会修改的链表（不过不会修改的链表用顺序表实现往往更容易）。否则，对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可能比较不好处理。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。

另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

[编辑] 块状链表

主条目：块状链表

块状链表本身是一个链表，但是链表储存的并不是一般的数据，而是由这些数据组成的顺序表。每一个块状链表的节点，也就是顺序表，可以被叫做一个块。

块状链表通过使用可变的顺序表的长度和特殊的插入、删除方式，可以在达到 $O( \sqrt n )$ 的复杂度。块状链表另一个特点是相对于普通链表来说节省内存，因为不用保存指向每一个数据节点的指针。

[编辑] 其它扩展

根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向，反向标记加在边上可能会更方便。

对于非线性的链表，可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn)，和平衡二叉树一样。

[编辑] 存储结构

链表中的节点不需要以特定的方式存储，但是集中存储也是可以的，主要分下面这几种具体的存储方法：

共用存储空间: 链表的节点和其它的数据共用存储空间，优点是可以存储无限多的内容（不过要处理器支持这个大小，并且存储空间足够的情况下），不需要提前分配内存；缺点是由于内容分散，有时候可能不方便调试。
独立存储空间: 一个链表或者多个链表使用独立的存储空间，一般用数组或者类似结构实现，优点是可以自动获得一个附加数据：唯一的编号，并且方便调试；缺点是不能动态的分配内存。当然，另外的在上面加一层块状链表用来分配内存也是可以的，这样就解决了这个问题。这种方法有时候被叫做数组模拟链表，但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针，这种下标索引其实也是逻辑上的指针，整个结构还是链表，并不算是被模拟的（但是可以说成是用数组实现的链表）。

[编辑] 基本操作

[编辑] 插入

 
单链表的插入可以总结为两种:
1:无序的插入。
2:有序的插入。
 
@1:无序的插入只要把新的结点的地址赋给头指针即可 代码:
 
//*****************************
Node *new_data;
 
cin>>new_data->data;
 
new_data->next = Head;
Head = new_data;
//*****************************
 
@2:有序的插入要分为很多种情况(数据的降序)
1)数据降序排序的话,如果新数据最大则如同@1。
2)如果新数据在中间的话,先用while循环，然后插入即可。
3)如果最小则尾随于最后。

[编辑] 删除

//----//

 
 
#include <iostream>
using namespace std;
 
struct	Node
{
	int no;
	int data;				//存储数据
	Node *next;				//指向下一组数据
};
 
class	Create
{
	public:
		Create(Node *HEAD = NULL);
		void create();			//创建链表
		void display() const;		//显示链表中的数据
		void Delete();			//删除结点
		void search() const;		//搜索结点
	//
	private:
		Node *Head;			//存储头指针
};
 
Create::Create(Node *HEAD) : Head(HEAD)
{}
 
void Create::create()
{
	Node *head = NULL;
	Node *tail = NULL;
	int value_data  = 100;
	int value_no	= 100;
 
	cout<<"\nEnter the no data and end by Enter 0:\nno data\n";
	cin>>value_no;
 
	while (value_no != 0)
	{
		head	 = new Node;		//栈上申请内存
 
		head->no = value_no;
		cin>>head->data;
 
		if (Head == NULL)		//判断头指针是否为空
		{
			Head		= head;
			Head->next	= NULL;
			tail		= head;	//新结点至尾
		}
		else
		{
			tail->next	= head;
			head->next	= NULL;
			tail		= head;	//新结点至尾
		}
 
		cin>>value_no;
	}
 
}
 
void Create::Delete()
{
	int search_no	= 0;
	Node *Te	= Head;
	Node *front_data= NULL;
 
	cout<<"Enter the no you want to delete:";
	cin>>search_no;
 
	if (Head->no == search_no)
	{
		Head = Head->next;
		delete Te;
	}
	else
	{
		while (Te)
		{
			if (Te->no == search_no)
			{
				break;
			}
			front_data = Te;
			Te = Te->next;
		}
 
		if (Te == NULL)
		{
			cout<<"No data!";
		}
		else
		{
			//if ()			
			front_data->next = Te->next;
			delete Te;
		}
	}
}
 
void Create::display() const
{
	Node *Te = Head;
 
	cout<<"\nno	data:\n";
	while (Te)
	{
		cout<<Te->no;
		cout<<'\t'<<Te->data;
		cout<<endl;
		Te = Te->next;
	}
	cout<<endl;
 
}
//
 
int main()
{
	Create instance;
 
	instance.create();
	instance.display();
	instance.Delete();
	instance.display();
 
	return 0;
}

[编辑] 查找

 
/*--------------------------------------------------
 
		Node.cpp
 
--------------------------------------------------*/
 
#include <iostream>
 
using namespace std;
 
struct	Node
{
	int no;
	int data;				//存储数据
	Node *next;				//指向下一组数据
};
 
class	Create
{
	public:
		Create(Node *HEAD = NULL);
		void create();			//创建链表
		void display() const;		//显示链表中的数据
		void Delete();			//删除结点
		void search() const;		//搜索结点
	//
	private:
		Node *Head;			//存储头指针
};
 
Create::Create(Node *HEAD) : Head(HEAD)
{
}
 
void Create::create()
{
	Node *head = NULL;
	Node *tail = NULL;
	int value_data  = 100;
	int value_no	= 100;
 
	cout<<"\nEnter the no data and end by Enter 0:\nno data\n";
	cin>>value_no;
 
	while (value_no != 0)
	{
		head	 = new Node;		//栈上申请内存
 
		head->no = value_no;
		cin>>head->data;
 
		if (Head == NULL)		//判断头指针是否为空
		{
			Head		= head;
			Head->next	= NULL;
		}
		else
		{
			tail->next	= head;
			head->next	= NULL;
		}
		tail = head;			// 新节点至尾
		cin>>value_no;
	}
 
}
 
void Create::Delete()
{
	int search_no	= 0;
	Node *Te	= Head;
	Node *front_data= NULL;
 
	cout<<"Enter the no you want to delete:";
	cin>>search_no;
 
	if (Head->no == search_no)
	{
		Head = Head->next;
		delete Te;
	}
	else
	{
		while (Te)
		{
			if (Te->no == search_no)
			{
				break;
			}
			front_data = Te;
			Te = Te->next;
		}
 
		if (Te == NULL)
		{
			cout<<"No data!";
		}
		else
		{
			front_data->next = Te->next;
			delete Te;
		}
	}
}
 
 
void Create::search() const
{
	int search_no	= 0;
	Node *Te	= Head;
 
	cout<<"Enter the no you want to search:";
	cin>>search_no;
 
	while (Te)
	{
		if (Te->no == search_no)
		{
			break;
		}
		Te = Te->next;
	}
 
	if (Te == NULL)
	{
		cout<<"No data!";
		return;
	}
	cout<<Te->no;
	cout<<'\t'<<Te->data;
	cout<<endl;
 
}
void Create::display() const
{
	Node *Te = Head;
 
	cout<<"\nno	data:\n";
	while (Te)
	{
		cout<<Te->no;
		cout<<'\t'<<Te->data;
		cout<<endl;
		Te = Te->next;
	}
	cout<<endl;
 
}
//
 
int main()
{
	Create instance;
 
	instance.create();
	instance.display();
	instance.search();
 
	return 0;
}

[编辑] 参考代码

单向链表: C++ Pascal
双向链表: C++ Pascal
单向循环链表: C++ Pascal

[编辑] 常见用途

[编辑] 评价

[编辑] 参见

[编辑] 其他数据结构

[编辑] 参考题目

链表是一个小作品，欢迎帮助扩充这个条目。

链表

目录