数据结构_双向带头循环链表

2023-05-09 13:42:30 浏览数 (1)

数据结构_双向带头循环链表

前言：此类笔记仅用于个人复习，内容主要在于记录和体现个人理解，详细还请结合bite课件、录播、板书和代码。

[toc]

学了双向带头循环链表，你就能知道什么是来自结构上的优势

比起单向无头不循环链表的家徒四壁，需要自己打拼的当代打工人，双向循环带头链表就像是富二代，来自先天性的优势让它实现各种共功能都更加容易

双向带头循环链表的组成
  1. 哨兵位的头节点

哨兵位的头结点唯一且最重要的功能就是占位，作为带头链表的头部，它不存储有效数据，它之后的各个结点才开始存储有效数据 不带头的链表在没有数据的时候是没有结点的或者说头指针是空 双向带头循环链表无论有无数据，都一定有哨兵位头结点，因为就靠它来占位啦 也正是因为有哨兵位头结点占位， 由于哨兵位的位置是不变的，所有不用更改它的地址，只需要更改它的next和prev就可以，所以不需要传二级指针 无头链表则不同，由于没有哨兵位，因此一旦头部有所改变，就需要更改头指针的地址，确保头结点一直指向链表第一个结点，修改指针的地址，则必须要二级指针 （next、data等是结点的元素，而不是结点本身的地址，修改结点的元素用结点的地址（一级指针），而修改结点指针的地址则需要指针的地址（二级指针） 或者这样理解，next本身就是结点指针类型的数据，但是它是结点的元素，修改结点元素的话就需要传结点地址，这就相当于next这个结点指针的地址了；但总归用的是存储next的结点的一级指针

  1. 双向指针

prev指针，指向前一个结点 next指针，指向后一个结点 双向指针的优势： 可以找到前一个结点，再进行数据插入和删除的时候非常简便

  1. 循环

成环 两个结点以上的时候，哨兵位结点是头phead，最后一个结点是尾tail，tail->next又是phead，phead->prev是tail

成环的优势： 可以直接通过phead找到tail，或者反过来

双向带头循环链表的实现

typedef struct ListNode { LTDataType data; struct ListNode *next; struct ListNode *prev; }ListNode;因为哨兵位的data不需要存储有效数据，因此人拿它来存储链表结点的个数，只能说这种方法缺乏工程经验，因为当data数据类型是int的时候可以，但是当data存储的是char呢，是指针呢，还有意义吗？

增删查改功能的实现

//创建并返回结点 ListNode *BuyLTNode(LTDataType x); //链表初始化 void ListInit(ListNode *plist); //链表销毁 void ListDestory(ListNode *plist); //打印链表 void ListPrint(ListNode *plist); //尾删 void ListPopBack(ListNode *plist); //尾插 void ListPushBack(ListNode *plist, LTDataType x); //头删 void ListPopFrint(ListNode *list); //头插 void ListPushhFrint(ListNode *plist, LTDataType x); //查找(是配合下面两个指定位置的增删使用的) ListNode *ListFind(ListNode *plist, LTDataType x); //在指定位置（pos）前面插入数据 void ListInsert(ListNode *pos, LTDataType x); //删除指定位置的结点 void ListErase(ListNode *pos);

创建并返回一个新的链表结点 ListNode *BuyLTNode(LTDataType x) { ListNode *newnode=(ListNode *)malloc(sizeof(ListNode)); if(newnode == NULL) { printf("no mallocnn"); exit(-1); } else { newnode->next = NULL; newnode->prev = NULL; newnode->data = x; } return newnode; }初始化链表 void ListInit(ListNode *plist) { assert(plist); plist->next = plist; plist->prev = plist; plist->data = 0; }链表销毁（优化前） void ListDestory(ListNode *plist) { assert(plist); ListNode *node = plist->next; while(node != plist) { ListNode *next = node->next; free(node); node = next; } free(plist); plist = NULL; }打印链表 void ListPrint(ListNode *plist) { assert(plist); ListNode *node = plist->next; while(node != plist) { printf("%d ",node->data); node = node->next; } printf("n"); }尾删（优化前） void ListPopBack(ListNode *plist) { assert(plist); assert(plist->next != plist);//这里必须要断言，不然就会把plist free掉 ListNode *tail = plist->prev; plist->prev = tail->prev; tail->prev->next = plist; free(tail); tail = NULL; } 如果链表内就剩下了头结点，就不能再删除了，否则就出错了，因此assert一下，之后也是同理 尾插（优化前） void ListPushBack(ListNode *plist, LTDataType x) { assert(plist); ListNode *newnode=BuyLTNode(x); ListNode *tail=plist->prev;//这里创建一个用来记录原来的尾结点的记录指针，方便链接新的尾结点时使用 //没有node的话需要严格按照顺序链接，否则最后会找不到结点 newnode->next=plist; plist->prev=newnode; tail->next=newnode; newnode->prev=tail; }创建记录结点的指针非常实用，对于链表结点的链接来说非常方便，在下面继续进行体会 头删（优化前） void ListPopFrint(ListNode *plist) { assert(plist); assert(plist->next != plist); ListNode *head = plist->next; plist->next = head->next; head->next->prev = plist; free(head); head = NULL; }头插（优化前） void ListPushhFrint(ListNode *plist, LTDataType x) { assert(plist); ListNode *newnode = BuyLTNode(x); ListNode *head = plist->next; newnode->next = head; head->prev = newnode; newnode->prev = plist; plist->next = newnode; }查找 ListNode *ListFind(ListNode *plist, LTDataType x) { assert(plist); ListNode *node = plist->next; while(node != plist) { if(node->data == x) return node; node = node->next; } printf("no searchnn"); return NULL; }在pos点之前插入 void ListInsert(ListNode *pos, LTDataType x) { assert(pos); ListNode *posPrev = pos->prev;//创建记录pos的前位的结点，方便链接 ListNode *newnode = BuyLTNode(x); newnode->next = pos; newnode->prev = posPrev; posPrev->next = newnode; pos->prev = newnode; }删除pos点结点 void ListErase(ListNode *pos) { assert(pos); assert(pos != pos->next);//防止删除哨兵位 ListNode *posPrev = pos->prev;//创建记录pos的前后位的结点，方便链接 ListNode *posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); pos = NULL; }由于在pos点之前插入数据和删除pos点的数据的函数复用性很强，可以用它来简化头尾的增删以及销毁 尾删（优化后） void ListPopBack(ListNode *plist) { assert(plist); assert(plist->next != plist);//这里必须要断言，不然就会把plist free掉 ListErase(plist->next); } 尾插（优化后） void ListPushBack(ListNode *plist, LTDataType x) { assert(plist); ListInsert(plist, x);//这里要注意，因为pos插入的话实在pos的前一个位置插入，因此实现尾插的话应该再plist的前一个位置插入，插入之后就变成了新的尾，所以传入的pos就是plist }头删（优化后） void ListPopFrint(ListNode *plist) { assert(plist); assert(plist->next != plist); ListErase(plist->next); }头插（优化后） void ListPushhFrint(ListNode *plist, LTDataType x) { assert(plist); ListInsert(plist->next , x); }销毁（优化后） void ListDestory(ListNode *plist) { assert(plist); while(plist != plist-> next) { ListErase(plist->next); } free(plist); plist = NULL; }这个优化其实没什么必要，因为销毁的话没必要每次销毁一个结点还要把后面的链接起来，listearse会把后面的链接起来

链表和顺序表的区别

不同点顺序表链表存储空间上物理上一定连续逻辑上连续，但物理上不一定连续随机访问支持，O(1)不支持，O(N)任意位置插入或者删除元素可能需要搬动元素，效率低O(N)只需要修改指针指向插入动态顺序表，空间不够时需要扩容没有容量的概念应用场景元素高效存储➕频繁访问任意位置插入和删除频繁CPU高速缓存命中率高低

CPU的一些知识

与程序员相关的CPU缓存知识 整理一些计算机基础知识(zhihu)

结束

That’s all, thanks for reading!

数据结构 链表 数据 优化 指针

0 人点赞