链表，一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域，一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针）。

链表的入口节点，链表的头节点，head

链表的类型：

• 单链表
• 双链表
• 循环链表

链表节点的定义：

定义链表节点方式：

// 单链表
struct ListNode {int val;  // 节点上存储的元素ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

若自定义构造函数，初始化节点，那么在初始化的时候能直接给变量赋值。若采用默认构造函数初始化节点，那么则不能直接给变量赋值。

自定义构造函数初始化节点：

ListNode* head = new ListNode(5);

链表的操作

删除节点：将一个节点的next指针指向另一个节点。同时，需要手动释放该节点的内存。

添加节点：链表的增添和删除都是O(1)操作，不影响其他节点。但，若删除第五个节点，则需要从头节点查找到第四个节点，通过next指针进行删除操作，查找的时间复杂度是O(n)。

这里需要注意：删除操作和查找再删除操作，实际意义不同。

 注意：

数组，在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表，长度是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。