网站建设店铺,网站怎么建立视频,小红书官方推广,中铁建设门户网登录初始密码目录 1、链表的定义 2、链表的特点 3、为何要使用链表 4、数组与链表的区别 5、链表的增删查 5.1、在头部插入链表 5.2、在中间插入链表 5.3、删除头节点 5.4、删除中间节点 5.5、查询某个值 6、链表的应用 6.1 如何设计一个LRU缓存算法#xff1f; 6.2 约瑟夫问题 1、链表的定… 目录 1、链表的定义 2、链表的特点 3、为何要使用链表 4、数组与链表的区别 5、链表的增删查 5.1、在头部插入链表 5.2、在中间插入链表 5.3、删除头节点 5.4、删除中间节点 5.5、查询某个值 6、链表的应用 6.1 如何设计一个LRU缓存算法 6.2 约瑟夫问题 1、链表的定义 链表通过指针将一组零散的内存块串联在一起。其中我们把内存块称为”结点“。为了将所有的结点串起来每个链表的结点除了存储数据之外还需要记录链上的下一个结点的地址。 2、链表的特点 1不需要连续的内存空间 2有指针引用 3三种常见的链表结构单链表、双链表、循环链表、跳表不常见但是功能强大用到的地方也很多比如redis可以了解一下 单链表 第一个结点和最后一个结点分别为头结点和尾结点。头结点用来记录链表的基地址有了它我们就可以遍历得到整条链表。而尾结点的特殊地方是指针不是指向下一个结点而是指向一个空地址NULL表示这是链表上的最后一个结点。 双向链表 单向链表只有一个方向结点只有一个后继指针next指向后面的结点。双向链表顾名思义它支持两个方向每个结点不止有一个后继指针next指向后面的结点还有一个前驱指针prev指向前面的结点。双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。缺点如果存储同样多的数据双向链表要比单链表占用更多的内存空间。优点可以支持双向遍历操作灵活特别是对于范围查询有明显的优势、大于、小于。实际应用如 BTreeMySQL索引的叶子节点采用的就是双向链表结构 循环链表 循环链表就是一种特殊的单链表。实际上循环链表与单链表的唯一区别就是尾节点。单链表的尾节点指针指向空地址表示这就是最后的结点了而循环链表的尾结点指针是指向链表的头结点形成一个环一样首尾相连的链表所以循环链表。约瑟夫问题 3、为何要使用链表 稀疏数组一般是针对多维数组 1 2 4 -1 -1 3 5 -1 -1 1 -1 -1 a[3][4]这是一个二维数组-1表示存储的数据为空已开空间大小3*412稀疏数组就是真正存的数据远远小于我们开的空间为了节省空间往往会用链表代替。 4、数组与链表的区别 重要区别 1数组简单易用在实现上使用的是连续的内存空间可以借助CPU的缓存机制缓存行、缓存局部性预读数组中的数据所以访问效率更高。 2链表在内存中并不是连续存储所以对CPU缓存不友好没办法有效预读。 3数组的缺点就是大小固定一经声明就要占用整块连续内存空间。如果声明的数组过大系统可能没有足够的连续内存空间分配给它导致内存不足Out Of Memory。如果声明的数组过小则可能出现不够用的情况。 4动态扩容数组需再申请一个更大的内存空间把原数组拷贝过去非常费时。链表本身没有大小限制天然支持动态扩容。但是链表不断的扩容会把内存撑爆使用时需要注意 5、链表的增删查 单向链表结构头结点指针指向下一节点value存储的值size已存储值的数量 public class MyLinkedList {private int size;ListNode head;class ListNode { //定义链表结构int value;ListNode next;ListNode(int value) { //构造函数用于构造一个结点this.value value;this.next null;head null;}}} 5.1、在头部插入链表 private void insertHead(int data) {//时间复杂度O(1)ListNode newData new ListNode(data);//构造一个结点newData.next head; //栈内存的引用head newData;size;} 5.2、在中间插入链表 private void insertNth(int data, int position) {//插入链表的中间假设定义在第N个插入O(n)if (position 0){//这里表示插入在头部insertHead(data);} else {ListNode newData new ListNode(data);ListNode curr head;for (int i0; i position; i){curr curr.next;//一直往后遍历找到要插入的位置,c/c的 pp-next;}//确保链表不会断裂丢失数据newData.next curr.next;//先将新加的结点指向后面保证不断链curr.next newData;//把当前的点指向新加的点}size;} 5.3、删除头节点 private void deleteHead(int data) {//O(1)head head.next;size--;} 5.4、删除中间节点 private void deleteNth(int data, int position) {//O(1)if (position 0){deleteHead(data);} else {ListNode curr head;for (int i0; i position; i){curr curr.next;}curr.next curr.next.next;//curr.next 表示的是删除的点}size--;} 5.5、查询某个值 public void find(int data){//O(n)ListNode cur head;while(cur ! null){//判断不是尾结点if(cur.value data) break;//找到后退出循环cur cur.next;//遍历下一个结点}} 6、链表的应用
6.1 如何设计一个LRU缓存算法 LRULeast Recently Used最近最少使用它主要思想是当缓存空间占满时移除最近最少使用的缓存对象 /*** 1、先判断链表中是否已存在该data如果已存在则抛弃旧的值然后在head插入新的值* 2、如果不存在改data则直接在head插入该data保证head为最新访问的值* 这里实现的是简单的lru深层次的lru可使用哈希表双向链表实现可参考力扣的题目* param data*/private void lru (int data) {ListNode newData new ListNode(data);ListNode curr head;while (curr.next ! null) {if (curr.value data){//删除该结点curr.next curr.next.next;break;}curr curr.next;}//插入链表头部head newData.next;} 6.2 约瑟夫问题
读者可以先思考此问题的实现该问题的求解过程小编会在另一篇博文解答敬请期待
