目录
编辑
双链表的初始化:
双链表的打印:
双链表的尾插:
双链表的头插:
双链表的尾删:
文章来源地址https://www.toymoban.com/news/detail-646295.html
双链表的头删:
双链表pos位置之前的插入:
双链表pos位置的删除:
关于顺序表和链表的区别:
文章来源:https://www.toymoban.com/news/detail-646295.html
- 上篇文章给大家讲解了无头单向循环链表,它的特点:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构子结构,如哈希桶、图的邻接表等等。但是呢,单链表在笔试中还是很常见的。
- 今天我给大家讲解一下带头双向链表,它的特点:结构复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然复杂,但是使用代码实现以后会发现结构会带来很多优势。
如图,这就是今天我为大家讲解的双链表结构了。下面跟随我的思路走下去,希望让你对链表有新的理解。
双链表的初始化:
- 今天我给大家带来另一种方式改变链表的结构,如果想了解双指针来改变链表的结构,可以参考参考我的上一篇单链表的博客。
- 思路:我创建了一个节点,然后把节点赋给了phead,再让它的上一个位置和下一个位置分别指向它自己,最后返回phead就是我们要的哨兵位的头节点了。
ListNode* ListCreate(ListDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
ListNode* ListInit() { ListNode* phead = ListCreate(0); phead->next = phead; phead->prev = phead; return phead; }
双链表的打印:
- 因为要让终端出现下面的样子,我就用到了打印的函数。
- 首先,还是老套路,我先断言了一下,防止传的参数有问题。
- 因为这里的phead是一个哨兵位,存放着无效的数据,所以,我就定义了一个cur的节点,用循环打印链表中的所有值,并标明他们的方向。
void ListPrint(ListNode* phead) { assert(phead); printf("phead<->"); ListNode* cur = phead->next; while (cur != phead) { printf("%d<->", cur->val); cur = cur->next; } printf("\n"); }
双链表的尾插:
- 在双链表尾插的时候,它的优势就体现出来了,如果是单链表,要尾插的话,是只有遍历找尾节点的,但是呢,如果是双向链表,phead的前一个节点就是尾节点,它就不用找尾,也不需要遍历了。这也是双链表的优势之一。
- 尾插思路:先断言一下,然后用tail保存尾节点,创建一个新节点,然后改变尾节点和头节点链接关系,让newnode为新的尾节点。
void ListPushBack(ListNode* phead,ListDateType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newnode = ListCreate(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
双链表的头插:
- 思路:头插的话,就是先保存一下头节点的位置,然后创建一个新节点,然后改变他们的链接关系就可以了。因为我是先保存了它们的位置,所以谁先链接先都可以,如果没有保存的话,要向好逻辑,不要出现找不到头节点的位置了。
void ListPushFront(ListNode* phead, ListDateType x) { assert(phead); ListNode* newnode = ListCreate(x); ListNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
双链表的尾删:
- 思路:尾删的话,就要记录一下尾节点的前一个节点了,然后去改变一下phead和尾节点前一个节点的链接关系。
void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* tailprev = phead->prev->prev; tailprev->next = phead; phead->prev = tailprev; free(tail); }
双链表的头删:
- 思路:头删的思路,其实和尾删的思路差不多,只不过这里保存的是phead之后的第二个节点了。然后就是改变链接关系。
void ListPopFront(ListNode* phead) { assert(phead); assert(phead != phead->next); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); }
双链表pos位置之前的插入:
- 思路:如果是插入的话,是不是和尾插和头插差不多呢,我在这里是保存的pos之前的节点,然后创建一个新的节点,让pos之前的节点指向新节点,让新节点和pos再建立连接关系。
void ListInsert(ListNode* pos, ListDateType x) { assert(pos); ListNode* posprev = pos->prev; ListNode* newnode = ListCreate(x); posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; }
双链表pos位置的删除:
- 思路:pos位置要删除的话,保存pos上一个节点和pos下一个节点,然后free掉pos位置,再改变他们的链接关系。
void ListErase(ListNode* pos) { assert(pos); ListNode* posprev = pos->prev; ListNode* posnext = pos->next; posprev->next = posnext; posnext->prev = posprev; free(pos); }
大家看了pos位置的删除和pos之前的插入,是不是感觉和前面的尾插尾删和头插头删差不多呢,其实呢,最后的两个函数是可以进行对函数的复用的。
- 尾插:其实就是在ListInsert函数传phead就可以了,这样就实现了尾插。
ListInsert(phead, x);
- 头插:头插是改变phead之后的位置,所以直接传phead->next就可以了。
ListInsert(phead->next, x);
- 头删和尾删:因为我写的删除的函数是删除pos位置,所以传要删除的位置就可以了。
ListErase(phead->prev);
ListErase(phead->next);
关于顺序表和链表的区别:
- 存储空间上:顺序表在物理上是连续的,而链表逻辑上是连续的,而物理上是不一定连续的。
- 随机访问上:顺序表是支持随机访问的,而链表是不支持的,向要访问链表中的节点,是需要遍历的。
- 任意位置的插入和删除:在这里链表就有很大的优势了,链表只需要改变指向就可以实现对任意位置的插入和删除。但是对于顺序表,它可能需要搬运元素,效率太低了。
- 插入:顺序表因为是连续的,所以在插入的上面,可能会有malloc扩容,但是呢malloc是有消耗的,如果一次扩二倍,但是用的不多,就会造成对空间的浪费,如果一次扩的空间是+1,可能局面临着多次扩容,而malloc的消耗并不低,所以这是不可取的。而链表并没有容器的概念,在这方面有优势。
- 缓存利用率:顺序表的缓存命中率高,而链表低。
#define _CRT_SECURE_NO_WARNINGS 1 #include "DoubleList.h" ListNode* ListCreate(ListDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode* ListInit() { ListNode* phead = ListCreate(0); phead->next = phead; phead->prev = phead; return phead; } void ListPrint(ListNode* phead) { assert(phead); printf("phead<->"); ListNode* cur = phead->next; while (cur != phead) { printf("%d<->", cur->val); cur = cur->next; } printf("\n"); } void ListPushBack(ListNode* phead,ListDateType x) { assert(phead); //ListNode* tail = phead->prev; //ListNode* newnode = ListCreate(x); //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); } void ListPushFront(ListNode* phead, ListDateType x) { assert(phead); //ListNode* newnode = ListCreate(x); //ListNode* first = phead->next; //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; ListInsert(phead->next, x); } void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); //ListNode* tail = phead->prev; //ListNode* tailprev = phead->prev->prev; //tailprev->next = phead; //phead->prev = tailprev; //free(tail); ListErase(phead->prev); } void ListPopFront(ListNode* phead) { assert(phead); assert(phead != phead->next); //ListNode* first = phead->next; //ListNode* second = first->next; //phead->next = second; //second->prev = phead; //free(first); ListErase(phead->next); } int ListSize(ListNode* phead) { assert(phead); int size = 0; ListNode* cur = phead->next; while (cur != phead) { ++size; cur = cur->next; } return size; } void ListInsert(ListNode* pos, ListDateType x) { assert(pos); ListNode* posprev = pos->prev; ListNode* newnode = ListCreate(x); posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; } void ListErase(ListNode* pos) { assert(pos); ListNode* posprev = pos->prev; ListNode* posnext = pos->next; posprev->next = posnext; posnext->prev = posprev; free(pos); }
什么是缓存利用率:
关于“Cache Line” ,缓存是把数据加载到离自己进的位置,对于CPU来说,CPU是一块一块存储的。而这就叫“Chche Line”。
我们所写的程序,其实都是会形成不同的指令,然后让CPU执行,但是呢,CPU执行速度快,内存跟不上,所以CPU一般都是把数据放到缓存中,对于小的字节来说,直接由寄存器来读取,大的字节会用到三级缓存。
简而言之,数据先被读取,然后运算,最后放到主存中,如果没有命令,就继续。
而顺序表呢,它的物理结构是连续的,它可能一开始没有命中,但是一旦缓存命中了,它可能就会被连续命中,所以这也是顺序表缓存利用率高的原因,而链表也是因为他的物理结构,导致缓存利用率低。
下面是双链表的源码:
#define _CRT_SECURE_NO_WARNINGS 1 #include "DoubleList.h" ListNode* ListCreate(ListDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } ListNode* ListInit() { ListNode* phead = ListCreate(0); phead->next = phead; phead->prev = phead; return phead; } void ListPrint(ListNode* phead) { assert(phead); printf("phead<->"); ListNode* cur = phead->next; while (cur != phead) { printf("%d<->", cur->val); cur = cur->next; } printf("\n"); } void ListPushBack(ListNode* phead,ListDateType x) { assert(phead); //ListNode* tail = phead->prev; //ListNode* newnode = ListCreate(x); //tail->next = newnode; //newnode->prev = tail; //newnode->next = phead; //phead->prev = newnode; ListInsert(phead, x); } void ListPushFront(ListNode* phead, ListDateType x) { assert(phead); //ListNode* newnode = ListCreate(x); //ListNode* first = phead->next; //phead->next = newnode; //newnode->prev = phead; //newnode->next = first; //first->prev = newnode; ListInsert(phead->next, x); } void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); //ListNode* tail = phead->prev; //ListNode* tailprev = phead->prev->prev; //tailprev->next = phead; //phead->prev = tailprev; //free(tail); ListErase(phead->prev); } void ListPopFront(ListNode* phead) { assert(phead); assert(phead != phead->next); //ListNode* first = phead->next; //ListNode* second = first->next; //phead->next = second; //second->prev = phead; //free(first); ListErase(phead->next); } int ListSize(ListNode* phead) { assert(phead); int size = 0; ListNode* cur = phead->next; while (cur != phead) { ++size; cur = cur->next; } return size; } void ListInsert(ListNode* pos, ListDateType x) { assert(pos); ListNode* posprev = pos->prev; ListNode* newnode = ListCreate(x); posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; } void ListErase(ListNode* pos) { assert(pos); ListNode* posprev = pos->prev; ListNode* posnext = pos->next; posprev->next = posnext; posnext->prev = posprev; free(pos); }
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int ListDateType; typedef struct ListNode { ListDateType val; struct ListNode* next; struct ListNode* prev; }ListNode; ListNode* ListCreate(ListDateType x); void ListPrint(ListNode* phead); ListNode* ListInit(); void ListPushBack(ListNode* phead,ListDateType x); void ListPushFront(ListNode* phead, ListDateType x); void ListPopBack(ListNode* phead); void ListPopFront(ListNode* phead); int ListSize(ListNode* phead); void ListInsert(ListNode* pos, ListDateType x); void ListErase(ListNode* pos);
到了这里,关于数据结构——双链表(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!