链表(上)

Monday, April 15, 2019

通过链表实现LRU缓存淘汰算法

常见的缓存淘汰策略

  • 先进先出FIFO
  • 最少使用LFU
  • 最近最少使用LRU

数组和链表的区别

  • 数组需要一块连续的内存空间来存储
  • 链表通过指针,将一组零散的内存块串联起来使用

链表的常见结构

  • 单链表
  • 双向链表
  • 循环链表

单链表

  • 第一个节点叫头结点
  • 最后一个节点叫做尾节点
  • 尾节点的指针指向空地址NULL
  • 因为链表不是连续的,插入和删除一个数据非常迅速,复杂度为O(1)

  • 链表无法像数组那样,根据首地址和下标,通过寻址公式直接计算对应的内存地址,而是需要根据指针一个节点一个节点的去遍历,所以链表的随机访问性能没有数组好,需要O(n)的复杂度。

循环链表和双向链表

  • 循环链表的优点是链尾可以直接访问链头。
  • 要处理的数据具有环形结构特点时,就特别适合才用循环链表(如约瑟夫问题)。

  • 每个节点有一个后继指针next指向后面的结点,还有一个前驱指针prev指向前面的节点。
  • 双向链表支持O(1)找到前驱结点
  • 在某些情况下,插入,删除等操作比单链表更简单高效

单链表的插入删除也是O(1),但实际情况并不是如此,我们先看看删除,一般有两种情况

  • 删除结点中“值等于某个值”的结点
  • 删除给定指针指向的结点

第一种情况我们需要首先找到这个值,为O(n),加上删除O(1),所以总时间复杂度为O(n) 第二种情况已经找到了要删除的节点,但是需要知道前驱结点,所以单链表还是要先遍历查找,但双链表就不需要了,所以这里双链表只要O(1) 插入同理

  • 在有序列表中,查询效率也会更高,因为可以记录上次查找的位置p,可以根据查找的值与p的大小关系,决定向前还是向后查找。
  • 总得来说,双链表就是用空间换时间的设计思想。

数组和链表性能对比

  • 在实际使用中,并不能局限于时间复杂度。
  • 数组简单易用,利用的是连续的内存空间,可以借助CPU的缓存机制,预读数组数据,访问效率更高。
  • 数组的缺点是大小固定,需要占用整块连续内存空间,当数组数据量过大时,扩容时非常耗时,链表没有这个问题
  • 链表对内存占用更多,因为每个结点都需要存指针,而且对链表频繁的进行插入删除,导致频繁的内存申请和释放,容易造成内存碎片,Java会导致频繁的垃圾回收。

链表实现LRU

我们维护一个单链表,越靠近尾部的结点表示越早访问的,当有新的数据,先从头开始遍历链表。

  • 如果已经有该数据,则删除原来的结点,并将其放到链表头部。
  • 如果没有,且缓存未满,则直接插入到头部。
  • 如果没有,且缓存满了,则将尾部结点删除,再插入到头部。

因为无论如何操作,都需要遍历链表,所以复杂度是O(n),如果引入散列表,可以降到O(1)

判断一个字符串是否是回文字符串

  • 用快慢指针去定位中间结点
  • 对前部分或者后部分进行逆序
  • 前后部分进行比较,判断是否为回文
  • 复原
数据结构-算法

链表(下)

iOS面试题