链表的每个节点由两部分组成：1.数据域 2.指针域（存放指向下一个节点的指针）最后一个节点的指针域指向NULL

链表的类型：

  1. 单链表：指针域只能指向节点的下一个节点。

  2. 双链表：每一个节点既有指向前一个节点的指针域，也有指向后一个节点的指针域。既可以向前查询，也可向后查询

3. 循环链表：链表首尾相连。可以用来解决约瑟夫环问题

链表的存储方式

区别：数组在内存中是连续分布的，链表在内存中不是连续分布

链表通过指针域的指针链接内存中各个节点


链表的定义

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

链表的操作

删除D节点：只需把C节点的指针域指向E节点，再释放D节点(Java、Python，就有自己的内存回收机制，就不用自己手动释放了。)

删除第4个节点，需要从头节点查找到第3个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

添加节点