链表
链表与顺序表的优劣
链表的优点:
插入删除比较快。没有空间限制。
链表的缺点:
存取速度比较慢。不连续存放,浪费空间。
使用场景
链表:频繁的插入和删除操作很少的查询。 顺序表:频繁的查找却很少的插入和删除操作。
读取数据的顺序
链表:随机存储,顺序读取。 顺序表:顺序存储,随机读取。
链表常用的操作
cur 为当前节点。node 为操作节点。
单链表
增加 (node 加在cur的后面)
node
.next = cur
.next
cur
.next = node
删除
cur
.next = cur
.next.next
双链表
增加(node 加在 cur 前面)
node
.next = cur
node
.pre
= cur
.pre
cur
.pre
.next = node
cur
.pre
= node
删除
cur
.pre
.next = cur
.next
cur
.next.pre
= cur
.pre
常见面试题
leetcode 876. 链表的中间结点leetcode 147. 对链表进行插入排序leetcode 142. 环形链表 IIleetcode 426. 将二叉搜索树转化为排序的双向链表leetcode 23. 合并K个排序链表leetcode 25. K 个一组翻转链表