Data-Struction-Linked-List工程中应用

Posted on | Views:

Linked List

简而言之，链表由node组成，每个node包含data value和next指向下一个node的指针。相比于数据，增删改时间复杂度为N（0），但查询复杂度为N（n）。为提高查询速度类似Redis中采用了Skip List。
linked-list

1
2
3
4
5
class Node {
public:
    int data;
    Node* next;
};

Skip List

在原有链表基础上，增加了维度。查询操作中，2维Skip List将next指针每次向后1位，改进为向后2位，诸如此类。
linked-list

可参考
https://www.jianshu.com/p/fd4a4248cf2d
https://www.jianshu.com/p/a85e392118a9
https://www.cnblogs.com/learnhow/p/6749648.html

leetcode-LRU缓存算法

https://www.jianshu.com/p/b1ab4a170c3c