链表
链表是由节点构成的，这个节点我们可以通过建立一个类来实现它。这个类我们通常选用内部类。
class TestLink{
	class Entry{
		int data;
		Entry next;
		public Entry() {
			next = null;
		}
		public Entry(int data) {
			this.data = data;
			next = null;
		}
	}
}

链表分为有头结点的链表和无头节点的链表，头结点不储存数据。本篇博客用的是头结点的链表。

注意链表要创建一个构造方法初始化头节点，否则会产生空指针异常
	Entry head;//成员变量
	public TestLink() {//构造函数
		head = new Entry();
	}

1.头插
	public void insertHead(int val) {
		Entry cur = new Entry(val);//插入的点
		cur.next = head.next;//把插入的点next指向head的下一个节点
		head.next=cur;//head的next指向插入的点
	}

2.尾插
遍历链表的时候要注意while（cur.next！=null）和while（cur!=null）的区别。

前者遍历完cur是链表尾元素，后者遍历完cur是null.
	public void insertTail(int val) {
		Entry goal = new Entry(val);//要插入的点
		Entry cur = head;//用来遍历链表
		while(cur.next!=null) {//当cur.next为null即cur已经在链表尾部，退出循环
			cur = cur.next;
		}
		cur.next=goal;//尾插

	}

3.获得链表长度
	public int getLength() {
		Entry cur = head;//用来遍历链表
		int count = 0;//计数器
		while(cur.next != null) {
			cur =cur.next;
			count++;
		}
		return count;
	}

4.任意位置插入
	public void insert(int val,int post) {
		Entry cur = head;//用来遍历链表
		if(post >= 0 && post <= this.getLength()) {//找到插入的位置前的的那一个节点
			for(int i=0;i<post;i++) {
				cur = cur.next;
			}
		}
		Entry entry = new Entry(val);
		 entry.next=cur.next;//插入
		 cur.next=entry;
	}

5.返回下标
public int valueOf(int val) {
		Entry cur = head.next;
		int count = 0;
		while(cur != null) {
			if(cur.val == val) {
				count++;
				return count;
			}
			count++;
			cur = cur.next;
		}
		return -1;
	}

6.删除指定元素
public void remove(int val) {
		int j = valueOf(val);
		if(j < 1) {
			return;	
		}
		Entry cur = head.next;
		Entry pr = head;
		for (int i = 1; i < j; i++) {
			cur = cur.next;
			pr =pr.next;
		}
		pr.next = cur.next;
		
	}


7.链表的逆置
	public Entry reverse(){
		Entry pre = null;//
		Entry newHead = null;//用来存放逆置后链表的头结点
		Entry cur = head;//用来遍历链表
		while(cur != null) {//当cur.next==null时即cur到尾部时再循环一次把cur变成头指针。
			Entry curNext = cur.next;
			if(curNext == null){
				newHead = cur;
			}
			cur.next = pre;
			pre = cur;
			cur = curNext;
		}
		return newHead;
	}

8.求倒数第k个元素
	public Entry getPost(int k) {
		if(head == null) {
			return -1;
		}
		Entry cur = head;//用来遍历链表
		if(k < 0 || k > this.getLength()) {//如果插入的位置小于零或大于链表长度返回null
			return null;
		}
		for(int i=0;i<this.getLength()-k+1;i++) {//找到倒数第k个位置
			cur =cur.next;
		}
		return cur;
		
	}

9.求两个链表是否相交
public boolean isCut(TestLink t1,TestLink t2) {
		TestLink.Entry head1 = t1.head;
		TestLink.Entry head2 = t2.head;
		int len1 = t1.getLength();
		int len2 = t2.getLength();
		int myLen = len1-len2;//两条链表的长度差
		if(myLen < 0) {//head1指向长链表表头
			head1 = t2.head;
			head2 = t1.head;
		}
		for(int i=0;i< myLen;i++) {//head1到在长链表上移动至和端链表对齐
			head1 = head1.next;
		}
		while(head1 != null && head2 !=null && head1 != head2) {//两个遍历节点同时向后移，如果到尾部结束循环或两个节点相交结束循环
			head1 = head1.next;
			head2 = head2.next;
		}
		if(head1 == head2) {//相交返回true
			return true;
		}
		return false;
	}

10.判断链表是否有环，并且求入口点和环长
public boolean judgeLoop() {
		Entry fast = head;//快节点
		Entry slow = head;//慢节点
		while(fast.next != null && fast.next.next != null) {//当快节点到尾部的时候循环结束，因为快节点每次要后移两格所以要加上fast.next.next不等于空的条件，否则会产生空指针异常
			fast = fast.next.next;
			slow = slow.next;
			if(fast == slow) {//相交返回true
				return true;
			}
		}
		return false;
	}

入口点
public int intoLoop(){
		 Entry fast = head;
		 Entry slow = head;
		 while(fast.next != null && fast.next.next != null){
			 fast = fast.next.next;
			 slow = slow.next;
			 if(fast == slow) {
				 break;
			 }
		 }
		 slow = head;
		 while(fast != slow){
			 fast = fast.next;
			 slow = slow.next;
		 }
		 return slow.data;
	 }

环长
当快慢节点第二次相遇时，慢节点从第一次到第二次相遇走的距离即环长。
public int getLoopLength() {
		Entry fast = head;
		Entry slow = head;
		boolean  tag = false;
		int length = 0;
		while(fast.next != null && fast.next.next != null) {
			fast = fast.next.next;
			slow = slow.next;
			if(fast == slow && tag == true) {
				break;
			}
			if(fast == slow && tag == false) {
				tag =true;
			}
			if(tag == true ) {
				length++;
			}
		}
		return length;
	}

11.合并两个链表
将两个递增链表合并成一个递增链表
public static Entry mergeLink(Link l1,Link l2) {

		Link.Entry p1 = l1.head.next;
		Link.Entry p2 = l2.head.next;
		Link.Entry newHead = null;
		if(p1.data<p2.data) {//确认头结点（值小的为头结点）
			newHead = l1.head;
		}else {
			newHead = l2.head;
		}
		Link.Entry tmpHead = newHead;//tmpHead相当于一个缝衣服的针将两个链表串起来
		while(p1 != null && p2 != null){
			if(p1.data < p2.data){
				tmpHead.next = p1;
				p1 = p1.next;
			}else{
				tmpHead.next = p2;
				p2 = p2.next;
			}
			tmpHead = tmpHead.next;
		}
		if(p1 != null){//如果p1链表没结束，就把p1后面的串上去
			tmpHead.next = p1;
		}
		if(p2 != null){//如果p2链表没结束，就把p2后面的串上去
			tmpHead.next = p2;
		}
		return newHead;
		
	}
	 

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

作为有强大功能的链表，对他的操作当然有许多，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。

初学链表，一般从单向链表开始

--->NULL
head

这是一个空链表。

 ---->[p1]---->[p2]...---->[pn]---->[NULL]
head   p1->next  p2->next   pn->next

有n个节点的链表。

创建链表

typedef struct student{
	int score;
	struct student *next;
} LinkList;

一般创建链表我们都用typedef  struct，因为这样定义结构体变量时，我们就可以直接可以用LinkList  *a;定义结构体类型变量了。

初始化一个链表，n为链表节点个数。

LinkList *creat(int n){
	LinkList *head, *node, *end;//定义头节点，普通节点，尾部节点；
	head = (LinkList*)malloc(sizeof(LinkList));//分配地址
	end = head;         //若是空链表则头尾节点一样
	for (int i = 0; i < n; i++) {
		node = (LinkList*)malloc(sizeof(LinkList));
		scanf("%d", &node->score);
		end->next = node;
		end = node;
	}
	end->next = NULL;//结束创建
	return head;
}

修改链表节点值

修改链表节点值很简单。下面是一个传入链表和要修改的节点，来修改值的函数。

void change(LinkList *list,int n) {//n为第n个节点
	LinkList *t = list;
	int i = 0;
	while (i < n && t != NULL) {
		t = t->next;
		i++;
	}
	if (t != NULL) {
		puts("输入要修改的值");
		scanf("%d", &t->score);
	}
	else {
		puts("节点不存在");
	}
}

删除链表节点



删除链表的元素也就是把前节点的指针域越过要删除的节点指向下下个节点。即：p->next = q->next;然后放出q节点的空间，即free(q);

void delet(LinkList *list, int n) {
	LinkList *t = list, *in;
	int i = 0;
	while (i < n && t != NULL) {
		in = t;
		t = t->next;
		i++;
	}
	if (t != NULL) {
		in->next = t->next;
		free(t);
	}
	else {
		puts("节点不存在");
	}
}

 

插入链表节点



我们可以看出来，插入节点就是用插入前节点的指针域链接上插入节点的数据域，再把插入节点的指针域链接上插入后节点的数据域。根据图，插入节点也就是：e->next = head->next;  head->next = e;

增加链表节点用到了两个结构体指针和一个int数据。

void insert(LinkList *list, int n) {
	LinkList *t = list, *in;
	int i = 0;
	while (i < n && t != NULL) {
		t = t->next;
		i++;
	}
	if (t != NULL) {
		in = (LinkList*)malloc(sizeof(LinkList));
		puts("输入要插入的值");
		scanf("%d", &in->score);
		in->next = t->next;//填充in节点的指针域，也就是说把in的指针域指向t的下一个节点
		t->next = in;//填充t节点的指针域，把t的指针域重新指向in
	}
	else {
		puts("节点不存在");
	}
}

输出链表

输出链表很简单，边遍历边输出就行了。

        while (h->next != NULL) {
		h = h->next;
		printf("%d  ", h->score);
	}

 

 

 

完整源码获取：

微信关注：嵌入式云IOT技术圈

发送"链表"即可获取。

为什么要学习链表？

链表主要有以下几大特性：

1、解决数组无法存储多种数据类型的问题。

2、解决数组中，元素个数无法改变的限制(C99的变长数组，C++也有变长数组可以实现)。

3、数组移动元素的过程中，要对元素进行大范围的移动，很耗时间，效率也不高。

先来感性的认识一下链表,我们先来认识下简单的链表:



从这幅图我们得出以下信息:

这个简单链表的构成：

头指针(Header)，若干个节点(节点包括了数据域和指针域)，最后一个节点要指向空。

实现原理：头指针指向链表的第一个节点，然后第一个节点中的指针指向下一个节点，然后依次指到最后一个节点，这样就构成了一条链表。

接下来看看链表的数据结构:

struct  list_node
{
	int data ; //数据域，用于存储数据
	struct list_node *next ; //指针，可以用来访问节点数据，也可以遍历，指向下一个节点
};


那么如何来创建一个链表的一个节点呢？

我们写个程序演示一下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  list_node
{
	int data ; 
	struct list_node *next ;
};

typedef struct list_node list_single ; 	

int main(void)
{
	list_single *node = NULL ;          //1、首先，当然是定义一个头指针
	node = (list_single *)malloc(sizeof(list_single)); //2、然后分配内存空间
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single)); //3、清一下
	node->data = 100 ;		    		//4、给链表节点的数据赋值
	node->next = NULL ;                 //5、将链表的指针域指向空
	printf("%d\n",node->data);
	free(node);
	return 0 ;
}

那么，这仅仅只是创建一个链表中的一个节点，为了好看，我们把创建节点封装成函数，以后想创建多少个节点，我们就可以反复调用一个函数来创建，会很方便:

list_single *create_list_node(int data)
{
	list_single *node = NULL ;
	node = (list_single *)malloc(sizeof(list_single));
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single));
	node->data = 100 ;
	node->next = NULL ;
	return node ;
}

接下来在程序上完成的程序:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  list_node
{
	int data ; 
	struct list_node *next ;
};

typedef struct list_node list_single ; 	
list_single *create_list_node(int data)
{
	list_single *node = NULL ;
	node = (list_single *)malloc(sizeof(list_single));
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single));
	node->data = data;
	node->next = NULL ;
	return node ;
}
int main(void)
{
	int data = 100 ;
	list_single *node_ptr = create_list_node(data); //创建一个节点
	printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
	printf("node_ptr->next=%d\n",node_ptr->next);  
	free(node_ptr);
	return 0 ;
}

执行结果 ：




这样我们就完成一个链表节点的创建了，那么它现在的样子如下图：

链表的结构里，数据存储了100，因为这个链表只有一个节点，所以它的指针域指向了NULL。



   上面只是建立一个单链表的基本雏形，接下来咱们再来增加一点难度。如果创建多个单链表节点，实现单链表的增删改查？把单链表应用起来。

1、首先定义一个单链表的数据结构



创建节点函数原型可定义如下：

struct list *create_node(int data) ;

如何创建单链表的节点，主要分以下步骤:

(1)给当前的每个节点的数据结构配置定量的空间大小

   ep : struct list *node = malloc(sizeof(struct list));

(2)清节点数据(由于结构体变量在未初始化的时候，数据是脏的)

   ep : memset(node,0,sizeof(struct list));

(3)给节点初始化数据

   ep : node->id = data ; 

(4)将该节点的指针域设置为NULL

   ep : node->next = NULL ;

2、单链表的尾插：

尾插节点函数原型可定义如下：



如何将当前链表和新的节点相连接？只要实现：

header->next = new 

尾插流程如下：

(1)获取当前节点的位置，也就是访问头节点

   ep : struct list *p = header ;

(2)判断是否为最后一个节点，如果不是，移动到下一个节点，如果是，将数据插入尾部。

   ep : while(NULL != p->next) p = p->next ;

        p->next = new ;

3、单链表的头插



很好理解，头插就是把新的节点插在原来的节点和原来节点的下一个节点之间的一个节点。如图，新的节点插在头节点和节点1。

所以可以推出头插流程如下：

(1)获取当前节点的位置，也就是访问头节点

    ep : struct list *p = header ;

(2)新的节点的下一个节点设置为原来头节点的下一个节点(第一个节点)

    ep : new->next = p->next ;

(3)原来的头节点的下一个节点设置为现在新插入的头节点

    ep : p->next = new ;

4、单链表的遍历



如图为一条单向链表的模型，看图知道该链表由头节点和若干个节点组成，最后一个节点(尾节点)为NULL 。

从图中可以得出信息，如果我们要打印出各个节点的数据，要考虑以下问题：

(1)需要打印头节点吗？(头节点肯定是不用打印的，因为这是我们为了操作方便而设置的一个节点)。

(2)这条链表有多少个节点我们怎么知道？(通过判断该链表是否已经到达了尾节点，标志就是NULL)

那么可以得到流程如下：

(1)获取当前节点的位置，也就是访问头节点

    ep : struct list *p = header ;

(2)由于头节点我们不需要去打印它，这时候，初始化打印的节点需要从第一个节点开始。

    ep : p = p->next ;  

(3)判断是否为最后一个节点，如果不是，先打印第一个节点的数据(1)，然后移动到下一个节点(2),重复这两个步骤。

   如果是最后一个节点，直接打印数据即可。

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

    printf("node:%d\n",p->data);

    当然还可以一句代码解决，这样就达到了先偏移，后取数据。

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

 

5、单链表的删除

删除节点的函数原型可定义如下：

int detele_list_node(struct list *pH , int data);

单向链表的删除要考虑两种情况，一种的普通节点的删除(当然，头节点不能算)

还有一种是尾节点的前一个节点的删除情况，注意，删除完节点还需要释放对应节点的内存空间。




删除节点的设计流程：

(1)先定义两个指针，一个表示当前的节点，另一个表示当前节点的上一个节点。

    ep : struct list *p = header ;  //当前节点

         struct list *prev = NULL ; //当前节点的上一个节点

(2)遍历整个链表，同时保存当前节点的前一个节点

    ep : while(NULL != p->next)

        { 

          //保存了当前的节点的前一个节点

          prev = p ;  

          //保存当前偏移的节点

          p = p->next ; 

          return 0 ;

        }

(3)在遍历的过程中查找要删除的数据

    ep : while(NULL != p->next)

        { 

          //保存了当前的节点的前一个节点

          prev = p ;  

          //保存当前偏移的节点

          p = p->next ; 

          //查找到了数据

          if(p->id == data)

          {

          

          }

          return 0 ;

        }

(4)查找到了数据后，分两种情况删除

    ep : 普通节点的删除

        if(p->id == data)

        {

            prev->next = p->next ;

            free(p);

        }

    ep : 考虑尾节点的下一个节点为NULL的节点删除

        if(p->id == data)

        {

            if(p->next == NULL)

            {

                prev->next = NULL ;

                free(p);

            }

        }

6、单链表的逆序



逆序步骤：



单链表的基本操作流程咱们基本搞懂了，下面写一个程序，这将会变得非常非常的简单。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct slist
{
	int id ;
	struct slist *next ;			
}L;
 
//创建一个节点 
L *create_node(int data)
{
	//给每个节点分配结构体一样的空间大小 
	L *p = malloc(sizeof(L));
	if(NULL == p)
	{
		printf("malloc error!\n");
		return NULL ;
	}
	//由于结构体在未初始化的时候一样是脏数据，所以要清 
	memset(p,0,sizeof(L));
	//初始化第一个节点 
	p->id = data ; 
	//将节点的后继指针设置为NULL 
	p->next = NULL ;
}
 
//链表的尾插 
void tail_insert(L *pH , L *new)
{
	//获取当前的位置 
	L *p = pH ; 
	//如果当前位置的下一个节点不为空 
	while(NULL != p->next)
	{
		//移动到下一个节点 
		p = p->next ;
	}
	//如果跳出以上循环，所以已经到了NULL的这个位置
	//此时直接把新插入的节点赋值给NULL这个位置 
	p->next = new ;
}
 
//链表的头插 
void top_insert(L *pH , L *new)
{
	L *p = pH ;
	new->next = p->next ;
	p->next = new ;
}
 
//链表的遍历 
void Print_node(L *pH)
{
	//获取当前的位置 
	L *p = pH ;
	//获取第一个节点的位置 
	p = p->next ;
	//如果当前位置的下一个节点不为空 
	while(NULL != p->next)
	{
		//(1)打印节点的数据 
		printf("id:%d\n",p->id);
		//(2)移动到下一个节点,如果条件仍为真，则重复(1)，再(2) 
		p = p->next ;
	}
	//如果当前位置的下一个节点为空，则打印数据
	//说明只有一个节点 
	printf("id:%d\n",p->id);
}
 
//删除链表中的节点 
int detele_list_node(L * pH , int data)
{
	//获取当前头节点的位置 
	L *p = pH ;
	L *prev = NULL;
	while(NULL != p->next)
	{
		//保存当前节点的前一个节点的指针 
		prev = p ;
		//然后让当前的指针继续往后移动 
		p = p->next ; 	
		//判断，找到了要删除的数据  
		if(p->id == data)
		{
			//两种情况，一种是普通节点，还有一种是尾节点
			if(p->next != NULL)  //普通节点的情况 
			{
				prev->next = p->next ;
				free(p);
			}
			else //尾节点的情况 
			{
				prev->next = NULL ; //将这个尾节点的上一个节点的指针域指向空 
				free(p); 
			}
			return 0  ;
		}
	}
	printf("没有要删除的节点\n");
	return -1 ;
}
 
void trave_list(L * pH)
{
	//保存第一个节点的位置 
	L *p = pH->next;
	L *pBack;
	int i = 0 ;
	if(p->next == NULL || p == NULL)
		return ;
		
	while(NULL != p->next) //遍历链表 
	{
		//保存第一个节点的下一个节点 
		pBack = p->next ; 
		//找到第一个有效节点,其实就是头指针的下一个节点 
		if(p == pH->next) 
		{
			//第一个有效节点就是最后一个节点，所以要指向NULL 
			p->next = NULL ; 
		} 
		else
		{
			/*
			new->next = p->next ;
			p->next = new ;
			*/
			p->next = pH->next ; //尾部连接 
		}
		pH->next = p ; //头部连接 
		p = pBack ; //走下一个节点 
	}
	top_insert(pH,p); //插入最后一个节点 
}
 
int main(int argc , char **argv) 
{
	//创建第一个节点 
	int i ;
	L *header = create_node(0); 
	for(i = 1 ; i < 10 ; i++)
	{
		tail_insert(header,create_node(i));
	}
	Print_node(header);
	detele_list_node(header,5);
	putchar('\n');
	Print_node(header);
	putchar('\n');
	trave_list(header);
	Print_node(header);
	return 0 ;
}


运行结果：



当然，单链表存在一定的弊端，就是查找数据和删除数据的时候比较麻烦，而双链表的出现就是为了解决它的弊端：

双链表的引入是为了解决单链表的不足：

(1)双链表可以往前遍历，也可以往后遍历，具有两个方向

双链表的节点 = 有效数据 + 两个指针(分别指向前一个节点和后一个节点)

双向链表的图形结构描述:



struct double_list                                   struct double_list

{                                                            {

    数据域;                  ep :------->                   int data ;

    指针域(前向指针) ;                                   struct double_list *prev ;

    指针域(后向指针) ;                                   struct double_list *next ;

};                                                             };

 

1、双向链表的创建

struct list *create_node(int data) ;

创建步骤(与单链表类似，就是多了一个指针):

(1)给节点申请空间：

   ep : struct double_list *p = malloc(sizeof(struct double_list));

(2)初始化数据域

   ep : p->data = data ;

(3)初始化指针域

   ep : p->prev = NULL ; 

        p->next = NULL ;

2、双向链表的尾插

双向链表尾插节点的函数可以定义如下：

void double_list_tail_insert(struct double_list *header , struct double_list *new) ;

尾插图示操作：

尾插的步骤：



(1)找到链表的尾节点

   ep : 和单链表差不多

        DL *p = header ;

        while(NULL != p->next)

            p = p->next ;

(2)将新的节点连接到尾节点的后面成为新的节点

   1.原来的next指针指向新节点的首地址。            p->next = new ;

   2.新节点的prev指针指向原来的尾节点的首地址。 new->prev = p;

 

3、双向链表的头插

双向链表头插节点的函数可以定义如下：

void double_list_top_insert(struct double_list *header , struct double_list *new) ;




4、双向链表的遍历

4.1 正向遍历

    void double_list_for_each(DL *header)

    步骤：和单链表完全一致，没什么好写的。

    

    

4.2 反向遍历

    void double_list_for_each_nx(DL *header)

    步骤：(1)和单链表一样，先循环找到最后一个节点的地址

          (2)再依靠prev指针循环往前移动

             2.1 先打印最后一个数据  ep : printf("%d ",p->data);

             2.2 向前循环遍历         ep : p = p->prev ;

             

             判断条件：header->prev != p->prev,

             header保存的是头节点的地址,

             header->prev保存的是头节点的prev的地址,

             header->next保存的是头节点的next的地址,

             头节点在创建的时候:

             header->prev = NULL ;

             header->next = NULL ;

             所以这个条件这样写header->prev = NULL也是对的。

5、双向链表节点的删除



假设需要删除节点1：    

    首先:

    (1)获取当前节点的地址： 

        ep : p = header;

    (2)遍历所有的节点，找到要删除的节点：

        ep : 

        while(NULL != p->next)

        {

            p = p->next ;

            if(p->data == data)

            {

            

            }

        }

    (3)找到要删除的数据以后，需要做判断，判断两种情况，这和单链表差不多

    3.1 如果找到当前节点的下一个节点不为空

    3.1.1    

        那就把当前节点的prev节点指向要删除的这个节点的prev

        因为当前的prev节点保存的是要删除的上一个节点的指针 

        p->next->prev = p->prev ;

    3.1.2    

        然后将当前节点的prev指针(也就是上一个节点的指针)指向当前节点(要删除的)的下一个节点:

        p->prev->next = p->next ;

    3.1.3    

        最后释放删除指针的空间：

        free(p);

        

    3.2 如果找到当前节点的下一个节点为空

    3.2.1   

    直接把当前指针(要删除的节点)的prev指针(保存着当前指针的上一个节点的地址)的下一个next指针设置为空。

    p->prev->next = NULL ;

    3.2.2

    将删除的指针的空间释放:

    free(p);

    看来，双链表学起来比单链表容易多了！确实啊，多了一个方向，操作起来就更加容易了，但是多了一个方向，一维多了一个指针，相比增加了一定的复杂度，但是，只要牢记prev指针和next指针的指向，那么，手画一图，代码即可写出！

下面给一个案例实现一下双向链表：

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//创建一个双链表的数据结构
typedef struct __double_list
{
	int data ;
	struct __double_list *prev ;
	struct __double_list *next ;
}DL ; 
 
//创建双向链表并插入一个节点 
DL *create_dl_node(int data)
{
	DL *p = malloc(sizeof(DL));
	if(NULL == p)
	{
		printf("create dl node fair!\n");
		return NULL ;
	}
	//初始化数据 
	p->data = data ;
	//初始化指针 
	p->next = NULL ;
	p->prev = NULL ;
}
 
//双向链表的尾插 
void double_list_tail_insert(DL *header , DL *new)
{
	//取得当前节点的地址 
	DL *p = header ;
	//找到链表的尾节点 
	while(NULL != p->next)
	{
		//找不到接着找 
		p = p->next ;
	}
	//找到了尾节点，指向新节点的首地址 
	p->next = new ;
	//新节点的prev指针指向原来的尾节点的首地址。
	new->prev = p;
}
 
//双向链表的头插(也就是插在两个节点之间的插入方式)
void double_list_top_insert(DL *header , DL *new)
{
	//新节点的next指针指向原来的节点一的地址
	new->next = header->next ; 
	//判断当前节点的下一个节点的地址是否为空
	if(NULL != header->next) 
		header->next->prev = new ; //节点1的prev指针指向新节点的地址 
	header->next = new ;
	new->prev = header ;
}
 
//双向链表的正向遍历 
void double_list_for_each(DL *header)
{
	DL *p = header ;
	while(NULL != p->next)
	{
		p = p->next ;
		printf("%d ",p->data);
	}
}
 
//双向链表的反向遍历 
void double_list_for_each_nx(DL *header)
{
	DL *p = header ;
	//先找到尾节点
	while(NULL != p->next)
	{
		p = p->next ;	
	} 
	//已经找到了尾节点，向前遍历，注意，遍历到头节点之前
	//限制条件: != 头结点 
	while(NULL != p->prev)
	{
		printf("%d ",p->data);
		p = p->prev ;
	}
}
 
//双向链表节点的删除
int double_list_delete_node(DL *header , int data)
{
	//取得当前节点 
	DL *p = header;
	//遍历所有的节点 
	while(NULL != p->next)
	{
		p = p->next ;
		//找到了对应要删除的数据了 
		if(p->data == data)
		{
			//一样存在两种情况
			//(1)当前节点的下一个节点不为空
			if(p->next != NULL)
			{
				//那就把当前节点的prev节点指向要删除的这个节点的prev
				//因为当前的prev节点保存的是要删除的上一个节点的指针 
				p->next->prev = p->prev ;
				//还要指定它的next节点 
				p->prev->next = p->next ;
				free(p);
			}
			//(2)当前节点的下一个节点为空 
			else
			{
				//把 
				p->prev->next = NULL ;
				free(p); 
			}
			return 0 ;
		}
	}
	printf("\n没有找到对应要删除的节点，或者节点已经被删除！\n");
	return -1 ;	
} 
 
int main(void)
{
	int i ;
	DL *header = create_dl_node(0);
	for(i = 0 ; i < 10 ; i++)
	{
		//双向链表的尾插 
		//double_list_tail_insert(header,create_dl_node(i));
		//双向链表的头插 
		double_list_top_insert(header,create_dl_node(i));
	}
	//双向链表的正向遍历 
	printf("双向链表的正向遍历:");
	double_list_delete_node(header,5);
	double_list_for_each(header);
//	double_list_delete_node(header,9);
	double_list_delete_node(header,5);
	putchar('\n');
	printf("双向链表的反向遍历:");
	double_list_for_each_nx(header);
	return 0 ;
}


运行结果：

为什么要使用链表

在未学习链表时，我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快，但是它的弊端也很明显：


 使用前需声明数组的长度，一旦声明长度就不能更改
	
插入和删除操作需要移动大量的数组元素，效率慢
	
只能存储一种类型的数据.


而链表则可以实现以上这些数组所不具备的功能，此时引入了结构体来实现创建链表的操作。

链表的特点：


 n个节点离散分配
	
每一个节点之间通过指针相连
	
每一个节点有一个前驱节点和一个后继节点
	
首节点没有前驱节点，尾节点没有后继节点


首先先定义一个简单的结构体

struct link{
       int data;          //定义数据域
       struct link *next; //定义指针域，存储直接后继的节点信息
};

数据域的内容可以自己指定，指针域用来存放下一个节点的地址。

创建链表前须知

首节点：存放第一个有效数据的节点

头节点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点，头结点的数据域可以不存储任何信息，指针域指向第一个节点（首节点）的地址。头结点的作用是使所有链表（包括空表）的头指针非空

头指针：指向头节点的指针

尾节点：存放最后一个有效数据的节点

尾指针：指向尾节点的指针



建立一个单向链表

方法：定义方法向链表中添加节点来建立一个单向链表

思路：首先定义一个结构体指针变量p，使用malloc函数为新建节点申请内存空间，让p指向这个节点(指向它刚申请的内存空间），再将其添加到链表中。此时需考虑两种情况：

1.若单链表为空表，则将新建节点置为头节点



//若此时只在链表中插入头节点
struct link *p = head;
p = (struct link *)malloc(sizeof(struct link));  //让p指向新建节点创建的内存空间
if(p == NULL){   //新建节点申请内存失败
    exit(0);
}
//此时head也指向头节点的地址
p->next = NULL;     //因为没有后续节点，所以新建节点指针域置空

2.链表非空，则将新建节点添加到表尾



//此时已存在头节点,再插入一个节点（首节点）
struct link *p = NULL,*pr = head;  
p = (struct link *)malloc(sizeof(struct link));
if(p == NULL){
    exit(0);
}
if(head == NULL){
    head = p;
}else{
    while(pr->next != NULL){     //当头节点的指针域不为NULL
      pr = pr->next;             //pr指向下一个节点的地址
  }
    pr->next = p;                //使头节点的指针域存储下一个节点的地址
}

完整操作

#include <stdio.h>
#include <stdlib.h>
struct link *AppendNode(struct link *head);
void DisplayNode(struct link *head);
void DeleteMemory(struct link *head);
//定义结构体 
struct link{
	int data; 				//定义数据域 
	struct link *next; 			//定义指针域 
}; 
int main(){
	int i =0;         			//定义i，记录创建的节点数 
	char c;							
	struct link *head = NULL;		//创建头指针，初始化为NULL 
	printf("DO you wang to append a new node(Y or N)?");
	scanf(" %c",&c);				
	while(c == 'Y' || c == 'y'){	//如果确定继续添加结点 
		head = AppendNode(head);	//通过函数获得链表的地址，AppendNode函数返回的是链表的头指针
		                            //可以根据头指针指向的地址来获取链表中保存的数据 
		DisplayNode(head);			//根据头指针打印链表 
		printf("DO you want to append a new node(Y or N)?");
		scanf(" %c",&c);
		i++; 
	}
	printf("%d new nodes hava been appended!\n",i);
	DeleteMemory(head);			//释放占用的内存 
}
struct link *AppendNode(struct link *head){    //声明创建节点函数 
	struct link *p = NULL,*pr = head;      //创建p指针，初始化为NULL；创建pr指针，通过pr指针来给指针域赋值 
	int data ;
	p = (struct link *)malloc(sizeof(struct link)) ; //为指针p申请内存空间，必须操作，因为p是新创建的节点 
	if(p == NULL){			//如果申请内存失败，则退出程序 
		printf("NO enough momery to allocate!\n");
		exit(0);
	}
	if(head == NULL){		//如果头指针为NULL,说明现在链表是空表 
		head = p;								//使head指针指向p的地址(p已经通过malloc申请了内存，所以有地址） 
	}else{										//此时链表已经有头节点 ，再一次执行了AppendNode函数 
												//注：假如这是第二次添加节点
	                                  //因为第一次添加头节点时，pr = head，和头指针一样指向头节点的地址 
		while(pr->next!= NULL){		//当pr指向的地址，即此时的p的指针域不为NULL(即p不是尾节点) 
			pr = pr->next;	//使pr指向头节点的指针域
		}
		pr->next = p;	//使pr的指针域指向新键节点的地址，此时的next指针域是头节点的指针域 
	}
	printf("Input node data:");                   
	scanf("%d",&data);
	p->data = data; 			//给p的数据域赋值 
	p->next = NULL;			//新添加的节点位于表尾，所以它的指针域为NULL 
	return head;			//返回head的地址 
}
void DisplayNode(struct link *head){         	//输出函数，打印链表 
	struct link *p = head;			// 定义p指针使其指向头节点 
	int j = 1;									//定义j记录这是第几个数值 
	while(p != NULL){		//因为p = p->next,所以直到尾节点打印结束 
		printf("%5d%10d\n",j,p->data);			
		p = p->next;		//因为节点已经创建成功，所以p的指向由头节点指向下一个节点(每一个节点的指针域都指向了下一个节点) 
		j++;	
	}
}
void DeleteMemory(struct link *head){			//释放资源函数 
	struct link *p = head,*pr = NULL;	        //定义p指针指向头节点 
	while(p != NULL){				//当p的指针域不为NULL 
		pr = p;									//将每一个节点的地址赋值给pr指针 
		p = p->next;			        //使p指向下一个节点 
		free(pr);								//释放此时pr指向节点的内存 
	}
}



第二种创建链表方式-优化

#include <stdio.h> 
#include <stdlib.h>
struct Stu *create(int n);
void print(struct Stu *head);
struct Stu{
	int id;
	char name[50];
	struct Stu *next;
};
int main(){
	int n;
	struct Stu *head = NULL;   //创建头指针 
	printf("请输入你想要创建的节点个数：\n");
	scanf("%d",&n);
	head = create(n);
	print(head);
}
struct Stu *create(int n){
	struct Stu *head,*node,*end;   						//定义头节点，普通节点，尾节点 
	head = (struct Stu *)malloc(sizeof(struct Stu)); 	//给头节点申请内存 
	end = head;        									//若是空表，则头尾地址一致 
	for(int i=0;i<n;i++){								//利用for循环向链表中添加数据 
		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
		scanf("%d %s",&node->id,node->name);	//给数据域赋值 
		end->next = node;					//让上一个节点的数据域指向当前节点 
		end = node;     						//end指向当前节点，最终end指向尾节点 
	}
	end->next = NULL;                                   //给end的指针域置空 
	return head;                                        //返回头节点的地址 
}
void print(struct Stu *head){
	struct Stu *p = head;
	int j =1;
	p = p->next;  //不打印头节点的数据域中的值 
	while(p != NULL){
		printf("%d\t%d\t%s\n",j,p->id,p->name);
		p = p->next;
		j++;
	}
}



前插法创建链表 --逆序输出



struct link *create(int n){
     struct link *headnode ,*node;
     headnode = (struct link *)malloc(sizeof(struct link));   //为头节点申请内存 
	 headnode ->next = NULL;     //让头节点的指针域置空 
	 for(int i=0;i<n;i++){ 
	 	node = (struct link *)malloc(sizeof(struct link));  //给新建节点申请内存 
	 	scanf("%d",&node->data);       //新建节点数据域传值 
	 	node->next = headnode->next;   //新建节点的数据域指向头节点 == 创建尾节点 
	 	headnode->next = node;         //将新建节点数据域传给头节点 
	 }	
	 return headnode;  
}

 

删除节点



void deleteNode(struct Stu *head,int n){         //删除n处的节点 
	struct  Stu *p = head,*pr = head;
	int i =0;
	while(i<n&&p!=NULL){       //到达指定节点，此时p指向指定节点，pr指向上一节点 
		pr = p;            //将p的地址赋值给pr
		p = p->next;       //p指向下一节点
		i++;
	}
	if(p!=NULL){               //当p不为空时，即p不能指向尾节点之后的节点
		pr->next = p->next;
		free(p);
	} else{
		printf("节点不存在！\n"); 
	}
} 


我在这着重解释一下p->next = NULL和p!=NULL的区别，因为我刚开始也经常弄错！！

while(p->next ！= NULL) 循环结束时，此时p的位置是尾节点的位置，但如果用于输出函数的判断条件，则尾节点的数据不会输出。
	
while(p!=NULL) 循环结束时， 此时p指向的位置为尾节点的下一个节点，因为没有申请内存空间，所以是一个未知的区域。


插入节点



void insertNode(struct Stu *head,int n){    //插入节点 
	struct Stu *p = head,*pr;
	pr = (struct Stu*)malloc(sizeof(struct Stu));  //让pr指向新建节点申请的内存 
	printf("input data:\n");
	scanf("%d %s",&pr->id,pr->name);
	int i = 0;
    //当插入位置是尾节点时，只要在尾节点后再插入一个节点，并让尾节点的指针域指向新建节点，新建节点的指针域置空
    while(i<n&&p!=NULL){             //使p指向将要插入节点的位置 
    	p = p->next;
		i++;
	}
	if(p!=NULL){            //如果p没越界 
		pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 
		p->next = pr;       //使插入节点指向新建节点 
	}else{
		printf("节点不存在！\n");
	}
}

修改节点

void change(struct Stu *head,int n){
	struct Stu *p = head;
	int i = 0;
	while(i<n && p!=NULL){      //使p指向需修改节点 
		p = p->next;
		i++;
	}
	if(p != NULL){             
	printf("请输入修改之后的值:\n");
	scanf("%d %s",&p->id,p->name);	
	}else{
		printf("节点不存在！\n");
	} 

链表的逆序

 



思路：假如此时链表有两个有效节点，头节点为0号，中间的节点为1号，尾节点为2号

1.定义三个指针pf指向链表的头节点（0号），tmp，pb初始化为NULL

2.让pb指向pf的下一个节点（1号），并将此时头节点的指针域置空（变为尾节点）

3.第一次while循环，让tmp指向pb（1号），然后让pb指向下一个节点，再让tmp让1号节点的指针域（tmp->next = pf)指向pf(上一个节点）（0号），再将pf指向tmp（1号）(pf = tmp)

4.第二次while循环，让tmp指向pb（2号），然后让pb指向下一个节点，此时pb==NULL，所以这是最后一次循环，再让tmp让2号节点的指针域（tmp->next = pf)指向pf（1号），再将pf指向tmp（2号）

 5.此时链表逆序完成，让头指针指向首节点（2号），返回头指针即可

                                                                          逆序后



STU *link_reversed_order(STU *head)
{
    STU *pf = NULL, *pb = NULL, *tmp = NULL; 
    pf = head;  //将头节点的地址赋值给pf 
    if(head == NULL) { //如果链表为空 
        printf("链表为空，不需要逆序！\n");
        return head;
    } else if(head->next == NULL) {  //如果只有一个节点 
        printf("链表只有一个节点，不需要逆序！\n");
        return head;
    } else {
        pb = pf->next;  //pb指向pf的下一个节点 
        head->next = NULL; //头节点的指针域置空(变为尾节点) 
        while(pb != NULL)	//当pb不为空时 
        {
            tmp = pb;	//将pb的地址赋值给temp 
            pb = pb->next; //pb指向下一个节点 
            tmp->next = pf;	//pb的上一个节点的指针域指向pf 
            pf = tmp;	//让pf指向tmp 
        }
        head = pf;
        return head;
    }    
}*/

所有操作

#include <stdio.h> 
#include <stdlib.h>
struct Stu *create(int n);
void print(struct Stu *head);
void deleteNode(struct Stu *head,int n);
void insertNode(struct Stu *head,int n);
void change(struct Stu *head,int n);
struct Stu{
	int id;
	char name[50];
	struct Stu *next;
};
int main(){
	int n,j,in,cn;
	char c;
	struct Stu *head = NULL;   //创建头指针 
	printf("请输入你想要创建的节点个数：\n");
	scanf("%d",&n);
	head = create(n);
	print(head);
	while(true){
	printf("请选择你想要执行的操作：\n");
	printf("1.插入节点\n2.删除节点\n3.修改节点\n4.退出程序\n");
	scanf(" %c",&c);
	if(c =='1'){
	printf("你想要在哪插入节点：\n");
	scanf("%d",&in);
	insertNode(head,in);
	print(head); 
	}else if(c == '2'){
	printf("你想要删除哪个节点的数据：\n");
	scanf("%d",&j);
	deleteNode(head,j);
	print(head);
	}else if(c =='3'){
	printf("你想要修改哪个节点的数据：\n");
	scanf("%d",&cn);
	change(head,cn);
	print(head); 
	}else if(c =='4'){
		exit(0);
	} 		
 } 
}
struct Stu *create(int n){
	struct Stu *head,*node,*end;   						//定义头节点，普通节点，尾节点 
	head = (struct Stu *)malloc(sizeof(struct Stu)); 	//给头节点申请内存 
	//head->id = n;										//头节点的数据域保存链表的长度 
	end = head;        									//若是空表，则头尾地址一致 
	for(int i=0;i<n;i++){								//利用for循环向链表中添加数据 
		node = (struct Stu *)malloc(sizeof(struct Stu));//给普通节点申请内存空间 
		scanf("%d %s",&node->id,node->name);			//给数据域赋值 
		end->next = node;								//让上一个节点的数据域指向当前节点 
		end = node;     								//end指向当前节点，最终end指向尾节点 
	}
	end->next = NULL;                                   //给end的指针域置空 
	return head;                                        //返回头节点的地址 
}
void print(struct Stu *head){
	struct Stu *p = head;
	int j =1;
	p = p->next;  //不打印头节点的数据域中的值 
	while(p != NULL){
		printf("%d\t%d\t%s\n",j,p->id,p->name);
		p = p->next;
		j++;
	}
}
void deleteNode(struct Stu *head,int n){         //删除n处的节点 
	struct  Stu *p = head,*pr = head;
	int i =0;
	while(i<n&&p!=NULL){       //到达指定节点，此时p指向指定节点，pr指向上一节点 
		pr = p;
		p = p->next;
		i++;
	}
	if(p!=NULL){
		pr->next = p->next;
		free(p);
	} else{
		printf("节点不存在！\n"); 
	}
} 
void insertNode(struct Stu *head,int n){    //插入节点 
	struct Stu *p = head,*pr;
	pr = (struct Stu*)malloc(sizeof(struct Stu));  //让pr指向新建节点申请的内存 
	printf("input data:\n");
	scanf("%d %s",&pr->id,pr->name);
	int i = 0;
    //当插入位置是尾节点时，只要在尾节点后再插入一个节点，并让尾节点的指针域指向新建节点，新建节点的指针域置空
    while(i<n&&p!=NULL){             //使p指向将要插入节点的位置 
    	p = p->next;
		i++;
	}
	if(p!=NULL){            //如果p没越界 
		pr->next = p->next; //将新建节点的地址指向将要插入节点的后一个节点的地址 
		p->next = pr;       //使插入节点指向新建节点 
	}else{
		printf("节点不存在！\n");
	}
}
void change(struct Stu *head,int n){
	struct Stu *p = head;
	int i = 0;
	while(i<n && p!=NULL){      //使p指向需修改节点 
		p = p->next;
		i++;
	}
	if(p != NULL){             
	printf("请输入修改之后的值:\n");
	scanf("%d %s",&p->id,p->name);	
	}else{
		printf("节点不存在！\n");
	} 	 
}