数组的上风，在于可以方便的遍历查找须要的数据。在查询数组指定位置（如查询数组中的第4个数据）的操作中，只须要进行1次操作即可，韶光繁芜度为O(1)。但是，这种韶光上的便利性，是由于数组在内存中占用了连续的空间，在进行类似的查找或者遍历时，实质是指针在内存中的定向偏移。然而，当须要对数组成员进行添加和删除的操作时，数组内完成这类操作的韶光繁芜度则变成了O(n)。
链表的特性，使其在某些操作上比数组更加高效。例如当进行插入和删除操作时，链表操作的韶光繁芜度仅为O(1)。其余，由于链表在内存中不是连续存储的，以是可以充分利用内存中的碎片空间。除此之外，链表还是很多算法的根本，最常见的哈希表便是基于链表来实现的。基于以上缘故原由，我们可以看到，链表在程序设计过程中是非常主要的。本文总结了我们在学习链表的过程中碰到的问题和体会。
接下来，我们将对链表进行先容，用C措辞分别实现：链表的初始化、创建、元素的插入和删除、链表的遍历、元素的查询、链表的删除、链表的逆序以及判断链表是否有环等这些常用操作。并附上在Visual Studio 2010 中可以运行的代码供学习者参考。
说到链表，可能有些人还对其观点不是很理解。我们可以将一条链表想象成环环相扣的结点，就如平常所见到的锁链一样。链表内包含很多结点（当然也可以包含零个结点）。个中每个结点的数据空间一样平常会包含一个数据构造（用于存放各种类型的数据）以及一个指针，该指针一样平常称为next，用来指向下一个结点的位置。由于下一个结点也是链表类型，以是next的指针也要定义为链表类型。例如以下语句即定义了链表的构造类型。
typedef struct LinkList
{
int Element;
LinkList next;
}LinkList;
链表初始化
在对链表进行操作之前，须要先新建一个链表。此处讲解一种常见的场景下新建链表：在任何输入都没有的情形下对链表进行初始化。
链表初始化的浸染便是天生一个链表的头指针，以便后续的函数调用操作。在没有任何输入的情形下，我们首先须要定义一个头指针用来保存即将创建的链表。以是函数实现过程中须要在函数内定义并且申请一个结点的空间，并且在函数的结尾将这个结点作为新建链表的头指针返回给主调函数。本文给出的例程是天生一个头结点的指针，详细的代码实现如下：
linklist List_init()
{undefined
linklist HeadNode= (linklist)malloc(sizeof(linklist));
if(HeadNode == NULL)
{undefined
printf("空间缓存不敷");
return HeadNode;
}
HeadNode->Element= 0;
HeadNode->next= NULL;
returnHeadNode;
}
当然,初始化的过程或者方法不但这一种，个中也包含头指针存在的情形下对链表进行初始化，此处不再逐一罗列。
这里引申一下，此处例程中返回的链表指针为该链表的头结点，相对应的还有一个头指针的观点。头指针内只有指针的元素，并没有数据元素，但头结点除了指针还有数据。
头指针便是链表的名字，仅仅是个指针而已。头结点是为了操作的统一与方便而设立的，放在第一个有效元素结点（首元结点）之前，其数据域一样平常无意义（当然有些情形下也可存放链表的长度、用做监视哨等等）。一样平常情形下见到的链表的指针多为头指针，但最近在一个程序员编程网站leetcode中创造，题目中所给的链表一样平常是首元结点作为第一个元素，而不是头指针。
下图为头指针与头结点以及首元结点的关系。
链表创建
创建链表须要将既天命据按照链表的构造进行存储，本文以一种最大略的办法来演示：利用数组对链表赋值。将原来在连续空间存放的数组数据，放置在不连续的链表空间中，利用指针进行链接。
链表创建的步骤一样平常利用给定的头指针以及须要初始化的数据序列作为输入参数，本文利用数组作为输入数据序列。不才面的例程中，先将首元结点利用数组第一个元素初始化，再在首元结点之后创建新的链表结点赋值数组内余下的数据。详细实现如下：
void CreatList(linklist HeadNode,int InData,int DataNum)
{undefined
int i = 0;
linklist CurrentNode = (linklist) HeadNode;
for(i = 0;i<DataNum;i++)
{undefined
CurrentNode->Element = InData[i];
if(i< DataNum-1)// 由于每次赋值后须要新建结点，为了担保没有多余的废结点
{undefined
CurrentNode->next =(linklist )malloc(sizeof(linklist));
CurrentNode= CurrentNode->next;
}
}
CurrentNode->next= NULL;
}
程序内先新建了一个指针变量CurrentNode用来表示当前的结点指针。最初，我们让CurrentNode指向了首元结点HeadNode的位置。然后根据输入数组的大小进行循环赋值，赋值完成之后再重新申请一个结点空间用来存放下一个结点的内容，并且将当前结点指针CurrentNode指向新天生的结点。由于链表创建函数调用时已经存在一个首元结点，按照这个逻辑终极在利用末了一个数组数据赋值之后还会多天生一个结点。因此，为了担保没有冗余的结点，循环内须要用DataNum-1来掌握结点数量。
其余，C措辞的初学者须要把稳：无论被调子函数内含在几个参数，虽然子函数内的形参利用的是主函数内实参的指针，但在子函数内是不会改变主函数里实参的地址的。也便是说，只要子函数不返回指针，子函数的内容就不会影响主函数内的参数指针。正如程序中CurrentNode的指针最初是主函数内的头指针通报进来的，虽然创建链表的函数内CurrentNode的指针一贯在今后移动，但并不会改变主调函数内的首元结点的指针。本文链表的学习过程中会大量利用指针，建议各位学习者在打牢根本后再进行学习。
插入链表结点
链表创建完之后，下面我们将先容如何向链表内插入结点。一样平常添加结点可以分为两类：一类是在链表尾部插入；另一类为在中间插入。
链表结尾添加结点的步骤便是新建一个链表结点，将其链接到当前链表尾指针。
在中间结点插入结点的步骤轻微繁芜一些，个中也包含两种情形，分别是在指定结点前插入和指定结点后插入。其操作事理一样，本文只对指定位置后插入结点进行先容。指定结点前插入结点留给大家考试测验。
假设一个链表内存在几个几点A1，A2,A3,A4….，当根据哀求须要在指定位置之后（比如A2结点）插入一个新结点时。首先我们须要新建立一个结点NodeToInsert，然后将新结点的next指向A3，并且将A2的next指针指向新建立的结点NodeToInsert，牢记操作顺序不要改变。如果操作顺序变换一下，先将A2的next指向了新建立的结点，那么我们就丢失了A3的寻址办法。因此，在将A2的next指向其他任何地方之前，请务必将A3的地址存在NodeToInsert或者某个新建节点内。
插入结点的详细操作如下：
bool InsertList(linklist HeadNode,int LocateIndex,int InData)
{undefined
int i=1;// 由于起始结点HeadNode是头结点，以是计数从1开始
linklist CurrentNode= (linklist ) HeadNode;
//将CurrentNode指向待插入位置的前一个结点（index -1）
while(CurrentNode&& i<LocateIndex-1)
{undefined
CurrentNode= CurrentNode->next;
i++;
}
linklist NodeToInsert=(linklist)malloc(sizeof(linklist));
if(NodeToInsert == NULL)
{undefined
printf("空间缓存不敷");
return ERROR;
}
NodeToInsert->Element= InData;
NodeToInsert->next = CurrentNode->next;
CurrentNode->next = NodeToInsert;
return OK;
}
删除链表结点
对应于插入链表结点，链表的基本操作中同样也有删除链表结点。删除结点包括删除指定位置的结点和指定元素的结点。其基本事理都是先锁定待删除的结点的位置，然后将该结点的后置结点链接到前置结点的next指针处。这样中间这个结点即我们要删除的结点就从原来的链表中分开开来。相对付原来的链表，即删除了该结点。
bool DeleteList(linklist HeadNode,int index, int DataToDel)
{undefined
int i = 1;
linklist CurrentNode = HeadNode;
linklist NodeToDelete;
//将CurrentNode指向待删除位置的前一个结点（index -1）
while(CurrentNode&& i<index-1)
{undefined
CurrentNode= CurrentNode->next;
i++;
}
NodeToDelete = CurrentNode->next;
DataToDel =NodeToDelete->Element;
CurrentNode->next= NodeToDelete->next;
free(NodeToDelete);
return OK;
}
此处为什么还要重新建立一个指针来记录或者保存待删除的结点呢？明明一个大略的步骤CurrentNode ->next = CurrentNode ->next->next;就可以将这个结点CurrentNode->next删除了，为什么要多此一举呢？
此处新建的链表类型的指针NodeToDelete是为了开释CurrentNode->next。直策应用CurrentNode ->next = CurrentNode ->next->next只是将该节点从链表中剔除，但是没有将其空间从内存中开释。而且,经由了CurrentNode ->next = CurrentNode ->next->next这个赋值语句之后，我们已经丢失了原来须要删除的结点的地址。以是，在删除之前新建了个结点用来保存待删除的结点地址，以便后面对内存空间的开释。
获取链表长度&链表遍历
获取链表的长度实际上和遍历链表具有相同的操作。遍历的过程将链表内的结点都访问了一边。获取链表长度的详细步骤是遍历链表之后能够记录并返回链表结点个数。
本文给出获取链表长的函数代码。
int GetListLength(linklist HeadNode)
{undefined
int ListLength = 0;
linklist CurrentNode= (linklist) HeadNode;
while(CurrentNode)// 当前指针不为空时可以计数累加
{undefined
ListLength++;
CurrentNode= CurrentNode->next; //指针移到下一结点
}
returnListLength;
}
在该函数中，涌现了CurrentNode = CurrentNode ->next的表示方法，这是将CurrentNode ->next这个结点的指针移动到了当前这个结点CurrentNode，下一次利用CurrentNode指针的时候CurrentNode实际已经指向了下一个结点CurrentNode ->next。以是这也是常说到的结点后移。
对付链表内的赋值操作我们总结出几种情形：
获取链表元素
接下来我们将“给定链表中的某一个位置，返回该位置的数据值”和“返回链表内某一个元素的位置”这两个问题放在一起先容。
这两种情形的思路都是须要遍历链表。在给定元素值的情形下，定义一个元素序号随着遍历的过程累加，遍历的过程校验链表的结点是否与给定的元素匹配，如果匹配则返回元素位置的序号；在给定位置的情形下就更大略一些，元素序号累加到对应位置，返回对应结点的元素即可。
本文只列出给定元素值的例子：
int LocateElement(linklist HeadNode,int DataToLocate)
{undefined
int LocateIndex = 1;
linklist CurrentNode= (linklist) HeadNode;
while(CurrentNode)
{undefined
if(CurrentNode->Element== DataToLocate)
{undefined
returnLocateIndex; //找到位置返回
}
CurrentNode= CurrentNode->next;
LocateIndex++;
}
return -1; //如果没有这个值，返回-1
}
本函数的逻辑是如果遍历链表之后能够找到与所给元素匹配的结点，则将该结点的位置返回。但如果没有匹配的结点的话，则返回一个-1，表示获取元素位置失落败。
链表置空
链表置空又可以称为销毁链表。同样是在遍历的条件下，一贯到链表结尾结束，所有遍历到的链表结点均开释掉空间，详细代码如下：
bool DestroyList(linklist HeadNode)
{undefined
linklist pNext;
linklist CurrentNode= (linklist) HeadNode;
while(CurrentNode)
{undefined
pNext = CurrentNode->next;
free(CurrentNode);
CurrentNode= pNext;
}
HeadNode->next = NULL;
return OK;
}
链表逆序
链表的逆序有很多种思路，本文先容一种将当前结点的下一结点一贯往头指针之后移动的思路。
假设当前有5个结点，head、a1、a2、a3、a4、a5，他们的头指针是head。我们的思路便是将a1作为当前元素一贯今后遍历，并且将a1后面的数据依次挪到head之后。
在第一次搬移的过程中，须要将a1的下一个元素a2放在head之后。如图所示，当前结点选定为a1，起一个变量名为current，当前结点的下一个结点为pNext，则a2便成了pNext = current->next。如果想要将pNext移到head之后，我们按照图中第1步先将a3连接到a1的后面，然后第2步再将head后面的整体链表放到要移动的a2的后面，也便是pNext->next= head->next，第3步将a2移到head之后。这三个步骤下来，我们的第一次反转事情就算完成了。此时的链表链表就变成了head、a2、a1、a3、a4、a5，如图所示：
如果上面移动的步骤不按图中进行会涌现什么情形呢？假设现在按照3-2-1的步骤来实现a2移动到head后面。当前辈行第三步之后，即head->next = pNext;这一步直接将a2挪到了head之后。然后我们接下来该当再将原来head后面的一串数据链接到刚刚移动到head后面的a2后面，此处由于head后面的数据已经被pNext更新了，此时head后面是a2结点，以是在实行第二步往后，链表就变成了无限循环的链表，而且循环的元素值是a2。
按照上图精确的顺序实现第一次反转往后，可以剖断当前的current指针是否已经是尾指针，如果不是就可以连续实行。第二次反转后链表就变成了head、a3、a2、a1、a4、a5。因此当把链表内的末了一个元素也移动到head之后时，链表逆序的事情就算完成了。
详细的代码实现如下。
linklist ListRotate(linklist HeadNode)
{undefined
linklist current,pNext,pPrev;
pPrev = (linklist)malloc(sizeof(linklist));
if(pPrev == NULL)
{undefined
printf("空间缓存不敷");
return ERROR;
}
pPrev->next = HeadNode;
current = HeadNode;
while(current->next)
{undefined
pNext = current->next;
current->next = pNext->next;
pNext->next = pPrev->next;
pPrev->next = pNext;
}
return pPrev->next;
}
链表判断是否有环
判断链表是否存在环的过程中，常日最先想到的方法便是从定义下手，有环的话就没有尾结点，也便是说不存在一个结点的next指针是null。通过这种思路可以对有环无环进行剖断，但须要剖断到何时呢？
当遍历了4000个结点都没有碰着null结点，难道就可以断定这便是一个有环的链表吗？如果它的第4001个结点便是尾结点呢？很多情形下，我们是不知道链表的长度的，以是我们很难确定须要剖断到哪一个结点才能确定链表是否为环形链表。因此我们须要借助快指针、慢指针的观点，这是目前用来判断链表内有环无环的最通用有效的方法。
假设有这样一种情形，有两辆车，一辆车每秒钟可以跑n米，其余一辆速率要快一些，每秒能跑2n米，这两辆车都匀速运行。如果在一个没有交叉点的跑道上，这时跑道上有一个终点，快车和慢车同时在起始点相遇出发之后，一贯到终点，快车和慢车的间隔只会越拉越大，等到快车到达终点的时候，两者之间的间隔差最大。假想一种情形，如果跑道的终点与起始点连接了起来，虽然说从慢车的角度看，快车在前方越来越远。但快车的角度看，慢车在后面越来越远，但在前面看的话确实越来越近。以是在一个环形的跑道上，快车究竟会有第二次与慢车相遇，此时恰好超车一圈。
函数的实行过程如下：
bool IsListLoop(linklist HeadNode)
{undefined
linklist pFast,pSlow;
pFast = pSlow = HeadNode;
while(pFast && pSlow)
{undefined
pSlow = pSlow->next;
if(pFast->next)
{undefined
pFast= pFast->next->next;
}
else
{undefined
pFast= pFast->next;
}
if(pFast == pSlow)
{undefined
returnTRUE;
}
}
return FALSE;
}
以上便是基本先容，如果以为对你有帮助的话可以点赞关注+收藏哦！
