1. Array

图 1 图 2

两种常见的数组操作：插入和删除
复杂度：
• Access: O(1)
• Insert: 平均 O(n)
• Delete: 平均 O(n)

特点：查询操作快，插入删除慢

2. Linked List

图 3.链表 图 4 图 5.链表插入一个元素 图 6. 链表删除一个元素

2.1 Doubly Linked List

图 7. 双链表
特点：查询操作慢，插入删除很快

3. 时间复杂度

space     O(n)
prepend   O(1)
append    O(1)
lookup    O(n)
insert    O(1)
delete    O(1)

4. 练习题目

1. https://leetcode.com/problems/reverse-linked-list/
2. https://leetcode.com/problems/swap-nodes-in-pairs
3. https://leetcode.com/problems/linked-list-cycle
4. https://leetcode.com/problems/linked-list-cycle-ii
5. https://leetcode.com/problems/reverse-nodes-in-k-group/