【数据结构】链接列表 Linked list

链接列表(Linked list)

链接列表 是 数据元素的线性集合,但是 并不会按照 线性的顺序存取数据。相反的是,每个元素 指向 另一个元素。链接列表是一个由一组代表了线性的节点组成的的数据结构。最简单的情况下,每个节点 由 数据 和 指向另一个节点的指针 组成。

基础概念

链接列表中每条记录被称为  元素(element)或者 节点(node);每个节点上 包含下一个节点地址 的字段 被叫做 下一个链接(link)或者 下一个指针(pointer);剩下的字段被称为 数据(data),信息(information),或者值(value)等。

链接列表可以用来实现其他常见的几种 抽象数据类型,包括  lists, stacks, queues, associative arrays ;

优点

插入 和 删除的时间复杂度为 O(1);

缺点

  • 查询元素的时间复杂度为 O(n)。
  • 比 数组数据结构 需要更多的 内存,因为需要保存他们使用的指针。
  • 链接列表中的节点 必须 从一开始 就 顺序读取,因为链表 本身就是 顺序访问的。
  • 由于节点的不连续存储,极大的增加了访问列表中单个元素所需的周期,尤其是 CPU 缓存。
  • 链接列表 在 反向遍历时也会有困难。例如,对于单向链表反向遍历会很繁琐,但是 双向链表相对容易一点,这个时候内存会被分配存储 后指针。

种类

  • 单向链接列表(Singly linked list)

包含两个字段:一个整数值 和  指向下一个节点的 链接  的 单向链接列表如下图:


  • 双向链表(Doubly linked list)

包含三个字段:一个整数值,一个指向下一个节点的链接 和 返回到前一个节点的链接


  • 循环链表


其他链表等;

相关文章
相关标签/搜索