链表的存储方式
- 数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
- 链表是通过指针域的指针链接在内存中各个节点。
- 所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
链表的定义
template <typename T>
struct LinkNode //单链表结点类型
{
T data; //存放数据元素
LinkNode<T>* next; //下一个结点的指针
LinkNode():next(NULL){} //构造函数
LinkNode(T d):data(d),next(NULL){} //重载构造函数
};
链表的操作
删除节点
注意：如上图所示，如果直接将C指向E，实际上D节点依然在内存中，所以需要手动释放，
但是其他语言例如python，Java有自己的内存回收机制
添加节点
可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。
但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。
链表的好处：
- 数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。
- 链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
其他语言版本的节点构造：
C++：
class ListNode {
val;
next = null;
constructor(value) {
this.val = value;
this.next = null;
}
}
python:
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next