2、链表

定义

链表是一系列的存储数据元素的单元通过指针串接起来形成的，故链表通常包含数据域与指针域两部分，合起来叫节点。
链表可以通过节点一个个遍历下去，只有尾节点的next为null，其他的都不为空。
链表主要包括单向链表、双向链表和循环链表。

单向链表

单向链表只有一个指针域，并指向下一个节点。
图片说明
图片说明
单向链表只能通过前找到后，无法通过后找到前，即为单向。
优点：

  • 插入、删除灵活。
  • 有元素才会分配节点空间，不会有闲置的节点（顺序存储未存满，就会有闲置的空间）。
    缺点：
  • 比顺序结构密度小，因为要同时存储指针。
  • 查找比顺序存储慢，无法随机查找。

    双向链表

    双向链表同时拥有前驱指针域与后驱指针域，可同时指向前节点与后节点。
    图片说明
    图片说明

    循环链表

    循环链表又被称作环，是头节点与尾节点连接在一起的链表，其头节点叫做环的入口。
    图片说明
    图片说明