链表

链表，是一种通过指针串联在一起的线性结构，每个节点由两部分组成，一个是数据域，一个是指针域，最后一个节点的next指针域指向null(空指针的意思)

链表类型：

1、单链表，包含数据域和next指针域,next指针只能指向当前节点的下一个节点

单链表

2、双链表，每个节点由数据域和两个指针域，一个指向下一个节点，一个指向上一个节点

即可以向前查询，也可以向后查询

双链表

3、循环链表，即：链表首尾相连

循环链表

链表的存储方式：

数组在内存中是连续分布的，但是链表在内存中不是连续分布的，而是散乱分布的，分配机制取决于操作系统的内存管理。

链表的操作：

添加节点

删除节点

性能分析：

插入/删除(时间复杂度) O(1)

查询(时间复杂度) O(n)

适用场景：数据量不固定，频繁增删，较少查询