Java 数据结构深入理解ArrayList与顺序表

Java 数据结构深入理解ArrayList与顺序表

目录一、ArrayList简介二、ArrayList的使用1、ArrayList的构造2、ArrayList的遍历3、ArrayList的常见操作(方法)4、ArrayList的扩容机制三、模拟实现一个顺序表(Object[])

一、ArrayList简介

在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：

ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。

二、ArrayList的使用

1、ArrayList的构造

方法使用ArrayList()无参构造ArrayLhttp://ist(Collection extends E> c)利用其他 Collection 构建 ArrayListArrayList(int initialCapacity)指定顺序表初始容量

public static void main(String[] args) {

// 无参构造

List list1 = new ArrayList<>();

// 给定初始容量

List list2 = new ArrayList<>(10);

// 使用另外一个 ArrayList对其初始化

LXqQIsaist list3 = new ArrayList<>(list2);

list1.add(1);

list1.add(2);

list1.add(3);

// 其父类 AbstractCollection重写了 toString方法

System.out.println(list1);// 输出 [1, 2, 3]

}

2、ArrayList的遍历

1、遍历顺序表

2、for - each（实现了Iterable接口）

3、迭代器（实现了Iterable接口）

// 遍历顺序表

for (int i = 0; i < list.size(); i++) {

System.out.print(list.get(i));

}

// for - each 遍历

for (StrinXqQIsag s : list) {

System.out.print(s);

}

// 迭代器打印

// 获取迭代器对象

Iterator iterator = list.iterator();

while (iterator.hasNext()) {

// 获取下一个对象

String next = iterator.next();

// 打印

System.out.print(next);

}

// listIterator ---- 实现了 Iterator 接口

ListIterator iterator2 = list.listIterator();

while (iterator2.hasNext()) {

String next = iterator2.next();

System.out.print(next);

}

这里的 listIterator 实现了 Iterator 接口，从方法上，listIterator 有更多的功能（方法），例如在遍历的时候，进行添加元素 add()。

ListIterator iterator2 = list.listIterator();

while (iterator2.hasNext()) {

String next = iterator2.next();

if (next.equals("hello")) {

iterator2.add("三团");// 在 hello 的后面添加 三团

}else{

System.out.print(next + " ");

}

}

System.out.println(list);// [hello, 三团, bit, world]

3、ArrayList的常见操作(方法)

方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection extends E> c)将集合 c 中的元素 尾插到该集合中E remove(int index)删除 index 位置元素并返回boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空顺序表boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标List< E > subList(int fromIndex, int toIndex)截取部分 list

List list = new ArrayList<>();

List listAdd = new ArrayList<>();

listAdd.add("hello");

listAdd.add("world");

listAdd.add("你好~");

list.add("哈哈");// 尾插元素

list.add(0,"你好"); // 0 下标插入 "你好 "

list.addAll(listAdd);// 将集合 listAdd 中的元素尾插到该集合中

String s = list.remove(0);// 删除 index 位置元素并返回

boolean s2 = list.remove("hello");// 删除遇到的第一个 hello，没找到则返回 false

list.set(0,"we");

list.indexOf("we");//返回第一个 "we" 所在下标

list.lastIndexOf("we");// 返回最后一个 "we" 的下标

System.out.println(list);

// 截取子串 -- 左闭右开区间

List sub = list.subList(1, 3);

System.out.println(sub);

list.set(2,"修改后的list");

System.out.println(sub);

注意： 这里的 subList方法，并不是真正的返回一个截取部分的新地址，而是将原地址的截取部分返回，所以当修改原来的线性表中的元素时，子串中的内容也会发生改变。

4、ArrayList的扩容机制

1、当调用无参构造时，即List< String > list = new ArrayList<>()，底层还没有分配真正的内存（初始化是一个空数组），初始容量为 0。当第一次添加元素（调用 add 方法） 时，整个顺序表的容量被扩充为10，放满后，以 1.5 倍扩容。

2、当调用带容量的构造方法时，例如 List< String > list = new ArrayList<>(16)，顺序表初始容量就为16，放满后以 1.5 倍扩容。

结论

如果调用无参构造方法，顺序表初始大小为0，当第一次放入元素时，整个顺序表容量变为10，当放满10个元素，进行1.5倍扩容。

如果调用给定容量的构造方法，初始大小就是给定的容量，当放满了，就进行1.5倍扩容。

三、模拟实现一个顺序表(Object[])

public class MyArrayList {

private Object[] elementData;// 数组

private int usedSize;// 代表有效的数据个数

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public MyArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

public MyArrayList(int capacity) {

// 判断参数的合法性

if (capacity >= 0) {

this.elementData = new Object[capacity];

}else {

throw new RuntimeException("初始化的容量不能为负数！");

}

}

/**

* 添加元素

* @param e 要添加的元素

*/

public boolean add(E e) {

// 确定一个真正的容量,预测 -> 如需扩容则扩容

ensureCapacityInternal(usedSize + 1);

// 扩容完毕，放数据

elementData[usedSize++] = e;

return true;

}

/**

* 给 index位置添加元素

* @param index

* @param e

*/

public boolean add(int index, E e) {

// 检查 index 是否合法

rangeCheckForAdd(index);

// 确定一个真正的容量 -> 如需扩容则扩容

ensureExplicitCapacity(usedSize + 1);

// 移动 index后面的元素,并在 index位置插入元素

copy(index,e);

usedSize++;

return true;

}

private void copy(int index, E e){

for (int i = usedSize; i > index; i--) {

elementData[i] = elementData[i - 1];

}

elementData[index] = e;

}

private void rangeCheckForAdd(int index) {

if (index > usedSize || index < 0)

throw new IndexOutOfBoundsException("index位置不合法！");

}

public void ensureCapacityInternal(int minCapacity) {

// 计算出需要的容量

int capacity = calculateCapacity(elementData, minCapacity);

// 根据计算出的容量，看是否需要扩容或者分配内存

ensureExplicitCapacity(capacity);

}

private void ensureExplicitCapacity(int minCapacity) {

// 如果需要的容量大于数组容量，就扩容

if (minCapacity - elementData.length > 0)

// 扩容

grow(minCapacity);

}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)

// 说明你要的容量非常大，就分配更大的内存

newCapacity = hugeCapacity(minCapacity);;

elementData = Arrays.copyOf(elementData, newCapacity);

}

private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow

throw new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ?

Integer.MAX_VALUE :

MAX_ARRAY_SIZE;

}

private static int calculateCapacity(Object[] elementData, int minCapacity) {

// 确定之前数组是否分配过内存，没有的话返回一个初始化的容量 10

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

return Math.max(10, minCapacity);

}

// 分配后，返回 +1 后的值，即实际所需要的容量

return minCapacity;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。