一般题目给的单链表是无头单向非循环链表,但是我们可以升级成双向带头循环链表,这个链表比起单链表更有优势。
上面带有head头结点的链表就是带头的链表,题目中的链表一般没有头节点,phead指针直接指向第一个结点,而带头的链表phead指针指向头结点,头节点指向第一个结点,一般称为 哨兵位的头节点。
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;
比起单链表的结点,多了指向前一个结点的指针——prev。
LTNode* BuyListNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));assert(newnode);newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;}
LTNode* InitList()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}
初始化即开辟一个头节点,然后让这个头节点的前后指针域都指向自己。
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x); newnode->prev = phead->prev;phead->prev->next = newnode;newnode->next = phead;phead->prev = newnode;
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);//空phead->prev = phead->prev->prev;free(phead->prev->next);phead->prev->next = phead;}
双向带头循环链表并没有单独讨论空链表的情况,这就是头节点的好处,之所以不用讨论就是因为节点的个数不可能为0,最少也包括一个头节点。
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->next;newnode->next = phead->next;newnode->prev = phead;tail->prev = newnode;phead->next = newnode;}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* tail = phead->next->next;LTNode* tailPrev = phead->next;phead->next = tail;tail->prev = phead;free(tailPrev);}
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("[%p | %d | %p]", cur->prev, cur->data, cur->next);if(cur->next != phead)printf("<->");cur = cur->next;}printf("\n");
}
就是从头遍历一遍即可,但是需要注意的是,这是一个循环链表,如果我们不加限制条件的话,他会一直循环下去。所以,我们这里需要加上判断条件。
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);assert(phead->next != phead);LTNode* cur = phead->next;while (cur->data != x && cur != phead)cur = cur->next;if (cur == phead)return NULL;else return cur;
}
也要加限制条件。
void* LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* tail = pos->prev;tail->next = newnode;newnode->next = pos;newnode->prev = tail;pos->prev = newnode;
}void* LTErase(LTNode* pos)
{assert(pos);LTNode* tail = pos->prev;tail->next = pos->next;tail->next->prev = tail;free(pos);
}
实现方式之前的头尾操作一样,也可以复用到头尾操作中。
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next != phead;
}size_t LTSize(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;size_t size = 0;while (cur != phead){size++;cur = cur->next;}return size;
}void LTDestory(LTNode* phead)
{LTNode* cur = phead->next;while (cur != phead)LTErase(cur);free(phead);
}
逐个释放就行。
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或者删除元素 | 可能需要搬移元素,效率低O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |
顺序表:
优点:尾插尾删效率高,下标的随机访问。
缺点:空间不够需要扩容(扩容的代价大);头部或者中间插入删除效率低,需要挪动数据。
链表:
优点:需要扩容,按需申请释放小块结点内存;任意位置插入效率很高–O(1)。
缺点:不支持下标随机访问;
CPU与内存经常有数据的访问与存储,但两者运行速度不同,就导致了CPU会“等待”内存传输数据的情况,我们在二者之间搭建一片缓冲区域,即缓存,来解决这个问题。
从下到上,各种存储器的内存逐渐降低,数据传输速度逐级增高。
那么每次CPU会从寄存器中读取数据,这二者的速度差距已经大大缩小了。我们以一个数组为例,我们想对第一个元素进行计算,我们不仅会把第一个元素所对的内存传输到寄存器,还会把其相邻的内存空间传输到寄存器中作为备用,每次传输到寄存器中的数据的大小取决于电脑的相应配置。
这样,我们在CPU访问完第一元素后,假设我们还需要计算第二个元素,我们又恰好在寄存器中存储了第二个元素的内存信息。CPU便可直接调用,而无需寄存器再去读取。这就叫缓存命中。
链表和顺序表各有优势,带头双向链表比起单链表更加方便操作。
深窥自己的心,而后发觉一切的奇迹在你自己。——培根