数据结构之链表精讲,数据结构之链表golang
博客明星评选
写完前面的序列表，这就是链表。这里不得不提一下链表的优点。没办法，优秀的东西总是要比较的。今天的任务并不简单。我们有很多东西要学。而本，这也是我们找工作时必考的知识点。
在链表《漫画算法：小灰的算法之旅》这本书里，举了一个很有意思的例子。它把有序列表比作正规军，链表就是地下党，非常形象。有序列表的物理结构是数组，我们按顺序存储，而链表是随机存储的。有时候我们只能找到它的上级和下级，不能为它而跳，就像地下工作者一样。
由于数据结构的模块大部分是用C语言编写的，学习这个需要对结构、指针和内存管理有充分的了解。所以我们的C语言知识一定要扎实。
什么是链表？链表是物理存储结构中不连续、无序的存储结构。数据元素的逻辑顺序是通过链表中指针链接的顺序实现的。
下面是一个结构。
typedef int SLDataType//数据类型typedef structs listnode { sldatatypeval；struct SListNode * next//记录下一个节点的地址} SListNode
我们来看一个完整的单向链表。下面是我们要学习的知识点。
我们想知道为什么有一个链表，因为有一个顺序列表。为什么我们需要一个链表？这是因为序列表存在一些缺陷。
中间/头的插入和删除，时间复杂度为O(N)。容量扩展需要申请新空间、复制数据和释放旧空间。会有很多消耗。一般容量提升2倍，必然会造成一定的空间浪费。比如现在的容量是100，满了就增加到200。我们
又插入了5个数据，后面没有插入数据，浪费了95个数据空间。再来看扩容的缺陷。当我们使用realloc进行扩容时，如果后面增加的空间过大，就会出现==异地扩容==，导致不必要的消耗。
void test(){ int * P1=(int *)malloc(40)；printf(%p\n ，P1)；p1=(int*)realloc(p1，100000)；printf(%p\n ，P1)；免费(P1)；} int main(){ test()；返回0；}
分类链表也有一定的分类，但本质是一样的，可以分为八种。
是带头单向还是双向循环单链表。先说单向链表不占主导。大家先学基础会比较容易。
在C语言中，我们需要定义一个结构，其成员具有有效数据和下一个节点的地址。如上所述，这里我们主要使用链表方法。
为了通过打印来测试代码的正确性，我们先来看看如何打印单链表，然后帮我们验证代码的正确性。
我们定义一个cur来指向链表的头节点。如果我们一次都没有打印出来，就让cur=cur- next，这样我们就可以打印出整个链表了。
void slist print(slist node * pHead){ slist node * cur=pHead；而(cur！=NULL) { printf(%d -，cur-val)；cur=cur-next；} printf( NULL \ n )；}插入数据一般来说，单链表数据的插入分为头插入和尾插入。一般我们很少用其他的插入方法，不是说这些方法不能实现，而是没有太大的价值。
插件就是在链表前面插入另一个节点。有两种情况。
链表是空链表，插入的节点是头节点。链表是正常的，插入一个节点。
我们需要解释代码，并有以下问题。
为什么要传入二级指针？如果我们第一次插入头，需要改变头节点的地址，引入一级指针(头节点的地址)。改变的是参数为什么定义buys list node(x)；我们发现后面的尾部插入也需要创建一个节点，这样可以避免代码重复做一个轮子。我们单独拿出了slistnode * BuysListNode (sl数据类型x){ slist node * node=(slist node *)malloc(sizeof(slist node))；if(node==NULL){ printf( malloc fail！\ n’)；退出(-1)；} node-next=NULL；node-val=x；返回节点；} void SListPushFront(slist node * * pplist，sl datatype x){ assert(pplist)；slist node * node=buys list node(x)；//判断是否第一次插入if(* pplist==NULL){ * pplist=node；返回；} node-next=* pplist；* pplist=node}测试一下吧？稍后我们将讨论打印功能。
int main(){ slist node * pHead=NULL；slist print(pHead)；SListPushFront( pHead，3)；SListPushFront( pHead，2)；SListPushFront( pHead，1)；slist print(pHead)；返回0；}
尾塞说完了，再来说说尾塞。一般来说，尾塞比头塞多一点。我们一般在尾部插入数据，这样更符合我们的想法。
尾插入是将一个节点插入链表的尾节点。在完成尾部插入之前，我们需要首先找到尾部节点，以便插入它。
还使用了二级指针，因为当我们第一次插入数据时，我们需要改变头节点的位置。
void slist push back(slist node * * PP head，sl datatype x){ assert(PP head)；slist node * node=buys list node(x)；//第一次插入if(* PP head==null){ * PP head=node；返回；} SListNode * cur=* ppHeadwhile (cur- next！=NULL){ cur=cur-next；} cur-next=node；}删除数据插入数据已经完成，现在我们来看看如何删除数据。
头删除意味着删除第一个节点。在序列表中，我们可能要移动很多数据，但单链表是不必要的。你会发现它的优点。
void SListPopFront(slist node * * PP head){ assert(PP head)；if(* PP head==NULL){ printf( no node )；返回；} slist node * cur=(* PP head)-next；免费(* PP head)；* ppHead=cur}测试
int main(){ slist node * pHead=NULL；SListPushBack( pHead，1)；SListPushBack( pHead，2)；SListPushBack( pHead，3)；slist print(pHead)；SListPopFront(pHead)；slist print(pHead)；slist destory(pHead)；返回0；}
尾删除列表的尾删除和尾插入一样，需要找到最后一个节点，但是尾删除需要将倒数第二个节点的next设置为NULL，这是必须要做的。
void SListPopBack(slist node * * PP head){ assert(PP head)；if(* PP head==NULL){ printf( no node )；返回；} SListNode * cur=* ppHead//只有一个节点if(cur-next==NULL){ free(cur)；* ppHead=NULL返回；} slist node * cur next=cur-next；while (curNext- next！=NULL){ cur=cur next；cur next=cur next-next；}免费(cur next)；cur-next=NULL；}测试
int main(){ slist node * pHead=NULL；SListPushBack( pHead，1)；SListPushBack( pHead，2)；SListPushBack( pHead，3)；slist print(pHead)；SListPopBack(pHead)；slist print(pHead)；slist destory(pHead)；返回0；}
寻找数据，我们可以检查val的值在单链表中是否相同。如果相同，我们将返回该节点的地址。如果不是，我们将返回NULL。数据搜索在现实生活中起着重要的作用。
slist node * slist find(slist node * pHead，sl datatype key){ assert(pHead)；SListNode * cur=pHead而(cur！=NULL){ if(cur-val==key){ return cur；} cur=cur-next；}返回NULL}测试代码
int main(){ slist node * pHead=NULL；SListPushBack( pHead，1)；SListPushBack( pHead，2)；SListPushBack( pHead，3)；SListNode* ret=SListFind(pHead，2)；如果(ret！=NULL) { printf(%d ，ret-val)；} slist destory(pHead)；返回0；}
在pos位置之后的X前面插入单个链表。我们谈到了在查找数据时返回节点的地址，这是这样做的基础。但是我们要想一想，为什么不在pos前面插入数据呢？很简单。我们使用单一的链表。后面节点的地址很容易得到，但是如果要得到前面的地址，请慢慢玩。
void SListInsertAfter(slist node * pos，sl datatype x){ assert(pos)；slist node * cur=pos-next；slist node * node=buys list node(x)；pos- next=节点；node-next=cur；}测试
int main(){ slist node * pHead=NULL；SListPushBack( pHead，1)；SListPushBack( pHead，2)；SListPushBack( pHead，3)；slist print(pHead)；SListNode* ret=SListFind(pHead，2)；SListInsertAfter(ret，0)；slist print(pHead)；slist destory(pHead)；返回0；}
单链表中删除pos位置后的值我们刚才说了pos后插入，现在要说删除了。这些都很简单。
void slisterasafter(slist node * pos){ assert(pos)；slist node * cur=pos-next；//判断pos是否为尾节点if(cur==NULL){ return；} pos-next=cur-next；免费(cur)；}测试
int main(){ slist node * pHead=NULL；SListPushBack( pHead，1)；SListPushBack( pHead，2)；SListPushBack( pHead，3)；slist print(pHead)；SListNode* ret=SListFind(pHead，1)；slisterasafter(ret)；slist print(pHead)；slist destory(pHead)；返回0；}
有些破坏链表的人可能会疑惑，为什么我们最后还要破坏链表？我们节点的空间都是来自malloc，用完后要释放，否则会出现内存泄漏。也许你觉得这个内存不算什么，但是如果我们的链表太长，次数太多，服务器的内存就会一点一点变小。最后会被领导骂。
void slist destory(slist node * * PP head){ assert(PP head)；SListNode * cur=* ppHead而(cur！=NULL){ slist node * cur next=cur-next；免费(cur)；cur=curNext} * ppHead=NULL}双头循环链表，单链表。我们已经详细说过了，但是单链表还是有一定的缺陷。
当我们无法得到前一个节点的地址后缀时，需要遍历整个链表，时间复杂度为O(N)。这些都是问题。我，大家想想有没有链表来解决这些问题。我很高兴双向循环链表可以解决这些问题。我们这里的方法和上面的差不多，这里就不做动画了。不过，我会用文字详细描述。
带前沿的双向循环链表：最复杂的结构一般用来单独存储数据。实际上，中使用的链表数据结构既是前导的又是双向的。
循环链表。另外，虽然这个结构很复杂，但是会发现用代码实现的时候结构会带来很多好处，反而是实现
很简单。当我们的代码实现后，我们就知道了。
Typedef int LTDataType节点；typedef结构ListNode { LTDataType datastruct ListNode * nextstruct ListNode * prev} ListNode
在头节点上创建一个单链表。我们没有增加一个标兵。这里补充一下。
既然是双头循环链表，那么头节点也一定是循环的。
ListNode * list create(){ ListNode * cur=(ListNode *)malloc(sizeof(ListNode))；assert(cur)；cur-data=-1；cur-next=cur；cur-prev=cur；返回cur} int main(){ ListNode * pace setter=list create()；//标兵返回0；}
和以前一样，我们需要测试代码的正确性。先来说说打印的功能。
创建一个节点，指向下一个标兵并打印这个值。这个节点向后移动，直到节点的地址等于pace setter void list print(list node * plist){ assert(plist)；ListNode * cur=plist-next；而(cur！=plist) { printf(%d-，cur-data)；cur=cur-next；} printf( NULL \ n )；}插入元素头需要完成以下步骤，
创建一个新节点。新节点的下一个保存原始的头节点。原始头节点的prev保存新节点的标兵。下一步保存新节点的位置。新节点的prev保存标兵的void listpushfront(listnode * plist，lt datatype x){ listnode * node=(listnode *)malloc(sizeof(listnode))；断言(节点)；node-data=x；node-next=plist-next；node-next-prev=node；plist-next=node；node-prev=plist；}
尾部插入更简单。使用单链表时，需要一步一步寻找尾节点。这里不需要O(N)的时间复杂度。我们可以观察到，定标器位的prev是尾节点的地址。
创建一个节点，将一个节点指向尾节点，依次修改尾节点和标兵的对应值：void list Push Back(listnode * plist，lt datatype x){ listnode * node=(listnode *)malloc(sizeof(listnode))；断言(节点)；node-data=x；ListNode * tail=plist-prev；//尾节点的next指向节点tail-next=node；//节点的prev指向尾节点-prev=tail；//next of node指向标兵node-next=plist；//标兵的prev指向节点plist-prev=node；}
删除元素标题。记住头删除不是模型删除，而是有效节点删除。
取一个节点记录头节点，判断该头节点是否是与标兵位置相同的记录头节点的下一个节点，依次修改相应的值。void ListPopFront(list node * plist){ assert(plist)；ListNode * head=plist-next；if(head==plist){ return；} ListNode * head next=head-next；head-next=NULL；head-prev=NULL；免费(头)；plist-next=head next；head next-prev=plist；}删尾删尾很简单。我们可以一步找到最后一个尾节点，修改对应的next和prev，这里就不跟大家分享了。
void ListPopBack(list node * plist){ assert(plist)；ListNode * tail=plist-prev；if(tail==plist){ return；} tail-prev-next=plist；plist-prev=tail-prev；tail-next=NULL；tail-prev=NULL；自由(尾巴)；}
这里总结一下，应该对链表的理论有一定的了解，但这远远不够。我们需要一些练习来练习和锻炼我们的思维。在这里，我给大家列举几个简单的OJ问题。只有答案，没有解释。但是，这些都比较简单。让我们坐下来提高我们的能力。
简单链表练习集
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。