代码随想录算法训练营第三天 | 熟悉链表

链表的存储方式

• 数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
• 链表是通过指针域的指针链接在内存中各个节点。
• 所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

链表的定义

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 = valself.next = next