[数据结构与算法]线性表——链表

链表

顺序表和链表都是线性表的一种。但链表与顺序表不同的是，他的物理上与逻辑上的机构并不一致。
顺序表的话，逻辑相邻，物理上也是相邻的。所以对于一整块连续的物理地址，当我们进行插入和删除操作的时候就会需要大量的移动元素。
而链表不需要使用地址连续的存储单元，即不需要满足物理与逻辑一致，通过"链"建立数据之间的逻辑关系，当进行插入或删除操作的时候，只需要修改指针即可。

单链表

线性表的链式存储为单链表，通过任意一组存储单元来存储数据。链表通过许多节点构成，节点除了放自身的数据还有存放下一个节点的地址来保证链表的逻辑关系。而链表一般只记录头节点。结构如下：

typedef struct node{
	int data;
	node *next;
}node;

typedef struct chainlist{
	node *head;
	int size;
}clist;

可以看到虽然链表解决了顺序表需要大量连续空间的问题，使其更灵活，但是也可以清楚的看到，每一个节点除了放置数据，还要多存放一个地址，那么这样的话一个数据元素所占据的空间就更大。

因为单链表的数据存放不再是连续的存储单元，所以其存储结构是非随机存取，不可以直接找到表中的某个特定节点，只能在每次寻找时从头遍历。

虚拟头节点

通常用头指针来标识一个单链表，当头指针为NULL时，则为空表。另外，为了简化操作，通常也会在链表第一个节点前加一个虚拟头节点。虚拟头不存放数据，或其存放数据是无意义的，但是他只想链表的第一个节点。

引入头节点的好处：

1. 因为头指针指向第一个节点，而其余节点由上一个节点指向，所以在操作上有了虚拟头节点使得整个链表变得一致
2. 无论链表是否为空，其头指针都指向虚拟头而非空指针，因此也空表和非空表的处理上也得到了统一

单链表实现

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	int data;
	node *next;
}node; 

typedef struct clist{
	node *head;
	int size;
}clist;
 

这是刚刚写好的代码先定义好链表和节点。以及头文件引用。

node *newNode(int val){
	node *n = (node *)malloc(sizeof(node));
	n->data = val;
	n->next = NULL;
	return n;
} 

写一个创建节点的方法，因为在我们插入数据的时候，根据数据要求申请地址，所以需要更方便的存储。

clist *initChainList(){
	clist *l = (clist *)malloc(sizeof(clist));
	l->head = newNode(-1);
	l->size = 0;
	return l;	 
}

void deleteChainList(clist *l){
	node *temp;
	temp = l->head;
	while(temp){
		node *t2 = temp->next;
		free(temp);
		temp = t2;
	}
	free(l);
}

然后就是创建初始化链表的方法以及删除链表的方法，同样为了避免内存泄漏在删除链表的同时要先释放每个节点的空间，因为在链表中只记录头指针，所以我们需要先进行遍历释放节点。最后再释放链表。

int insertElement(clist *l, int loc, int val){
	
	if(loc > l->size){
		return 0;
	}
	node *n = newNode(val);
	node *t = l->head;
	while(loc--){
		t = t->next;
	}
	n->next = t->next;
	t->next = n;
	l->size++;
	return 1;
} 

int deleteElement(clist *l, int loc){
	if(loc > l->size || loc <= 0){
		return 0;
	}
	node *t1 = l->head;
	while(--loc){
		t1 = t1->next;
	}
	node *t2 = t1->next;
	t1->next = t1->next->next;
	free(t2);
	l->size--;
	return 1;	
}

同顺序表一样我们需要两个操作链表的方法插入和删除，可以看到这里的插入删除操作要简单，只需要改变一下指针就好，但是在寻找时我们只能通过遍历的方式，这里就比顺序表麻烦。在这里同样也可以看到，我在插入的时候并不是选择头插法或尾插法,而是按照顺序表那样指定位置插入，可以做一个很好的比对。注意做完操作后对size也要进行相应的加减操作。

void showChainList(clist *l){
	node *t = l->head;
	while(t && t->next){
		node *t2 = t->next;
		printf("%d ", t2->data);
		t = t2;
	}
	printf("\n");

同样在最后的时候加上一个输出函数，方便我们检验实现效果。

int main(){
	
	clist *p = initChainList();

	
	int a,b,c;
	a = 0;
	while(a!=4){
		printf("输入您的操作指令:");
		scanf("%d %d",&a ,&b);
		if(a == 1){
			//InsertData
			scanf("%d", &c);
			insertElement(p, b, c);
			showChainList(p);
		}
		if(a == 2){
			deleteElement(p, b);
			//DeleteData
			showChainList(p);
		}
		if(a == 3){
			deleteChainList(p);
		}
	}
}

主程序代码和顺序表的差不多。看一下效果

当然我们也可以实现头插法或尾插法，或按序号和值查找节点等等一般线性表的操作。
以上就是单链表的全部内容。

双链表

在单链表中节点只可以指向后面的节点，那么在双链表里节点除了指向下一个节点，也可以指向前一个节点，我么把节点的前后节点分别称为前驱和后继。双链表的引入对于尾插和删除链表的最后一个元素的效率大大提高。双链表的定义如下：

//节点定义相同
struct chainlist{
	node *prior, *next;
	int data;
}

同单链表定义相同只是加了一个前驱指针。所以对操作来讲变化不大，只需要在上面代码的基础上加上前驱变化即可，这里不做演示。

循环链表

循环单链表

循环链表顾名思义就是链表会构成一个环，也就是说在链表最后一个节点的指向不再是NULL而是指向头节点，当首尾相连之后实际上就没有了头尾的概念，但是处于链表的特点我们需要经常遍历，所以我们的size的作用就显现出来了。但是在进行插入操作的时候因为环是没有首尾的所以插在任何地方的效果都是等价的。

循环双链表

同理就是在循环单链表的基础上在每个节点上加上指向前驱的指针

静态链表

静态链表借助数组来描述线性表的链式结构，与之前节点地址指针不同的是，指向下一个节点的是数组相对应的下标。同样也是需要先分配一块连续的内存空间

struct chainlist{
	int data;
	int next;
}

静态链表以next = -1 为结束标志，静态链表的插入删除与动态链表相同，只需要修改指针而不需要移动元素。但是使用起来并不方便，只适用不支持指针的高级语言，但又有该方面需求的场景。

顺序表和链表

因为链表的每个节点都有指针域，所以链表数据密度要小于顺序表