单向链表
单向循环链表
双向循环链表
链栈
链队列

动态链表

静态链表和动态链表的区别：

静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。
1、静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。
2、动态链表是用内存申请函数（malloc/new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。

一、静态链表
结构体中的成员可以是各种类型的指针变量，当一个结构体中有一个或多个成员的基类型是本结构体类型时，则称这种结构体为“引用自身的结构体”。如：


struct node
{
　　char ch;
    int num;
　　struct node *p;
};

struct node a;	//声明一个结构体变量

p是一个可以指向struct node类型变量的指针成员。因此，a.p = &a 是合法的表达式，由此构成的存储结构如下图所示：



参考程序如下所示：



/*****************************************************
Copyright (C) 2017-2018 All rights reserved.
File name    ： static_link.c
Version      ： v1.0       
Author       ： Zhengqijun
Date         ： 2017年10月10日 星期二 15时12分30秒
Description  ： 
Funcion List ： 
*****************************************************/

#include <stdio.h>

/* 静态链表 */
struct node
{
    int num;
    struct node *next;
};

int main()
{
    struct node stu[3];
    struct node *head, *p;

    stu[0].num = 10;		//对结点的num成员赋值
    stu[1].num = 20;
    stu[2].num = 30;

    head = &stu[0];		//头指针指向第1个结点stu[0]
    stu[0].next = &stu[1];	//将结点stu[1]的地址赋值给stu[0]结点的next成员
    stu[1].next = &stu[2];	//将结点stu[2]的地址赋值给stu[1]结点的next成员
    stu[2].next = NULL;		//stu[2]是最后一个结点，其next成员不存放任何结点的地址，置为NULL

    //遍历静态链表
    p = head;			//使p指针也指向第1个结点
    
    do{
        printf("%d\n", p->num);	//输出p所指向结点的数据
        p = p->next;		//然后让p指向下一个结点
    } while (p != NULL);	//直到p的next成员为NULL，即完成遍历

    return 0;
}

输出结果为：

root@ubuntu:~/2017/1010$ ./static_link 
10
20
30


二、动态链表
到目前为止，凡是遇到处理“批量”数据时，我们都是利用数组来存储。定义数组必须（显式的或隐含的）指明元素的个数，从而也就限定了一个数组中存放的数据量。在实际应用中，一个程序在每次运行时要处理的数据的数目通常并不确定。如果数组定义的小了，就没有足够的空间存放数据，定义大了又浪费存储空间。

对于这种情况，如果能在程序执行过程中，根据需要随时开辟存储空间，不需要时再随时释放，就能比较合理的使用存储空间。C 语言的动态存储分配提供了这种可能性。每次动态分配的存储单元，其地址不一定是连续的，而所需处理的批量数据往往是一个整体，各数据之间存在着接序关系。链表的每个节点中，除了要有存放数据本身的数据域外，至少还需要有一个指针域，用它来存放下一个节点元素的地址，以便通过这些指针把各节点连接起来。由于链表每个存储单元都由动态存储分配获得，故称这样的链表为“动态链表”。
参考程序如下所示：

/*****************************************************
Copyright (C) 2017-2018 All rights reserved.
File name    ： dynamic_link.c
Version      ： v1.0       
Author       ： Zhengqijun
Date         ： 2017年10月10日 星期二 15时31分59秒
Description  ： 
Funcion List ： 
*****************************************************/

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

/*所谓动态链表，是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。*/
struct Student
{
    int No;		//学号
    struct Student *next;
};

int main()
{
    struct Student *p1, *p2;
	struct Student *head, *p;

    int n = 0; //结点个数

    head = NULL;
    p1 = (struct Student *)malloc(sizeof(struct Student));
    printf("请输入第1个学号\n");
    scanf("%d", &p1->No);

    p2 = p1; //开始时，p1和p2均指向第1个结点
    while (p1->No != 0)
    {
        n++;
        if (n == 1)
        {
            head = p1;
        }
        else
        {
            p2->next = p1;
        }

        p2 = p1;//p2是最后一个结点
        printf("请输入学号，输入0终止：\n");
        p1 = (struct Student *)malloc(sizeof(struct Student));
        scanf("%d", &p1->No);
    };

    p2->next = NULL;//输入完毕后，p2->next为NULL

    //遍历动态链表
	p = head;
    printf("\n学号为：\n");

    while (p != NULL)
    {
        printf("%d\n", p->No);
        p = p->next;
    }

    return 0;
}

输出结果为：

root@ubuntu:~/2017/1010$ ./dynamic_link 
请输入第1个学号1请输入学号，输入0终止：2请输入学号，输入0终止：3请输入学号，输入0终止：4请输入学号，输入0终止：0学号为：1234


注意：动态链表中，每个节点没有自己的名字，只能靠指针维系节点之间的关系。一旦某个节点的指针“断开”，后续节点就再也无法找寻！

1. 静态链表和动态链表的区别：

（1）静态链表放在栈区

（2）动态链表放在堆区，堆区数据必须要手工开辟，手工释放

2. 单链表定义

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

struct LinkNode
{
	int num;  //数据域
	struct LinkNode * next;  //指针域
}

3. 静态链表的创建方法及使用

struct LinkNode node1 = {10, NULL};
struct LinkNode node2 = {20, NULL};
node1.next = &node2;  //建立结点之间的关系
struct LinkNode * pCurrent = &node1;
while(pCurrent != NULL)   //遍历链表
{
	printf("%d\n", pCurrent->num);  //打印结点中的数据
	pCurrent = pCurrent->next;
}

4. 动态链表的创建方法及使用

struct LinkNode * node1 = malloc(sizeof(struct LinkNode));
struct LinkNode * node2 = malloc(sizeof(struct LinkNode));
node1->next =node2;  //建立结点之间的关系
struct LinkNode * pCurrent = node1;
while(pCurrent != NULL)   //遍历链表
{
	printf("%d\n", pCurrent->num);  //打印结点中的数据
	pCurrent = pCurrent->next;
}
free(node1);
free(node2);

5. 常用约定：头结点不保存数据域，只保存指针域的一个空结点。

设定空头结点的好处：空头结点便于头插，头部插入数据方便，头结点永远不会变！



6. 动态链表的相关操作（函数）

（1）初始化链表，让用户拿到一个链表的头结点

struct LinkNode * initLinkList()
{
	//创建头结点
	struct LinkNode * pHeader = malloc(sizeof(struct LinkNode));
	if(pHeader != NULL)
	{
		return NULL;
	}
	pHeader->next = NULL;  //初始化头结点
	
	// 让用户初始化链表
	//专门用于维护当前链表中的尾节点，好处在于添加数据方便
	struct LinkNode * pTail = pHeader; //这句很重要！！！！
	int val = -1;
	while(1)
	{
		printf("请输入链表中的数据，-1代表输入结果\n");
		scanf("%d",&val);
		if(val == -1)
		{
			break;
		}
		//创建新结点	
		struct LinkNode * newNode = malloc(sizeof(struct LinkNode));
		newNode->num = val;
		newNode->next = NULL;
		
		//更改指针的指向
		pTail->next = newNode;  //相当于当前链表的最后一个结点的指针指向了当前新创建的结点
		pTail = newNode;//使pTail指向当先新建的结点。即永远指向最后一个结点
	}
	return pHeader;
}

（2）动态链表的遍历

void foreachList(struct LinkNode * pHeader)
{
	if(pHeader == NULL)
	{
		return;
	}
	struct LinkNode * pCurrent = pCurrent->next; 
	while(pCurrent != NULL)   //遍历链表
	{
		printf("%d\n", pCurrent->num);  //打印结点中的数据
		pCurrent = pCurrent->next;
	}
}

（3）动态链表插入结点

void insertList(struct LinkNode * pHeader, int oldVal, int newVal)
{
	//在oldVal后面插入newVal
	if(pHeader == NULL)
	{
		return;
	}
	//创建两个临时辅助指针
	struct LinkNode * pPrev = pHeader;
	struct LinkNode * pCurrent = pHeader->next;
	while(pCurrent != NULL) 
	{
		//用户传入的数据和遍历的链表中的数据一样
		if(pCurrent->num == oldVal)  //找到了
		{
			break;
		}
		//没找到,两个指针往后移
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
	//创建新结点
	struct LinkNode * newNode = malloc(sizeof(struct LinkNode));
	newNode->num = newVal;
	newNode->next = NULL;
	
	//更改指针的指向
	newNode->next = pCurrent;  
	pPrev->next = newNode;
}


（4）删除动态链表中一个结点

void deleteList(struct LinkNode * pHeader, int Val)
{
	if(pHeader == NULL)
	{
		return;
	}
	//创建两个临时辅助指针
	struct LinkNode * pPrev = pHeader;
	struct LinkNode * pCurrent = pHeader->next;
	while(pCurrent != NULL) 
	{
		//用户传入的数据和遍历的链表中的数据一样
		if(pCurrent->num == Val)  //找到了
		{
			break;
		}
		//没找到,两个辅助指针往后移
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
	//如果链表中没有用户传入的Val值，直接return
	if(pCurrent == NULL)
	{
		return;
	}
	
	//链表中有用户传入的Val值且已经找到，更改指针的指向
	pPrev->next = pCurrent->next;
	
	//删除结点并释放堆区数据
	free(pCurrent);  
	pCurrent = NULL;  //严谨的写法，防止野指针出现
}


（5）清空一个动态链表

注意：清空一个动态链表 是 把所有有数据的结点释放掉，还留着一个头结点，并没有将链表销毁掉，还可以从头插入数据。

void clearList(struct LinkNode * pHeader)
{
	if(pHeader == NULL)
	{
		return;
	}
	//创建1个临时辅助指针
	struct LinkNode * pCurrent = pHeader->next; //指向第一个有效数据的结点
	while(pCurrent != NULL) 
	{
		//先保存住下一个结点的位置
		struct LinkNode * nextNode = pCurrent->next;
		
		//删除当前结点并释放堆区数据
		free(pCurrent);  
		pCurrent = nextNode;
	}
	pHeader->next = NULL;
}

（6）销毁链表

注意：销毁链表 是 将链表销毁掉，头结点也没了。

void destroyList(struct LinkNode * pHeader)
{
if(pHeader == NULL)
	{
		return;
	}
	
	//先清空链表
	clearList(pHeader)；
	
	//将头结点也释放掉
	free(pHeader);  
	pHeader = NULL;
}

（7）翻转链表

void reverList(struct LinkNode * pHeader)
{
	if(pHeader == NULL)
	{
		return;
	}
	//创建三个临时辅助指针
	struct LinkNode * pPrev = NULL;
	struct LinkNode * pCurrent = pHeader->next;
	struct LinkNode * pNext = NULL;
	
	while(pCurrent != NULL) 
	{
		
		pNext = pCurrent->next;  //pNext存储当前结点的下一个结点
		pCurrent->next = pPrev;  
		
		//移动辅助指针
		pPrev =pCurrent;  //pPrev永远指向翻转后链表的第一个结点
		pCurrent = pNext; //pCurrent永远指向剩下没有翻转的链表的第一个结点
	}
	pHeader->next = pPrev;
}


 

动态链表

链表是一种物理上非连续、非顺序的存储结构，数据元素之间的顺序是通过每个元素的指针关联的。链表由一系列节点组成，每个节点一般至少会包含两部分信息：一部分是元素数据本身，另一部分是指向下一个元素地址的指针。链表分为单向链表和双向链表。



链表的存储结构

链表的每个节点包含两个部分，分别是数据(data)和指向下一个节点的指针(next). 





链表的操作

链表的操作有：创建、插入、删除、输出。

创建操作即使空间的分配，把头，尾指针及链表节点数等信息初始化。



1）插入操作

有三种情况：头插入、尾插入、中间插入。

头插入的操作：增加一个新的节点，然后把新增加的节点的指针指向原来头指针指向的元素，再把头指针指向新增的节点，如图所示： 



尾插入的操作：增加一个指针为空的节点，然后把原指针指向节点的指针指向新增加的节点，最后把尾指针指向新增加的节点，如图所示： 

 

中间插入元素：首先增加一个节点，然后把新增加的节点的指针指向插入位置的后一个位置的节点，把插入位置的前一个节点的指针只想新增加的节点。如图所示： 





2）删除操作

有三种情况：头删除、尾删除、中间删除。

删除头元素：把头指针指向下一个节点，然后将原头结点的指针置空。如图所示： 



删除尾元素：首先找到倒数第2个元素。然后把尾指针指向这个元素，接着把原倒数第2个元素的尾指针置空。如图所示： 

 

删除中间元素：首先把要删除的节点的之前一个节点的指针指向要删除的节点的下一个节点，接着把要删除的节点置空。如图所示： 





链表的特点

1）物理空间不连续，空间开销更大。物理空间不连续的优点是可以使用操作系统的动态内存管理，缺点是需要更多的存储空间去存储指针信息。 

2）在运行时可以动态添加。 

3）查找元素需要顺序查找。



链表的性能

（以单链表作为对象）

链表的插入：头插和尾插为直接插入，时间复杂度为O(I);中间插需要遍历，时间复杂度为O(L),L为插入下标。

链表的删除：头删的时间复杂度为O(1);中间删的时间复杂度为O(L);尾删的时间复杂度为O(N),N为链表的长度。

对于查询来说，时间复杂度是O(L).





静态链表

使用用数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。



静态链表的实现

静态链表的实现就是使用一段固定长度的数组，其中每个元素由两部分组成：一个是data,用于记录数据；一个是cur,用于记录指向下一个节点的位置。

一个元素的结构代码：



public class Element{
     private int data;
     private int cur;

     public int getData() {
        return data;
     }

     public void setData(int data) {
        this.data = data;
     }

     public int getCur() {
        return cur;
     }

     public void setCur(int cur) {
        this.cur = cur;
     }

}



创建静态链表

首先需要三个标记：头指针标记、尾指针标记和未使用链表的头指针标记。

未使用链表的头指针标记的作用？因为我们需要把未使用的空间通过一个链表串起来，这样在需要分配空间时，可以直接把未使用链表的头指针指向的元素给我们真正使用的链表。如图所示： 

 

这个未使用的链表一般叫做备用链表，用于串起那些没由被使用的数组元素，为在链表中插入的操作使用，而在链表中删除元素时，需要及时把要删除的元素加入备用链表的头部记录下来。

创建静态链表的代码实现：



public StaticLinkedList(int capacity){
    elements = new Element[capacity];
    unUsed = 0;
    for(int i = 0;i < capacity - 1;i++){
        elements[i] = new Element();
        elements[i].setCur(i+1);
    }
    elements[capacity - 1] = new Element();
    elements[capacity - 1].setCur(-1);

}

我们在此对除了最后一个元素外的所有元素进行循环赋值，对最后一个元素赋值为-1，表明没有下一个元素。



插入与删除：

假如静态链表S中存储着线性表（a，b，c，d，f，g，h，i），Maxsize=11。

插入：要在第四个元素后插入元素e，方法是：先在当前表尾加入一个元素e，即：S[9].data = e;然后修改第四个元素的游标域，将e插入到链表中，即：S[9].cur = S[4].cur; S[4].cur = 9

删除：删除第7个元素h，则先顺着游标链通过计数找到第7个元素存储位置6，删除的具体做法是令S[6].cur = S[7].cur。

学习完了，想要实践一下吗？链表的所有操作代码实现代码由于过长，想要了解的可以留言：）