山西做杂粮的网站,长沙今天最新招聘信息,网站经常被攻击,wordpress 右侧空白摘要#xff1a; 1#xff0c;双链表的介绍 2#xff0c;双链表的用途 3#xff0c;双链表的节点插入和删除 1#xff0c;双链表的介绍 前面我们讲过单链表#xff0c;单链表的特点就是只能往后访问不能往前访问。单链表一般在面试中用的比较多#xff0c;比如删除倒数第… 摘要 1双链表的介绍 2双链表的用途 3双链表的节点插入和删除 1双链表的介绍 前面我们讲过单链表单链表的特点就是只能往后访问不能往前访问。单链表一般在面试中用的比较多比如删除倒数第 n 个节点链表反转等但在实际的工作中单链表用的并不多。比如Java中的LinkedListLinkedHashMap等都是双链表。 双链表每个节点包含三个域一个是数据域两个指针域。两个指针域中一个指向前一个节点一个指向后一个节点如下图所示 Java代码 // 双链表节点类
class LinkNode {int val;// 节点中存储的数据。LinkNode pre;// 指向前一个节点的指针。LinkNode next;// 指向下一个节点的指针。public LinkNode(int val, LinkNode pre, LinkNode next) {this.val val;this.pre pre;this.next next;}
} C语言 // 双链表节点类
struct LinkNode {int val;// 节点中存储的数据。LinkNode *pre;// 指向前一个节点的指针。LinkNode *next;// 指向下一个节点的指针。LinkNode(int x, LinkNode *p, LinkNode *n) : val(x), pre(p), next(n) {}
}; 单链表中因为只能从前往后遍历我们只需要记录头节点head即可但双链表中可以从后往前遍历我们还需要记录尾节点tail两个方向都可以遍历。如果不想记录尾节点也可以让双链表的首尾相连构成一个环形链表只记录头节点head即可从head开始沿着两个方向都可以访问。 2双链表的用途 双链表的用途非常强大除了当链表使用以外还可以当做普通队列双端队列栈来使用除此之外还可以用于数据的缓存比如常见的LRU(Least Recently Used)缓存LFU(least frequently used)缓存等。 在Android开发中图片的缓存一般使用的是LruCache而LruCache继承的就是LinkedHashMapLinkedHashMap就是一个双向链表。 他会把经常使用的数据插入到头节点head这样不经常使用的数据就会越来越靠后当存储数据足够多的时候就会从尾节点tail往前删除也就是把最不经常使用的数据给删除即达到缓存的效果又防止了数据量过大。 3双链表的节点插入和删除 双链表的节点插入和删除与单链表一样也是分三种情况分别是在头部尾部和中间我们分别来看下。 3.1 头部插入 1创建新节点让它的next指针指向head节点。 2让head的pre指针指向新节点。 3让head指向新节点。 3.2 尾部插入
