5. 理论讲解：数组、链表（Array、Linked List）
2018-11-21 本文已影响0人
博士伦2014
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)
