单链表
data.next-->data.next-->NULL
时间复杂度
插入节点:
时间复杂度:O1
删除节点
时间复杂度:O1
查找节点
时间复杂度:O(n)
链表想要随机访问第K个元素arr[k],需要根据指针一个一个找
双向链表
-->prev.data.next<==>prev.data.next<==>prev.data.next
即支持两个方向,每个节点不知有一个后继指针next,还有一个前驱指针prev指向前面的结点
空间复杂度
双向链表需要额外的两个空间来存储后继结点和其前驱结点的地址.所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间.虽然两个指针比较浪费存储空间,但是可以支持双向遍历.这样也带来了双向链表操作的灵活性
特点
双向链表可以支持O1时间复杂度的情况下找到前驱结点,这样,双向链表在某些情况的插入,删除操作都要比单链表简单高校.
循环链表
单链表的尾节点指针指向空地址
循环链表的尾节点指针指向链表的头结点
优点:从链尾到链头比较方便.当要处理的数据具有环型结构特点时,就特别适合采用循环链表
把约瑟夫问题降低到O(n)时间复杂度
具体的复杂度分析:
删除操作,有两种情况
- 删除结点中 “ 值等于某个给定值 ” 的结点;
- 删除给定指针指向的结点。
第一种情况,为了找到节点的值等于给定值的结点,单链表和双向链表都要从头结点一个一个一次遍历比较,直到找到这个节点,才利用指正操作进行删除.
主要的时间复杂度在于遍历结点,时间复杂度为On
第二种情况,我们知道要删除哪一个结点,可是删除这个结点的操作需要其前驱结点的参与,因此我们还要知道指向前驱结点的指正.这时双向链表和单链表的区别就体现出来了.
单链表依然需要从头结点开始遍历链表.因此,单链表删除的时间复杂度为On
双向链表的结点中有prev,可以直接删除,因此,双向链表删除的时间复杂度为O1
查找
除了插入和删除操作以外,双向链表的按值查询效率也比单链表快
记录上次查找的位置P,每次查询时,根据要查找的值与P的大小关系,决定是往前还是往后查找,平均下来只需要查找一般的数据
范例
LinkedHashMap,采用了双向链表的数据结构
链表与数组
数组
实现上使用的是连续的内存空间,可以借助CPU的缓存机制,预读数组中的数据,所以访问效率高
缺点:大小固定,如果内存不够,只能重新再申请一个更大的内存空间,把原数组拷贝进去,费时
链表
在内存中并不是连续存储,对于CPU缓存不友好,没有办法有效预读.
与数组相比,天然支持动态扩容
缺点:需要消耗额外的存储空间去存储一份指向下一个结点的指正,所以内存消耗会翻倍.并且,对链表进行频繁的插入,删除操作,还会导致频繁的内存申请和释放,容易造成内存碎片.比如java:会导致频繁的GC(垃圾回收)
基于链表实现LRU缓存淘汰法
思路:
我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的,当有一个新的数据被访问时,我们从链表头开始顺序遍历链表.
如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后插入到链表的头部
如果这数据没有在缓存链表中,又可以分为两种情况:
如果此时缓存未满,则将此节点直接插入到链表的头部
如果此时缓存已满,则链表尾结点删除,将新的数据结点插入到链表的头部
时间复杂度:O(n)
优化:引入散列表,来记录每个数据的位置,将缓存访问的时间复杂度降到O1
代码:
查找key:
//在数组中a中,查找key,返回key所在的位置
int find(char* a, int n, char key) {
//边界条件处理,如果 a 为空,或者n<=0,说明数组中没有数据,就不用while循环比较了
if(a == null || n <= 0) {
return -1;
}
int i = 0;
//这里有两个比较操作: i<n 和 a[i]==key.
while (i < n) {
if (a[i] == key) {
return i;
}
++i;
}
return -1;
}
//在数组a中,查找key,返回key所在的位置
//n表示数组a的长度
int find(char* ａ，int n,char key){
if(a == null || n<= 0 ){
return -1;
}
//这里因为要将a[n-1]的值替换成key,所以要特殊处理这个值
if(a[n-1]==key){
return n-1;
}
//要把a[n-1]的值临时保存在变量tmp中,以便之后恢复
char tmp = a[n-1];
a[n-1] = key;
int i = 0;
while (a[i] != key){
++i;
}
//恢复a[n-1]原来的值
a[n-1] = tmp;
if(i == n-1){
//如果i == n-1 说明,在0...n-2之间没有key,所以返回-1
return -1;
}else{
//否则,返回i,就是要等key值的元素的下标
return i;
}
}
注意点:
1.理解指针或引用的含义
java,Python没有指针,而是引用{都是用来存储所指对象的内存地址}
2.警惕指针丢失和内存泄露
简单地说,对结点进行操作时,注意操作的顺序
例如C语言:
//-->a.next-->b.next-->,插入一个结点x.next
x->next = p->next;//将x的结点的next指针指向b结点
p->next = x//将p的next指针指向x结点
3.利用哨兵简化实现难度
普通的实现方式,在针对链表的插入删除时,需要对插入第一个结点和最后一个节点的情况进行特殊处理,例如:
//向空链表插入第一个节点
if(head == null){
head = new_node;
}
//删除链表中的是最后一个节点
if(head->next == null){
head = null;
}
引入哨兵结点:处理边界问题,我们不管链表是否为空,head指针都会一直指向这个哨兵结点.
带头链表:有哨兵节点的链表
null.next-->a.next-->b.next
4.留意边界条件处理
检查边界条件是否考虑全面,代码在边界条件下能否正确运行
- 如果链表为空,代码能否正常工作
- 如果链表只包含一个结点时,代码能否正常工作
- 如果链表只包含两个结点,代码能否正常工作
- 代码逻辑在处理头结点和尾节点时,能否正常工作
5.对于复杂的链表操作,可以举例,画图进行理解
6.常见的链表操作:
- 单链表反转
- 链表中环的检测
- 两个有序的链表的合并
- 删除链表倒数第n个结点
- 求链表的中间结点
7.对于链表,需要注意内存管理
Comments