2.2 数组列表
2023-09-14 09:06:54 时间
@[toc]
emsp;emsp;对于java程序员来说,数组列表可能是用得最多的了,对于年限比较高的程序员来说,ArrayList都写吐了,哈哈。数组列表的出现是为了克服链表的一些缺点而诞生的。链表这个数据结构虽然好用,但是也存在一个最重要的缺点,就是按索引访问比较慢,需要按照引用或者指针去循环检索。为此,才有了数组列表。数组列表内部实现是一个数组,内部有个字段记录最后一个元素所在的数组索引。添加元素直接在在这个位置后添加。当数组满了的时候就对数组进行扩容。
emsp;emsp;扩容的方法是长度加一然后翻倍。
emsp;emsp;但是数组列表,也有缺点,就是从头部删除,需要将所有元素前移,性能十分低下。
emsp;emsp; 其数据字段如下图:
emsp;emsp; 数组列表代码比链表简单,我这里贴一下Java代码:
public class ArrayList<T> {
private Object[] data = new Object[0];
private int index;
public void addLast(T value) {
ensureCapacity();
data[index++] = value;
}
public T removeLast() {
return (T) data[index--];
}
public void addFirst(T value) {
ensureCapacity();
System.arraycopy(data, 0, data, 1, index);
data[0] = value;
index++;
}
public T removeFirst() {
T temp = (T) data[0];
System.arraycopy(data, 1, data, 0, data.length - 1);
index--;
return temp;
}
public T get(int index) {
return (T) data[index];
}
private void ensureCapacity() {
if (index >= data.length) {
Object[] array = new Object[(data.length + 1) << 1];
System.arraycopy(data, 0, array, 0, data.length);
data = array;
}
}
}
emsp;emsp;同样,对于数组列表,不建议自己实现,而是建议使用各个语言官方库里的实现。比如java有ArrayList实现。
相关文章
- python基础知识-列表的排序问题
- 列表滚动加载(静态)
- 在Python的列表中利用remove()方法删除元素的教程
- 列表 数组 哈希表
- 过滤列表或命令的输出的项
- 仿listBox写了一个Control控件为item的列表集合
- 599. 两个列表的最小索引总和(数组)
- python3将列表当作队列使用
- 168. 用 SAP UI5 Select 控件(下拉列表),来驱动表格控件(Table)刷新的一个实战例子
- 89. 如何给 SAP UI5 列表控件增添多个图形界面的过滤器
- SAP Spartacus B2B user列表对应的Angular Component
- Android 简单数组适配器+下拉列表
- 支持DevOps和功能安全/信息安全的静态代码分析器 Klocwork——工具简介|原厂简介|客户列表
- 散列表在PAT中的应用,例题:1041,1050,1084
- css案例11——去除列表默认小黑点
- uni-app 实现数据列表(右带默认箭头)的功能(点击item 背景色改变)
- 【Python】列表循环修改索引
- 第8讲:Python中列表的概念与基本使用