数组与链表
2023-02-01 本文已影响0人
iOS小洁
数组
数组是一种顺序存储的线性表，所有元素的内存地址是连续的
缺点：
- 无法动态修改容量
- 造成空间浪费
动态数组
可以动态修改数组容量
复杂度：最好：O(1) 最坏：O(n) 平均：O(1) 均摊：O(1)
均摊复杂度：经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况
复杂度震荡：扩容倍数、缩容时机设计不得当，有可能会导致复杂度震荡
链表
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
双向链表
双向链表比单向链表的效率更高。在删除操作中，操作数量可以减少近一半
单向链表删除操作，平均复杂度1/2 + n/2
双向链表删除操作，平均复杂度1/2 + n/4
发挥链表最大威力
可以考虑增设1个成员变量、3个方法
- current ：用于指向某个节点
- void reset() ：让 current 指向头结点 first
- E next() ：让 current 往后走一步，也就是 current = current.next
- E remove() ：删除 current 指向的节点，删除成功后让 current 指向下一个节点
链表练习
线性结构接口设计
数组链表需要实现的公共接口如下：
public interface List<E> {
static final int ELEMENT_NOT_FOUND = -1;
/**
* 清除所有元素
*/
void clear();
/**
* 元素的数量
* @return
*/
int size();
/**
* 是否为空
* @return
*/
boolean isEmpty();
/**
* 是否包含某个元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到尾部
* @param element
*/
void add(E element);
/**
* 获取index位置的元素
* @param index
* @return
*/
E get(int index);
/**
* 设置index位置的元素
* @param index
* @param element
* @return 原来的元素ֵ
*/
E set(int index, E element);
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
void add(int index, E element);
/**
* 删除index位置的元素
* @param index
* @return
*/
E remove(int index);
/**
* 查看元素的索引
* @param element
* @return
*/
int indexOf(E element);
}
数组链表公共方法如下：
public abstract class AbstractList<E> implements List<E> {
/**
* 元素的数量
*/
protected int size;
/**
* 元素的数量
* @return
*/
public int size() {
return size;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 是否包含某个元素
* @param element
* @return
*/
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}
/**
* 添加元素到尾部
* @param element
*/
public void add(E element) {
add(size, element);
}
protected void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
protected void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
protected void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
}
动态数组与链表对比
复杂度对比
| 动态数组 | 链表 | |||||
|---|---|---|---|---|---|---|
| 最好 | 最坏 | 平均 | 最好 | 最坏 | 平均 | |
| add(int index, E element) | O(1) | O(n) | O(n) | O(1) | O(n) | O(n) |
| remove(int index) | O(1) | O(n) | O(n) | O(1) | O(n) | O(n) |
| set(int index, E element) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) |
| get(int index) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) |
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容解决）
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费
如何选择：
- 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
- 如果频繁在头部进行添加、删除操作，建议选择使用双向链表
- 如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
- 如果有频繁的查询操作（随机访问操作），建议选择使用动态数组
