双向链表（双向链表存储结构中,删除p所指的结点时需修改指针）

本篇文章给大家谈谈双向链表，以及双向链表存储结构中,删除p所指的结点时需修改指针对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、双向链表的原理与实现
• 2、c++ 单向链表和双向链表有什么区别？各自有什么优缺点？
• 3、单链表和双链表区别
• 4、双向链表相比单链表的优势

双向链表的原理与实现

顾名思义，双向链表跟单链表和循环列表最大的差别，就是同时拥有前驱指针迅缺和后驱指针，基于这一个特性，查询某结点的前一个结点，时间复杂度可以达到O(1)，非常高效。双向链表的存取时间复杂度是O(n)，增删时间复杂度为O(1)，跟其他链表没啥区别。

双向链表表示意图：

所以双向链表的结点定义如下：

class Node{

Object data; //元素值

Node pre; //前驱指针

Node next; //后驱指针

}

对于双向链表做增删操作，有一定的顺序要求，顺序不对，很可能会造成空指针异常。

双向链表增加结点示意图：

双向链表删除结点示意图：

将不常被访问的数据进行淘汰，来保证有限空间的使用，在计算机cache当中广为应用，因为cache的大小有限，为了尽可能多的命中热数据，就可以将冷数据进行淘汰，充分利用内存空间。

-》put进数据时，将其放于链尾，因为链尾的数据最不容易被淘汰，并且插入之前需要判断一下空间是否已满，如果满了，就需要将链头的数据淘汰掉。

-》get数据时，如果未在cache中命中，就返回-1，来模拟cache未命中的现象，如果命中，将该数据从当前位置删除，并移至链尾。

之前也提到过，双向链表同其他链表一样，存取时间复杂度都是O(n)，因为都是需要遍历嫌昌判链表才行，增删操作的时间复杂度都是O(1)。实现LRU的过程，如果是put操作，那么针对双向链表的操作只有删除第一个结点，然后添加尾结点，时间复杂度为O(1)，如果是get操作，需要先遍历查找芹改到对应的结点，然后在进行增删操作，前者时间复杂度为O(n)，后者时间复杂度为O(1)，所以加起来还是O(n)。

后续为大家介绍一种实现LRU算法，并且时间复杂度为O(1)的实现方式。

LRU算法的原理与实现

[img]

c++ 单向链表和双向链表有什么区别？各自有什么优缺点？

一、指代不同

1、双向链表：也叫双链表，是链表的一种，每个数据结点中都有两个指针，分别指向直接后继和直接前驱

2、单向链表：是链表的一种，野孙其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

二、优点不同

1、双向链表：从双向链表中的任意一个结点开始，都可以很方便地访问前驱结点和后继结点。

2、单向链表：单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小，结点的访问方便，可以通过循环或者递归的方法访问到任意数据。

三、缺点不同

1、双向链表：增加删除节点复杂，需要多分配一个指针存储空间。

2、单向链表：结点的脊脊银删除非常方便，不需要像线性结构那样移动剩下的数据，但是平均的访问效率低于线樱宴性表。

参考资料来源：百度百科-双向链表

参考资料来源：百度百科-单向链表

单链表和双链表区别

1、指向不同：单向链表只有一个指向下一结点的指针，双向链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针。

2、功能不同：单向链表只能next ，双向链表游念可以return。

3、单双向不同：单链表只能单向读取，双向链表可以通过prev()快速找到前一结点。

单向链表优缺点：

1、优点：单向链表增加删除节点简单。遍历神轮困桐正时候不会死循环；

2、缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。

双向链表优缺点：

1、优点：可以找到前驱和后继，可进可退；

2、缺点：增加删除节点复杂，多需要分配一个指针存储空间。

双链表：LinkedList

单链表：HashMap

双向链表相比单链表的优势

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

你可能会说，我刚讲到单链表的插入、删除操作的时间复杂度已经是 O(1) 了，双向链表还

能再怎么高效呢？其实说单链表插入、删除操作的时间复杂度为O(1)是不准确的，或者说是有先决条件的。

我们先来看删除操作。

在实际的软件开发中，从链表中删除一个数据无外乎这两种情况：

对于第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从

头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后将其删除。

尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。败做咐

对于第二种情况，我们已经找到了要删除的结点胡世，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p-next=q，说明 p 是 q 的前驱结点。

但是对于双察纯向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了！

同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。

除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。 因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

关于双向链表和双向链表存储结构中,删除p所指的结点时需修改指针的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。