来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/tenth-line

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个文本文件 file.txt，请只打印这个文件中的第十行。

示例：

假设 file.txt 有如下内容：

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10

你的脚本应当显示第十行：

Line 10

说明：

1. 如果文件少于十行，你应当输出什么？
2. 至少有三种不同的解法，请尝试尽可能多的方法来解题。

二、题解

2.1 tail+head

返回文本中的第十行，最简单的方式可以通过tail + head配合输出，通过head取到前面10行，然后输出前面10行的最后一行。很容易能想到的办法：

head -10 file.txt | tail -1

但这么做就错了，题目中已经提到如果文件少于10行，你应当输出什么？。一旦文件少于10行，上面的命令会输出文件的最后一行，不满足题意。正确的命令：

tail -n +10 file.txt | head -1

-n +10表示从第10行开始到结束，意思是先从第10行开始取到结束的所有数据然后取第一行。

2.2 sed

sed的p模式可以直接打印指定行：

sed -n '10p' file.txt

2.3 awk

awk内置变量NR表示行数

awk 'NR==10' file.txt

一、题目描述

Description

Write a program to convert numbers in one base to numbers in a second base. There are 62 different digits: { 0-9,A-Z,a-z }
HINT: If you make a sequence of base conversions using the output of one conversion as the input to the next, when you get back to the original base, you should get the original number.

Input

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines will have a (decimal) input base followed by a (decimal) output base followed by a number expressed in the input base. Both the input base and the output base will be in the range from 2 to 62. That is (in decimal) A = 10, B = 11, ..., Z = 35, a = 36, b = 37, ..., z = 61 (0-9 have their usual meanings).

Output

The output of the program should consist of three lines of output for each base conversion performed. The first line should be the input base in decimal followed by a space then the input number (as given expressed in the input base). The second output line should be the output base followed by a space then the input number (as expressed in the output base). The third output line is blank.

Sample Input

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

Sample Output

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

Source

Greater New York 2002

二、题目解析

题目的意思是实现62进制内任意进制数据的转换，其中A-Z表示10-35，a-z表示36-62。

这道题目一共考察了两个问题点，第一个是进制转换，第二个是大数据处理。更倾向于考察第二个问题点。

看了很多题解，百度上的题解基本都是copy的，一模一样的代码套进去，都没有说明白为什么要这样，没有任何价值。最后是google到的一篇题解才真正明白，其实解题的思路很简单，就是实现进制转换的短除法，然后处理除法过程中的大数据运算。

2.1 进制转换

解题前首先要搞清楚进制之间的转换逻辑，A进制转B进制如何转？

一般的思路是先从当前进制转到10进制，再从10进制转成目标进制。

从其他进制转换成十进制的办法是按权相加：

从十进制转成其他进制的办法是短除法：

2.2 大数计算

除了进制转换以外，最重要的功能就是除法的实现了，如何通过除法来获取余和商。

因为题目给的数据范围过大，如果用整形来保存数据，肯定是不够的，即使是long long或者更大的类型，都不足以容纳下题目所要求的数据范围。因此，数据只能用字符数组来保存，每个数组元素表示1位数字。

那么这道题目就转变成了通过字符串数组来求商和余数的问题了，只要循环求出所有的商和余数，问题就解决了。

三、代码

代码一共分为几个步骤：

1. 将字符数组中的每个元素都转成整形，方便运算。
2. 对每个元素求商和余数，模拟短除法，记录余数。
3. 反转所有的余数，转成字符形式，输出。

第一部分，62进制字符和数字之间的相互转换：

// char转整形
static int char2int(char ch) {
    if (ch >= '0' && ch <= '9')
        return ch - '0';
    else if (ch >= 'a' && ch <= 'z')
        return ch - 'a' + 36;
    else
        return ch - 'A' + 10;
}

// 整形转char
static char int2char(int n) {
    if (n >= 0 && n <= 9)
        return '0' + (char) n;
    else if (n >= 10 && n <= 35)
        return 'A' + n - 10;
    else
        return 'a' + n - 36;
}

第二部分，任意进制转换函数：

char *base_conversion(int from, int to, const char *src, char *ans) {
    int len, i, j, idx;
    unsigned int tmp[MAX_SIZE], ans_rev[MAX_SIZE];
    len = strlen(src);

    // 将字符串转成整形
    for (i = 0; i < len; i++) {
        tmp[i] = (char)char2int(src[i]);
    }
    tmp[len] = '\0';

    idx = 0;
    for (i = 0; i < len;) {
        // 短除法，辗转相除，从高位往低位除
        // 假设当前字符串是123，下面就是让123除2得到商61和余1的过程
        // 下一次再走进这里就是通过63取得商31和余1的过程
        for (j = i; j < len - 1; j++) {
            tmp[j + 1] += tmp[j] % to * from;
            tmp[j] = tmp[j] / to;
        }
        
        // 最后一位取余数，ans_rev是逆序排放的余数
        ans_rev[idx++] = tmp[len - 1] % to;
        tmp[len - 1] /= to;
        
        // tmp[i]现在是商，忽略掉头部的0
        while (i < len && !tmp[i])
            i++;
    }

    // 反转所有的余并转成字符形式
    ans[idx] = '\0';
    for (j = 0; j < idx; j++) {
        ans[j] = int2char(ans_rev[idx - j - 1]);
    }
    return ans;
}

第三部分，main函数：

int main() {
    char input[MAX_SIZE], output[MAX_SIZE];
    int n, i = 0, from, to;
    scanf("%d", &n);
    while (++i < n) {
        scanf("%d %d %s", &from, &to, input);
        base_conversion(from, to, input, output);
        printf("%d %s\n%d %s\n\n",from, input, to, output);
    }
    return 0;
}

要注意的一个问题是输出格式是三行，每行输出后面都要有一个空行。

单元测试案例

// 测试char和int互转
TEST(base_conversion, int2char_and_char2int) {
    char map_arr[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    int i;
    for (i = 0; i < 62; i++) {
        EXPECT_EQ(i, char2int(map_arr[i]));
    }
    for (i = 0; i < 62; i++) {
        EXPECT_EQ(map_arr[i], int2char(i));
    }
}

// 测试进制转换，数据来源样例输入
TEST(base_conversion, conversion) {
    char input[MAX_SIZE] = { 0 }, output[MAX_SIZE] = { 0 };
    strcpy(input, "103");
    EXPECT_STREQ(base_conversion(10, 2, input, output), "1100111");
    EXPECT_STREQ(base_conversion(62, 2, "abcdefghiz", output), "11011100000100010111110010010110011111001001100011010010001");
    EXPECT_STREQ(base_conversion(10, 16, "1234567890123456789012345678901234567890", output), "3A0C92075C0DBF3B8ACBC5F96CE3F0AD2");
    EXPECT_STREQ(base_conversion(16, 35, "3A0C92075C0DBF3B8ACBC5F96CE3F0AD2", output), "333YMHOUE8JPLT7OX6K9FYCQ8A");
    EXPECT_STREQ(base_conversion(35, 23, "333YMHOUE8JPLT7OX6K9FYCQ8A", output), "946B9AA02MI37E3D3MMJ4G7BL2F05");
    EXPECT_STREQ(base_conversion(23, 49, "946B9AA02MI37E3D3MMJ4G7BL2F05", output), "1VbDkSIMJL3JjRgAdlUfcaWj");
    EXPECT_STREQ(base_conversion(49, 61, "1VbDkSIMJL3JjRgAdlUfcaWj", output), "dl9MDSWqwHjDnToKcsWE1S");
}

EAGAIN和EWOULDBLOCK是linux环境下的两个错误码，在非阻塞IO中经常会碰到，对新手而言，如何处理这两个值非常头疼。如果处理不当，很容易导致程序异常。

EAGAIN的官方定义：

“Resource temporarily unavailable.” The call might work if you try again later. The macro EWOULDBLOCK is another name for EAGAIN; they are always the same in the GNU C Library.

翻译：资源短暂不可用，这个操作可能等下重试后可用。它的另一个名字叫做EWOULDAGAIN，这两个宏定义在GNU的c库中永远是同一个值。

EWOULDBLOCK的定义：

“Operation would block.” In the GNU C Library, this is another name for EAGAIN (above). The values are always the same, on every operating system.

翻译：操作将会被阻塞，在GNU C的库中，它的另外一个名字是EAGAIN，在任何操作系统中他们两个的值都是一样的。

这两个错误码在大多数系统下是都同一个东西，特别是在使用了GNU的libc库平台（目前广泛使用的centos和ubuntu都是）下一定是相同的。这个错误产生的情况：

• 尝试在一个设置了非阻塞模式的对象上执行阻塞操作，重试这个操作可能会阻塞直到其他条件让它可读、可写或者其他操作。
• 对某些操作来说，资源短暂不可用。例如fork函数可能返回这个错误（当没有足够的资源能够创建一个进程时），可以采取的操作是休息一段时间然后再继续操作。

那么应该如何处理这个错误？

最好的办法是重试，重试一定次数后还不成功就退出操作。

为什么不能无限重试呢？假设在通过socket发送一段数据，发送缓冲区如果一直不可写，就会出现无限循环的情况，进程卡死。

其他

在某些较老的unix系统上，这两个值的意义可能不一样。

可以参考：Which systems define EAGAIN and EWOULDBLOCK as different values?。

参考

Difference between 'EAGAIN' or 'EWOULDBLOCK'

Error Codes

一、索引类型

索引根据底层实现可分为B-Tree索引和哈希索引，大部分时候我们使用的都是B-Tree索引，因为它良好的性能和特性更适合于构建高并发系统。

根据索引的存储方式来划分，索引可以分为聚簇索引和非聚簇索引。聚簇索引的特点是叶子节点包含了完整的记录行，而非聚簇索引的叶子节点只有所以字段和主键ID。

根据聚簇索引和非聚簇索引还能继续下分还能分为普通索引、覆盖索引、唯一索引以及联合索引等。

- 阅读剩余部分 -

一、AOF持久化

1.1 实现机制

AOF（Append Only File）是redis持久化方式的一种，它通过把所有redis执行过的命令都写入到文件来维持持久化。一旦服务崩溃，则可以重放这些命令来恢复服务数据。

例如，在redis上执行下面2条语句：

127.0.0.1:6379> set data "helloworld"
OK
127.0.0.1:6379> sadd zdata hello world
(integer) 2

那么AOF文件中的内容就类似是：

set data "helloworld"
sadd zdata hello world

当然，文件中保存不是直接的命令语句。而是按照redis命令请求协议保存的，除了执行的命令以外还有一些其他的内容也会保存到文件。redis协议是redis执行命令专用的一种协议，当客户端向服务端发送请求也是使用的redis协议，AOF也使用redis协议的好处是可以直接使用redis协议解析库，不用再单独实现一套。

AOF数据并不是实时写入到文件中的，而是优先保存在缓冲区。redisServer对象中保存了一个aof_buf字段，它就是aof命令的保存缓冲区。当执行完命令后，会先把指令保存到这里，然后根据策略把缓冲区中的内容写入到磁盘。一个要注意的是，文件写入磁盘并不会立马刷新到文件系统，因为操作系统对系统IO有缓存，缓存到达一定条件后才会同步缓存到文件系统。

为了避免数据没有及时写入到文件系统（还在缓存中），AOF提供了三种策略来同步缓存：

1.2 AOF重写

当服务运行久了之后，AOF文件会变得很大，redis提供了AOF重写功能来优化AOF文件数据。

所做的优化就是整合指令，例如：

127.0.0.1:6379> zadd age 14 hello 15 world 16 nginx
(integer) 3
127.0.0.1:6379> zrem age hello
(integer) 1

执行完这两个命令后，数据库保存了一个有序集合age，里面包含了两个元素world和nginx。其中hello在第一个命令中加进来了，但是第二个指令又删除了，所以实际上写入AOF文件并不需要上面两行，只需要一行就可以完成：

zdd age 15 world 16 nginx

AOF重写就是基于这种策略来重写的，但是有一个要注意的地方是：在执行AOF写入的时候，会导致redis阻塞。所以一般建议是使用后台重写来完成整个AOF文件的重写，后台重写会新建一个子进程，避免在父进程中操作阻塞正常业务。执行后台重写的指令是BGREWRITEAOF。

二、RDB持久化

RDB持久化是redis的第二种持久化方式，它持久化的原理是把数据库中所有键值对的二进制数据直接写入到文件。RDB持久化的优先级一般低于AOF持久化，因为AOF持久化的实时性高于RDB，所以在系统启动的时候如果存在AOF持久化，redis会优先通过AOF持久化恢复数据。

执行持久化的操作指令是SAVE和BGSAVE，一个是前台执行，一个是后台执行。和AOF持久化一样，前台执行会阻塞当前redis进程，所有客户断请求都会被阻塞，因此一般建议是用BGSAVE，它也会新创建一个子进程来做持久化操作。RDB备份是全量备份。

可以在redis.conf中配置RDB相关的操作，主要有以下几个配置：

save <seconds> <changes>
dbfilename dump.rdb
dir ./

第一个配置是执行BGSAVE的策略，当在secnods秒之内执行了changes次操作时，会自动把改动写入到RDB文件。可以同时有多个save配置段存在，例如官方默认的配置中就有三个save配置：

save 900 1
save 300 10
save 60 10000

这三个配置，只要在任意时间段内满足了任意一条就会执行（三者互不影响，互相独立，各自备份各自的）：

1. 900秒内执行了一次更新，BGSAVE就会执行。
2. 300秒内执行了10次更新，BGSAVE就会执行。
3. 60秒呢执行了10000次更新，BGSAVE就会执行。

dbfilename和dir指定了备份文件名和路径，执行后就会把RDB文件写入到这个文件中。例如，设置保存的路径为/appdata/redis/dump.rdb，执行save命令后，就会生成这个文件：

RDB持久化文件可以使用官方的redis-check-rdb程序（低版本叫redis-check-dump）来检测相关数据：

当然，这个文件只提供了基本检测功能（即验证rdb文件是否合法），并不包含导出所有数据的功能。

如果需要处理实际的数据可以通过其他工具来实现，google一下redis rdb parser就能看到了。

github上也有很多，例如https://github.com/sripathikrishnan/redis-rdb-tools。

三、AOF和RDB对比

表格从Redis持久化AOF和RDB对比整理得来。

当使用的内存到达上限后，redis提供了6种策略来淘汰键值：

LRU是最近最少使用的，直译出来就是最久没有使用的。

redis默认的淘汰策略是volatile-lru，修改淘汰策略可以通过修改redis.conf文件中的maxmemory-policy字段，配置中关于各种淘汰策略也有详细的解释。使用grep volatile-lru redis.conf -A 6 -n可以过滤出这部分配置 ：

一、为什么要使用索引

索引是存储引擎用于快速找到记录的一种数据结构。索引对于数据库良好的性能十分关键，尤其是表中的数据量越来越大时，索引对性能的影响十分明显。

《高性能MySQL》中对索引的评价是：索引优化应该是对查询性能优化最有效的手段了，索引能够轻而易举将查询性能提高几个数量级。

以innodb为例，innodb中存储数据的基本元素是页，页里面保存了许多数据记录，各个记录通过链表串联起来。一个innodb页的结构为：

innodb给每个页分配了16KB的大小，除了存储用户记录以外还有一些额外的字段没有展示出来。用户记录并不是一定装满了整个页，因此除了用户记录以外还有一部分未使用的空间，后续的新纪录可以继续插入到未使用空间中。

除了页内的记录用链表串起来了之外，每个页面也是通过链表连接起来的：

试想正常情况下，如果想要找到一条记录应该怎么找呢？首先要遍历所有的页面，然后遍历页面里面的记录，一条条记录对比，找到需要查询的记录。这样的话时间复杂度是O(N)，N代表总的记录条数。

如果数据库中只有几条或者几十条记录，查起来或许还行。但是如果数据库有几千万甚至上亿条记录，这么查起来是什么样子？MySQL数据是写在磁盘上的，一次磁盘寻址所需要的时间是10ms，如果有1亿条记录，那么执行一次查询需要10亿毫秒，也就是1百万秒，算下来需要11.5天。这种级别的耗时是任何一个业务系统都无法忍受的。

而索引存在的意义就在于此，通过特定的结构来排布整个数据库，使得系统能在较快的时间内查询到记录。索引就像是一本书的目录，告诉你哪一章在哪一页，想看对应的章节直接放到对应页数就可以了。

一个最简单的索引思路是：把所有的记录排序，通过二分查找的方式来查找元素，查询的时间复杂度是O(logN)。这样的话1亿条记录，只需要20多次查询就可以了，算下来时间不到1秒，相比之前的11天已经不是一个数量级了。当然，实际的索引实现也不仅仅是二分查找这么简单。

最常用的索引有两种：

1. B-Tree索引，基于B+树结构的索引。
2. 哈希索引，基于哈希表实现的索引。

大部分时候，使用的都是B-Tree索引。

二、B-Tree索引

B-Tree索引是一种基于B+树结构的索引，B+树因为其独特的结构优势所以被广泛应用于索引中：

1. 一个节点包含了多个数据域，适应于操作系统成块访问磁盘的特性，可以一次读取多个节点的数据。
2. 相对于B树来说，B+树非叶子节点不包含任何数据，只包含子节点指针 ，因此一个节点所能指向的子节点个数更多，这样的话B+树会更矮，查询起来更高效。

一个B-Tree索引的结构为（橙色是数据域，绿色是子节点指针）：

如果想要找到id等于32的记录，首先通过页1定位到子页10，然后继续查找页10，定位到页31，最终找到32。

可以看出，查找的效率是与B+树的层数相关的，树越高，查找效率越慢，树越低，查找效率越快。实际的应用中，一个页远远不止上面展示的3个记录项，按照一行记录100字节来算，一页数据（16K）至少可容纳1500个记录，那么1亿条记录只需要三层树（10^9<1500*1500*1500）。也就是说，1亿条数据最多执行三次IO就能定位到，可见其效率之高。

索引除了可以按值查找以外，还支持对ORDER BY子句的排序，只要排序字段也正确匹配上了索引就可以。

B-Tree支持的索引匹配条件：

1. 全部匹配：支持同时匹配多个索引。
2. 部分匹配：支持同时匹配多个索引中的部分索引。
3. 匹配列前缀：对添加了索引的列，可以匹配其左前缀。例如匹配maqian中的前缀ma。
4. 匹配范围：支持对索引列去范围值。

三、哈希索引

哈希索引是一种基于哈希表的索引结构，它是一种需要精确匹配才生效的索引结构。

实现原理：对索引列计算哈希值把记录映射到哈希槽中，然后指向对应记录行的地址。因此，在查询的时候只要正确匹配到索引列，就能在O(1)的时间复杂度内查到记录。

以下是一个哈希索引的示例，左边是哈希槽，右边是对应的数据列：

相比于B-Tree索引而言，哈希索引有不少的局限性：

• 哈希索引不支持排序
• 哈希索引不支持部分列索引查找
• 哈希索引只支持等值查询，无法提供范围查询功能

哈希索引的查找效率是非常高的，大多数时候都能在O(1)的时间内找到记录，除非哈希冲突很高。

innodb中有一个内建功能叫自适应哈希，当存储引擎注意到有列频繁访问的时候，就会建立对应的哈希索引。这样，引擎就同时拥有了B-Tree索引和哈希索引，就能使用更加快速的查找。这是一个无需人工干预的自动行为。

哈希索引使用的场景

哈希索引常见的一种场景是针对长字符串查询的优化，例如数据库中保存了大量的URL信息，查询URL中不可能一个字符一个字符去搜索，这样效率太低。

这种情况就可以使用哈希索引：给所有的URL计算一个crc保存起来，然后对crc做哈希索引。查询的时候指定crc和url就能快速定位到记录了。如：

select * from url_info where crc = xxxx and url = "http://www.baidu.com"

执行这条语句的时候，会先针对crc查找哈希索引，找出所有crc值等于xxxx的记录，过滤掉大多数不符合条件的记录。然后再根据后面的url信息详细匹配，这样查询效率就很高了。

四、索引的缺点

所有的优点是查询速率很快，但同时也有缺点。

索引的主要缺点是会导致插入和更新语句变慢，因为每次更新数据都要重新维护索引，索引越多，耗时越长。

同时，如果建立了不恰当的索引可能还会导致数据库性能更低，这个就依赖人工的操作了。

一、链表定义

链表在redis中的使用十分广泛，例如列表的底层实现之一就是链表，包括发布、订阅等等功能都是有用到链表的。redis中链表在adlist.h和adlist.c中实现，只用了300+行代码，十分简单。

redis中的链表是一个双向不循环的链表，两个核心的数据结构是listNode和list，其中listNode的定义如下：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

listNode是链表节点定义，链表节点和平常用到差别不大，由一个数据域和两个分别指向前后节点的指针组成。

list的定义为：

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned int len;
} list;

它和普通链表定义的不同点在于：除了包含首尾指针以及链表长度以外，链表的结构还包含了3个函数指针结构：

• dup: 用于拷贝节点的函数。
• free: 用于释放节点的函数。
• match: 用于对比节点是否相等的函数。

链表的宏观结构：

二、链表操作

2.1 链表创建和释放

初始化的过程主要是创建链表对象，并初始化值：

list *listCreate(void)
{
    struct list *list;

    // 分配内存空间
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;

    // 初始化成员
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

释放链表：

void listRelease(list *list)
{
    unsigned int len;
    listNode *current, *next;

    current = list->head;
    len = list->len;

    // 循环遍历链表
    while(len--) {
        next = current->next;
        // 如果有自定义的free函数，先调用函数释放节点内部数据
        if (list->free) list->free(current->value);
        // 释放节点
        zfree(current);
        current = next;
    }

    // 释放链表
    zfree(list);
}

2.2 插入节点

插入节点提供了三个函数，分别是从头部插入、从尾部插入以及从指定位置插入。

头插法：

list *listAddNodeHead(list *list, void *value)
{
    listNode *node;

    // 给新插入的节点分贝内存空间并赋值
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;

    // 插入节点
    if (list->len == 0) {
        // 链表为空的时候要给首尾指针赋值
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        // 插入节点到链表
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }

    // 长度加1
    list->len++;

    return list;
}

尾插法，和头插法基本一致：

ist *listAddNodeTail(list *list, void *value)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

插入节点到指定位置：

/*
 * 参数说明
 * @list 链表对象
 * @old_node 被插入的节点
 * @value 新插入节点的数据域
 * @after 是查到节点的后面还是前面
 * @return 插入成功后返回传入的链表对象，否则返回NULL
 */
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;

    // 创建新节点并赋值
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;

    // 插入节点
    if (after) {
        // 插入到old_node节点后
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        // 插入到old_节点前
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {
            list->head = node;
        }
    }
    
    // 修改前一个节点的next指向
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    // 修改后一个节点的prev指向
    if (node->next != NULL) {
        node->next->prev = node;
    }
    // 链表长度加1
    list->len++;

    return list;
}

2.3 删除节点

void listDelNode(list *list, listNode *node)
{
    if (node->prev) // 删除的不是头结点，修改前一个节点的next指针
        node->prev->next = node->next;
    else // 删除的是头结点，更新head指向
        list->head = node->next;

    if (node->next)
        node->next->prev = node->prev;
    else // 删除的是尾结点，更新next指向
        list->tail = node->prev;
    // 存在节点的free函数，调用函数释放节点内部资源
    if (list->free) list->free(node->value);
    zfree(node);
    list->len--;
}

三、链表遍历

redis在实现链表的时候，给链表的遍历单独创建了一套结构和方法。其中遍历的结构是listIter，它包含了一个listNode *的指针域和遍历方向direction：

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

direction的作用是标记遍历方向是从头部往尾部遍历还是从尾部往头部遍历，获取一个listIter的方法：

listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL)
        return NULL;

    if (direction == AL_START_HEAD)
        iter->next = list->head; // 从头往尾遍历，iter指向头结点
    else
        iter->next = list->tail; // 从尾往头遍历，iter指向尾结点
    iter->direction = direction;
    return iter;
}

配合listNode获取下一个节点的函数：

listNode *listNext(listIter *iter)
{
    // 保存当前指针
    listNode *current = iter->next;

    // 
    if (current != NULL) {
        if (iter->direction == AL_START_HEAD)
            iter->next = current->next; // 赋值下一个节点到iter
        else
            iter->next = current->prev; // 赋值前一个节点到iter
    }
    return current;
}

注意listNext函数只是获取当前iter指向的节点，并把iter指向下一个节点。为什么要把遍历操作单独抽离出来呢？

主要有以下几个目的：

1. 外部遍历时不用重复编写遍历代码。前面已经说过，链表在redis很多场景都用到了，所有的结构共用一套遍历实现就可以了。
2. 外部遍历的时候无需访问list的内部元素，充分做到了面向对象的理念。

四、其他

4.1 链表拷贝

list *listDup(list *orig)
{
    list *copy;
    listIter *iter;
    listNode *node;

    // 为新链表创建内存空间
    if ((copy = listCreate()) == NULL)
        return NULL;
    // 初始化
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    // 遍历
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        void *value;

        if (copy->dup) {
            // 如果存在复制函数，使用自定的复制函数来复制每个节点
            value = copy->dup(node->value);
            if (value == NULL) {
                // 复制失败，释放掉前面已经拷贝成功的节点，避免内存泄漏
                listRelease(copy);
                listReleaseIterator(iter);
                return NULL;
            }
        } else
            value = node->value;

        // 新拷贝的节点插入到链表结尾
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            listReleaseIterator(iter);
            return NULL;
        }
    }
    listReleaseIterator(iter);
    return copy;
}

4.2 链表查找

listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;
    listNode *node;

    // 遍历链表
    iter = listGetIterator(list, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        if (list->match) {
            // 使用自定义的比较函数来比较每个节点和查找的key
            if (list->match(node->value, key)) {
                listReleaseIterator(iter);
                return node;
            }
        } else {
            // 使用默认的比较函数来比较节点和key
            if (key == node->value) {
                listReleaseIterator(iter);
                return node;
            }
        }
    }
    listReleaseIterator(iter);
    return NULL;
}

4.3 返回指定位置上的元素

传入索引，返回对应位置上的元素，支持从尾部索引：

listNode *listIndex(list *list, int index) {
    listNode *n;

    if (index < 0) {
        // index小于0，从尾部开始索引
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    } else {
        // index大于0，从头部开始索引
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
}

五、总结

收获很大，主要是两个地方感触很深：

1. 链表的遍历
2. 从尾部开始返回对应索引位置上面的元素

其实实现并不算难，只是实现的思路和想法很新颖，很值得学习！

一、LRU算法描述

LRU全称是Least Recently Used，最近最少使用的意思，是一种常用的内存置换算法。当内存不够的时候，要把部分内存写入到磁盘中，此时就要用到LRU算法来决定把那部分内存写入到磁盘。

当把内存数据写入到磁盘的时候，肯定是把不常用的内存置换到磁盘这样才是最优的。不然把常用的内存写入磁盘，然后又频繁从磁盘读出来，明显会降低系统性能。LRU的核心思想就是把最近最少使用的内存置换到磁盘中去。

一般来说，实现LRU算法都是使用哈希表+链表来实现，这样可以使得LRU操作的时间复杂度是O(1)。具体的过程描述为：

1. 传入内存地址，通过哈希表判断内存是否已经存在于链表了。如果内存存在，把节点移到链表开头。

2. 如果内存不存在于哈希表中，有两种情况：

   • 链表没满，把节点插入链表开头。
   • 链表满了，淘汰掉链表末尾节点，当前节点插入到链表开头。

哈希表中记录的是内存和链表节点的对应关系，这样当一个内存地址传入的时候，在O(1)的时间内就能确定该内存地址是否已经存在于缓存中了。如果没有哈希表，那么每次判断内存是否存在于缓存的时候都要遍历链表查询，需要时间复杂度为O(n)。

LRU图解

假设存在一个缓存容量为5的缓存区，当前已经缓存了1、4、8、9四块内存：

访问内存块3，因为缓存中不含有这块内存，要把3加到缓存中去：

访问内存块5，因为5不存在于缓存中，要把5插入到缓存。但是目前链表已经满了，不能容纳更多的节点，所以必须把最后的节点淘汰掉，也就是去掉9：

访问内存块1，1已经存在于缓存了，把它放到链表最前面来：

二、代码描述

2.1 lru对象设计

实现LRU需要用到双向链表+哈希表：

• 哈希表保存了每个缓存节点的地址，可以直接使用STL中的map。
• STL中也有双向链表，可以直接使用这个链表结构。

一个LRU缓存对象需要包含的方法：

• get()：从缓存获取一块内存
• put()：存放一块内存到缓存

LRU对象设计：

// 缓存的数据
typedef pair<int, int> cache_val;

class lru_cache {
private:
    // 链表
    list<cache_val> l;
    // 哈希表
    map<int, list<cache_val>::iterator> m;
    // 链表的容量和长度
    size_t cap, len;
public:
    // 构造函数
    lru_cache(size_t cap) : cap(cap), len(0) {}
}

2.2 get函数实现

get函数的实现：

int get(int key) {
    cache_val cache;
    map<int, list<cache_val>::iterator>::iterator it;

    it = m.find(key);

    // 没有找到，返回-1
    if (it == m.end())
        return -1;

    // 找到了，移到最前面去
    cache = *(it->second);
    // 先删除
    m.erase(key);
    l.erase(it->second);

    // 再插入
    l.push_front(cache);
    m.insert(pair<int, list<cache_val>::iterator>(key, l.begin()));
    return it->second->second;
}

2.3 put函数实现

put`函数的实现：

void put(const int &key, const int val) {
    cache_val cache;
    map<int, list<cache_val>::iterator>::iterator it;
    it = m.find(key);

    // 找到了缓存
    if (it != m.end()) {
        // 移到链表开头
        cache = *(it->second);
        l.erase(it->second);
        l.push_front(cache);
        // 重新修改哈希表的指向
        m.erase(key);
        m[key] = l.begin();
        return;
    }

    // 下面是没有找到缓存，要插入新的节点到链表和哈希表
    // 链表的长度已经超过容量了
    if (len >= cap) {
        // 哈希表移除节点
        m.erase(l.back().first);
        // 链表移除末尾节点
        l.pop_back();
    }

    cache = pair<int, int>(key, val);
    l.push_front(cache);
    m.insert(pair<int, list<cache_val>::iterator>(key, l.begin()));

    if (len < cap)
        len++;
}

三、单元测试

测试案例：

TEST(lru_cache, leetcode) {
    lru_cache cache = lru_cache(2);

    cache.put(1, 1);
    cache.put(2, 2);
    EXPECT_EQ(1, cache.get(1));       // 返回  1

    cache.put(3, 3);    // 该操作会使得密钥 2 作废
    EXPECT_EQ(-1, cache.get(2));

    cache.put(4, 4);    // 该操作会使得密钥 1 作废
    EXPECT_EQ(-1, cache.get(1));
    EXPECT_EQ(3, cache.get(3));
    EXPECT_EQ(4, cache.get(4));
}

本篇文章是基于前篇《数据结构之链表（一）：单向链表》实现的，和单向链表重复的细节这里不再描述。

一、双向链表

双向链表和单向链表类似，唯一的区别是链表节点中除了有指向下一个节点的指针以外，还有一个指向上一个节点的指针。

节点的定义：

template<typename T>
class list_node {
public:
    friend class doubly_linkedlist<T>;
private:
    T data;
    list_node<T> *prev; // 指向前一个节点
    list_node<T> *next; // 指向后一个节点
};

链表的定义：

template<typename T>
class doubly_linkedlist {
public:
    doubly_linkedlist() : head(nullptr), tail(nullptr), len(0) {}
private:
    size_t len; // 链表长度
    list_node<T> *head; // 头节点
    list_node<T> *tail; // 尾结点
};

二、插入操作

双链表的插入操作和单链表基本没有差别，就只是多了一个修改prev节点的步骤。

以下是添加节点node2的过程：

操作主要有两步：

1. 修改node2的prev和next指向，分别指向前后节点。
2. 修改前节点node1的next指针指向node2，修改后节点node2的prev指针指向node2。

插入函数实现：

/*
 * 添加节点操作
 * @new_node 新节点，不为空
 * @prev 前驱节点
 * @next 后继节点
 */
void add_node(list_node<T> *new_node, list_node<T> *prev, list_node<T> *next) {
    if (new_node == nullptr)
        return;
    
    len++;
    new_node->next = next;
    new_node->prev = prev;

    if (prev) {
        prev->next = new_node;
    }

    if (next) {
        next->prev = new_node;
    }
}

实现了这个函数之后，单链表中所有的头插、尾插函数都不用修改了，直接调用这个函数就完成了。

其实后面的删除元素也是一样，前面所说的把添加和删除逻辑抽离出来的好处就在这里。

三、删除操作

删除node2节点的操作步骤：

过程描述：

1. 删除node2的prev和next指针指向。
2. 修改node1的next指针指向node3，修改node3的prev指针指向node1。

删除代码实现：

void remove_node(list_node<T> *del_node, list_node<T> *prev, list_node<T> *next) {
    len--;
    del_node->next = nullptr;
    del_node->prev = nullptr;

    if (prev) {
        prev->next = next;
    }

    if (next) {
        next->prev = prev;
    }
}

四、双向循环链表

双向循环链表是在双向链表的基础上增加了循环机制，即链表的尾结点要连接上首节点，链表的首节点要连接上尾结点。循环链表的示意图：

《算法导论》中实现双向循环链表的方法是引入一个哨兵节点，这个节点不包含任何数据信息，只作为首尾相连的用途：

实际上也就是一个NULL值，和双向链表没有很大区别。