果果带你写链表，小学生看了都说好

摘要：明明我们在之前已经接触了数组，感到数组已经是万能的数据存储位置了。但是，如果我们如果一直在使用比较复杂的数据（也就是比较多的数据时），我们肯定会感到很反感，因为对于数组这种数据结构，在你自己使用之前，一定要对其大小进行一番定义，这样一来，它的存储空间在数据处理过程中显得极为不方便，因为谁也不想对将要处理的数据做一个空间的预算，这是我们每一个程序员都很忌讳的，并且还要让其空间足够大，这样才能满足我们的要求(但是如果分配的太多，难免会浪费内存)。
所以这就是为啥你要用链表，学链表。

链表是一种数据结构，它弥补了数组带来的诸多不便，让我们可以任意为一些数据进行空间的分配，根据需要进行内存单元的开辟。

提到链表就必须要提到一个比较重要的知识点就是指针，因为前后数据要有关联，必须要进行一系列的连接和指向处理，那么扮演这个角色的就是指针，并且，在现在的编程语言中，指针是任何东西都没有办法去替代的。

如果你不太理解指针，我强烈建议你看这一篇文章：手把手教你写单片机的指针。

当然学习链表前，你还要有结构体的基本概念和知识，为啥？因为链表就是通过指针连接的多个结构体。每一个结构体中有一个存放指针的成员变量，并且，这个成员的类型是该结构体类型。每一个链表，都有这个自己的结点，这些结点是结构体的变量，当然，他们也是结构体类型的变量。

如果你不太理解结构体，我强烈建议你看这一篇文章：手把手教你写单片机的结构体。

当你看完理解了指针和结构体，那么如果你想进步学习一下链表，然后再看这篇文章，你一定会有一种恍然大悟的感觉，你会发现，指针、结构体、链表也没有真难。

话不多说，开始：

一、链表

1、链表基础知识

我们假设有三个特务，ABC。A的下线是B，B的下线是C。换句话说，就是A有B的地址，B有C的地址。写成代码就是这样：

//注：:如果这个结构体你看不懂，回去补结构体的知识
typedef struct spy 
{
    
	char *name;
	struct spy *next;
}spy, *p_spy;

spy A = {
    "A", NULL};
spy B = {
    "B", NULL};
spy C = {
    "C", NULL};
spy D = {
    "D", NULL};

int main( void )
{
    
	p_spy pHead = NULL;//定义一个头结点，但是这个几点本身不存数据，为哨兵节点
	
	A.next = &B;//A的下线是B
	B.next = &C;//B的下线是C
	C.next = NULL;//C没有下线
	
	pHead = &A;	//让头节点指向第一个节点A
	while (pHead )
	{
    
		printf("%s\r\n", pHead ->name);
		pHead = pHead ->next;让第一项一直往后跑，遍历这个链表
	}//直到pHead 跑到链表的最后一项，最后一项的下一项为空，自然就退出了
	while (1);	
}

给大家画一个图

首先我们定义了三个结构体，ABC。在内存里面就必定有这三个结构体。再看看下面这句话，他会导致什么结果：A.next_addr=&B

记住上面这个图，结构体A里面的next_address，等于B的地址。那蓝色箭头是我画出来的，只是给我们形象的认识而已，结构体A里面保存有B的地址。链表的核心就是：

这个链表结构体里面有一个指针，这个指针，等于其他结构体的地址。

用人类形象化的话来说，就是结构体A里面的某一个指针，指向结构体B。

首先作为一个链表，肯定有头部呀，我们怎么来确定这个链表的头部？实际上我们用一个指针来表示链表头，代码如下:

typedef struct spy {
    
	char *name;
	struct spy *next;
}spy, *p_spy;
p_spy pHead = NULL;

看一下这段代码，我们定义了三个结构体，还有一个结构体指针。它们都是变量，在内存里面都有对应的空间。

在上面的图里面，在红色方框里，我们用那个指针来表示链表头，现在这个链表头，它的值它是空的，也就是说它里面保存的地址是空的：这是一个空链表。

我们怎么判断一个链表是空的呢？

if(pHead == NULL)
printf("it is empty list");

那么我们怎么往这个链表里面添加一个元素呢？我们先用一个图来表示，假设把结构体A放到列表里面去：

再看一下插入第一项非常简单，我让这个链表头直接等于结构体A的地址就可以了。我们用箭头来表示，让我们更加形象的去了解这个链表：

在这个图里面加了这个箭头，在代码里面可没有什么箭头，它只是pHead这个变量，它的值等于结构体A的地址。

2、链表的插入

现在再把一个结构体B放入链表。有两种方法，你是放在链表头部？还是放在链表尾部？
我们画出一个图：

链表里面只有元素A.我们可以在A的左边插入这个新的元素B，也可以在A的右边插入这个新的元素B。也就是说，我们可以在链表的头部插入新的节点，也可以在列表的尾部插入新的节点。在右边的图里面，上面这个就是把B插在链表的尾部，下面这个就是把B插在链表的头部。
怎么写代码呢？
我们先来看看，把B插在链表的头部：

void InsertNodeToHead(spy newNode）
{
    
	/*插到链表最前面*/
	newNode->next_addr = pHead;//新插入节点的下一个节点为空
	pHead = newNode; //头结点指向新插入的节点
}

画个图演示一下

在这个图里面，左边是代码，右边是结果。假设一开始的时候先插入结构体A，执行图中标号为2的代码的时候，就是：A.next_addr=pHead等于初始值NULL。执行上图中标号为3的代码的时候，就是：pHead=A的地址。结果在上图里面右边地方，在图里面也写出了标号2、标号3。标号2那里A的next.address等于NULL，标号3那里pHead等于结构体A的地址。

下面我们再来增加第2个元素B，我们在链表的头部插入元素B.

在这个图里面用蓝色的标号，把调用过程给标了出来。在左边是代码，看标号为4的代码，要用这个函数把元素B插入链表。怎么做呢？也分为两步：

• 第1步
  不是插到头部去吗？那我就让B指向头部

但头部等于A，也实际上就是B指向了A

也就说现在B指向了A，头部也指向了A。

• 第二步：
  让头部要指向B：

这就是一个完整的插入过程。
这个图还要补充一下，让结尾指向NULL

把链表，想成一个手拉着手的队伍，就容易理解了。刚才我们讲的是在链表的头部插入一个元素，那怎么在一个链表的尾部插入一个元素呢？

我们假设这个图里面它有好几个元素，我们在最后面一个元素的右边，再插入新元素

得到的结果如下图：

tmp假设是最后一个元素，B是新元素。

tmp->next.addr=&B;
B.next addr = NULL;

问题的关键在于，我怎么在原来的列表里面找出最后一个元素。

来看看这段代码，使用一个while循环：

void insertNodeToTail(p_spy newNode)
{
    
	p_spy  temp;//定义一个临时节点
	temp = head;//让头结点指向临时节点，现在temp就是整个链表的第一项
	while(temp)//在原来的列表里面找出最后一个元素
	{
    
		if (temp ->next == NULL)//找到了最后一个节点 temp就是最后一个节点
			break;
		else
			temp = temp ->next;//让第一项一直往后跑，遍历这个链表
	}
	temp ->next = newspy;//最后一个节点插入新节点
	newspy->next = NULL;//新节点的下一个节点为空，这样就将新节点插入最后了
}

图中红圈处，它的特征是什么：它的next.addr等于NULL。如果不是最后一项的话，我们就取出他有边的那一项：temp = temp -> next.addr。这句话可能有些同学理解起来困难，这里画个图解释一下：

插入尾部的代码

void InsertNodeToTail(p_spy newNode）
{
    
	p_spy  temp;//定义一个临时节点
	if(pHead == NULL)//如果链表为空
	{
    
		pHead = newNode;
		newNode->next = NULL;
	}
	else
	{
    
		temp= pHead ;//让头结点指向临时节点
		while (temp)
		{
    
			if (temp->next == NULL) //找到了最后一个节点 temp就是最后一个节点
				break;
			else
				temp= temp->next;
		}
		temp->next = newNode;//最后一个节点插入新节点
		newNode->next = NULL;//新节点的下一个节点为空，这样就将新节点插入最后了
	}
}

void InitInputDevices(void)
{
    
	PInputDevice pDev = g_ptInputDevices;//PInputDevice pDev = &g_tNetInputDevice

	while (pDev)
	{
    
		pDev->DeviceInit();
		pDev = pDev->pNext;//这句话可能理解起来有困难，要好好理解,看下面的解释
	}
}


/** PInputDevice pDev = &g_tNetInputDevice; 第一次循环开始 pDev = &g_tNetInputDevice; 因为g_tNetInputDevice节点是最后一次添加到这个链表的 pDev->DeviceInit(); <==>&g_tNetInputDevice->DeviceInit();执行的是设备g_tNetInputDevice的初始化函数 pDev = pDev->pNext; <==>右边：&g_tNetInputDevice->pNext 等于&g_tKeyDevice 左边：pDev 执行完这句话就是 pDev = &g_tKeyDevice 第一次循环完毕，此时 pDev = &g_tKeyDevice； 第二次循环因为 pDev！=NULL;所以还会进行第二次循环 pDev->DeviceInit(); <==>&g_tKeyDevice->DeviceInit();执行的是设备g_tKeyDevice的初始化函数 pDev = pDev->pNext; <==>右边：&g_tKeyDevice->pNext 等于NULL(因为只有两个设备，g_tKeyDevice就是最后一个添加的设备) 左边：pDev 执行完这句话就是 pDev = NULL; 第二次循环完毕，此时 pDev = NULL; 第二次循环因为 pDev！=NULL;所以就不满足while (pDev)，程序就不会再执行下去了。 */

3、链表的删除

在链表中，怎么删除一个元素?

再看这个图，在链表中我们要删除红色方框的这个节点

再想象一下，在一个手牵着手的队伍里面，有一个人要走了，是不是他前面那个人要跟后面那个人牵手？

所以我们要找出前面那个人和后面那个人。假设temp是前面那个人，后面那个人是谁？needDeleteNode->next，needDeleteNode表示要删除的节点。代码怎么写呢：temp->next = 后面的人 = needDeleteNode->next所以关键在于我们怎么找到前面的人：temp。这也比较简单，遍历链表：

void RemoveNode(p_spy needDeleteNode)
{
    
	p_spy temp;//定义一个临时的节点，用来遍历
	if (pHead == needDeleteNode)//如果被删除的节点正好是头结点指向的那一个节点
	{
    
		pHead = needDeleteNode->next;//直接让头节点指向被删除节点的下一个节点
		return;//返回
	}
	else
	{
    
		/* 找出NeedDeleteNode的上一个节点 */
		temp = pHead;//让头结点指向临时节点temp
		while(temp)
		{
    
			if (temp->next == needDeleteNode)//找到了，要删除的节点就是temp的下一个节点
				break;
			else
				temp= temp->next;//继续找
		}		
		if (temp)
		{
    
			temp->next = needDeleteNode-> next;//让被删除的上一个节点temp的下一个节点指向被删除节点的下一个节点，那么就把原来的要删除的节点给从链表中删除了。
		}
	}
}

也是一个循环，如果我的下一项就等于你的话，我就是你的前一个。找到之后，就执行这条指令：temp->next=后面的人=needDeleteNode->next。

4、链表的使用

现在明白链表的插入删除，那么我们怎么使用链表呢？就比如说在上一节课我们说过，班主任需要把每个学员的信息都给统计起来，用链表如何操作？怎么去把这些信息全都打印出来，从链表头去遍历链表即可：

void PrintList(void)
{
    
	p_spy temp;	//定义一个临时节点，用于遍历
	temp = pHead;//让头节点指向临时节点
	while (tmp)//循环遍历，直到temp==NULL(最后一个节点的下一个节点为NULL，退出循环)
	{
    
		printf("%s\r\n", tmp->name);
		tmp = tmp->next;
	}	
}

现在回到我们的视频，我们的视频里面也讲了链表的操作
我给大家画这个图：

/*------------------------1.链表和结点的定义----------------------------*/

/*结点结构体*/
typedef struct LIST_NODE {
    
	int data;                        /*用于存放结点数据*/
	struct LIST_NODE *pxNext;        /*用于指向下一个结点*/
	struct LIST_NODE *pxPrevious;    /*用于指向上一个结点*/
}ListNode;


/*链表结构体*/
typedef struct LIST {
    
	unsigned int NumberOfNodes;      /*用于记录链表结点数量*/
	ListNode RootNode;               /*用于作为循环链表的参考点*/
}List;

/*------------------------2.链表和结点的初始化---------------------------*/
/*结点初始化*/
void ListInitialiseItem(ListNode *pxListNode, int value)
{
      
	pxListNode->data = value;       /*结点数据赋值*/
}

/*链表初始化*/
void ListInitialise(List *pxList)
{
    
	pxList->RootNode.pxNext = &(pxList->RootNode);     /*由于此时链表中没有结点,第一个结点指向自己*/
	pxList->RootNode.pxPrevious = &(pxList->RootNode); /*由于此时链表中没有结点,第一个结点指向自己*/
	
	pxList->NumberOfNodes = 1;                         /*链表结点计数初始化为1,也就是只有一个根结点*/     
}

/*------------------------3.1结点插入链表---------------------------*/
void ListInsertEnd(List *pxList, ListNode *pxInsertListNode)
{
    
	ListNode *pxNextNode = &(pxList->RootNode);                /*插入结点的后结点*/
	ListNode *pxPreviosNode = pxList->RootNode.pxPrevious;     /*插入结点的前结点*/

	
    pxInsertListNode->pxNext = pxNextNode;                     /*插入结点指向后结点*/
	pxInsertListNode->pxPrevious = pxPreviosNode;              /*插入结点指向前结点*/ 
	
	pxPreviosNode->pxNext = pxInsertListNode;                  /*前结点指向插入结点*/   
    pxNextNode->pxPrevious = pxInsertListNode;                 /*后结点指向插入结点*/   

   (pxList->NumberOfNodes)++;                                  /*链表结点计数加1*/
}

/*------------------------3.2链表删除结点---------------------------*/
void ListRemove(List *pxList, ListNode *pxIListToRemove)
{
    
	ListNode *pxPreviosNode = pxIListToRemove->pxPrevious;     /*删除结点的前结点*/
	ListNode *pxNextNode = pxIListToRemove->pxNext;            /*删除结点的后结点*/
	
    pxNextNode->pxPrevious = pxPreviosNode;                    /*后结点指向前结点*/
    pxPreviosNode->pxNext = pxNextNode;                        /*前结点指向后结点*/

	(pxList->NumberOfNodes)--;                                 /*链表结点计数减1*/
}


int main(void)
{
    
	/*1.定义链表、结点*/
	List      list;         //定义链表
	ListNode  list_node1;   //定义结点1
	ListNode  list_node2;   //定义结点2

	/*2.初始化链表、结点*/
	ListInitialise(&list);
	
	ListInitialiseItem(&list_node1, 100);
	ListInitialiseItem(&list_node2, 200);
	
	/*3.插入链表*/
	ListInsertEnd(&list, &list_node1);
	ListInsertEnd(&list, &list_node2);
	
	/*4.删除结点*/
	ListRemove(&list, &list_node1);
	
	return 0;
}

首先我们定了一个结构体：List list。它是一个变量，在内存里面必定有对应的空间。初始化完这个链表之后，它的结果就像上面的图表示的那样。因为这个链表内部它有一个根节点，所以把它的节点个数设置为1。这个链表一开始的时候只有一个元素，它的下一个元素是它自己，它的上一个元素也是它自己。这是一个双向的循环链表，双向循环链表稍微复杂一点，但是再怎么复杂，它也就是使用两个单向链表组成的，这里就不展开说了。