链表

1. 双向链表的删除操作

删除的两种情况:
1.删除节点(节点的值等于给定值)
2.删除给定指针指向的节点

第一种情况,单链表还是双向链表都需要遍历,删除的时间复杂度是O(1),遍历的复杂度是O(n),因此结果还是O(n)
第二种情况,单链表是O(n),双链表是O(1)

@discardableResult public func remove(node:Node) -> Node?{
    let previous = node.previous
    let next = node.next
    
    //判断之前的节点是否存在,不存在则说明删除的是头节点
    if let pre = previous {
        pre.next = next
    }else{
        head?.next = next
    }
    
    next?.previous = previous
    node.next = nil
    node.previous = nil
    return node
}

2. 双向列表的插入同删除,耗时操作主要发生在查找节点阶段.

3. 对于有序链表,双向链表的查找操作,可以记录上次查找的位置p,并比较p节点的值与给定值的大小,平均只需要查一半的数据. (还没有自己实现过)

4. 数组和链表的对比

   • 数组是连续的内存空间,可以借助CPU缓存机制,访问效率更高,而链表不行。
   • 数组的缺点，不支持动态扩容。
   • 链表的缺点，内存消耗翻倍，频繁的插入和删除，导致频繁的内存申请和释放，容易造成内存碎片。

---

LRU缓存淘汰算法

维护一个有序链表，越靠近尾部是越早访问的，当添加一个节点的时候，有三种情况：

1. 在链表中，则删除该节点，添加到头部
2. 不在链表中，添加到头部
3. 不在链表中，链表已满，删除尾部，添加到头部。

---

写链表的几点注意事项

1. 利用哨兵简化难度
2. 注意边界条件的处理
   • 链表为空
   • 链表有一个节点
   • 链表有两个节点
   • 代码在处理头结点和尾节点时候的逻辑
3. 几个需要熟练掌握的操作
   • 单链表翻转
   • 链表中环的检测
   • 两个有序链表的合并
   • 删除链表倒数第n个节点
   • 求链表的中间节点