数据结构-链表

链表概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

特点

效率

• 插入：O（1）
• 访问：O（n）

由于不必须按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间。

优点

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

缺点

链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

常见的链表

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

单向链表

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

链表是由结点构成，head 指针指向第一个成为表头结点，而终止于最后一个指向 NULL 的指针。

单向链表组成

• 存储数据元素的数据域
• 直接后继的指针

定义结构体

type Element struct {
    // 后继节点
    next *Element

    // 节点所属链表 list
    list *List

    // 节点存储的值 Value
    Value interface{}
}

单向循环链表

和单向链表类似，只是最后一个节点可以指向首节点。

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表组成

• 存储数据元素的数据域
• 直接后继的指针
• 直接前驱的指针

定义结构体

type Element struct {
    // 前驱和后继节点
    next, prev *Element
    
    // 结点所属的链表 list
    list *List
    
    // 结点里储存的值 Value
    Value interface{}
}

双向循环链表

和双向链表类似，只是在实现中存在一个 root 节点是链表第一个元素的前驱，root 节点也是链表最后一个元素的后继，这样双向循环链表就可以通过一个 root 实现循环了。

思维导图