数据结构-链表

链表概念

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


特点

效率

  • 插入: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 实现循环了。


思维导图

数据结构-链表-思维导图.png

Next