山西大同专业网站建设制作价格新版阿里指数官网
链表
通过指针串联在一起的线性结构，每个节点由数据域和指针域两部分组成。链表节点在内存中的存储通常不是连续的，各节点通过指针连接在一起，其内存分布大致如下图所示。
定义
单链表
struct ListNode {// DATATYPE 可以是任意存放数据的类型，如int, string等DATATYPE val; ListNode *next;ListNode(DATATYPE v) : val(v), next(nullptr) {}
};
双链表
双链表节点定义比单链表节点多一个指向前驱节点的指针域。
struct ListNode {DATATYPE val;ListNode *prev;ListNode *next;ListNode(DATATYPE v) : val(v), prev(nullptr), next(nullptr) {}
};
删除
在单链表中，删除一个节点，需要将该节点的前驱元素的 next 指针指向，该节点的后继元素。如果删除节点为头节点，则仅需找到正确的头节点即可。
插入
在单链表中，插入与删除相反，但仍需要找到插入的位置。将插入节点的 next 指针指向插入位置的后继节点，将插入位置的前驱节点指向插入节点。如果是头节点，则仅需要将插入节点指向原来头节点，将头节点标记为当前插入节点。
总结
链表在插入和删除上的时间复杂度为 O(1)，在查询上的时间复杂度为 O(n)。
适用于数据量不固定，频繁增删，少量查询的场景。
解题技巧
- 额外的数据结构（哈希表）；
- 快慢指针；
- 虚拟头节点；
面试&笔试
在面试和笔试中，对算法的要求应有所区分。
在笔试中，题量多时间少，我们要尽量采取写出容易想到并且时间复杂度符合要求的算法，通常可以以空间换时间。
而在面试中的题，通常难度更小，为了给面试官留下深刻的影响，应尽量写出低时间复杂度，低空间复杂度，能体现代码水平的代码。
Reference
通常难度更小，为了给面试官留下深刻的影响，应尽量写出低时间复杂度，低空间复杂度，能体现代码水平的代码。
Reference
- 代码随想录 (programmercarl.com)