数据结构List 总结
· 5 min read
List
这里只对常用list集合进行分析
ArrayList
标准的线性数组结构封装实现了Collection和List接口，可以灵活的设置数组的大小。要注意的是ArrayList并不是线程安全的，因此一般建议在单线程中使用ArrayList。##ArrayList的方法使用和源码解析 ###构造方法
//1-----------------------
public ArrayList() {
this(10);
//调用ArrayList(10) 默认初始化一个大小为10的object数组。
}
//2-------------------------
public ArrayList(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//如果用户初始化大小小于0抛异常，否则新建一个用户初始值大小的object数组。
this.elementData = new Object[initialCapacity];
}
//3--------------------------
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// 当c.toArray返回的不是object类型的数组时，进行下面转化。
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
ArrayList初始化会生成一个长度为10的数组，随着元素的增加自动扩容。
add(E e)方法
//1-----------------------
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 加入元素前检查数组的容量是否足够
elementData[size++] = e;
return true;
}
//2-----------------------
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// 如果添加元素后大于当前数组的长度，则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//3-----------------------
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//将数组的长度增加原来数组的一半。
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果扩充一半后仍然不够，则 newCapacity = minCapacity;minCapacity实际元素的个数。
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//数组最大位2^32
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
add方法比较复杂，涉及到扩充数组容量的问题。其中要弄清楚size和elementData.length的区别，size指的是数组中存放元素的个数，elementData.length表示数组的长度， 当new一个ArrayList系统默认产生一个长度为10的elementData数组，elementData.length=10，但是由于elementData中还未放任何元素所有size=0。 如果加入元素后数组大小不够会先进行扩容，每次扩容都将数组大小增大一半比如数组大小为10一次扩容后的大小为10+5=10;ArrayList的最大长度为 2^32 .
LinkedList
LinkedList 双向链表结构,内置Node节点 节点属性item 存放element prev上个节点 next下个节点
LinkedList 是线程不安全的，允许元素为null的双向链表。 没有实现RandomAccess所以其以下标，随机访问元素速度较慢。 因其底层数据结构是链表，所以可想而知，它的增删只需要移动指针即可，故时间效率较高。不需要批量扩容，也不需要预留空间，所以空间效率比ArrayList高。 缺点就是需要随机访问元素时，时间效率很低，虽然底层在根据下标查询Node的时候，会根据index判断目标Node在前半段还是后半段，然后决定是顺序还是逆序查询，以提升时间效率。不过随着n的增大，总体时间效率依然很低。 当每次增、删时，都会修改modCount。ArrayList的方法使用和源码解析
add(E e) 方法
public boolean add(E e) {
linkLast(e); //从链表尾部添加元素
return true;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;//将新添元素设置为末尾元素 将上个末尾设置为当前的prev
if (l == null)
first = newNode;
else
l.next = newNode;//将上个末尾元素next设置为当前末尾元素
size++;
modCount++;
}
push(E e) 方法
public void push(E e) {
addFirst(e);
}
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.
*/
private void linkFirst(E e) {//从头部添加元素
final Node<E> f = first;//之前头部元素
final Node<E> newNode = new Node<>(null, e, f);//新添头部元素
first = newNode;
//更改指针指向
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
get(int index) 获取角标的元素
public E get(int index) {
checkElementIndex(index);//检查索引有效性
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//先判断index角标处于整个链表的前半部分还是后半部分 然后决定是从头找还是从末尾找 提高查找效率 类似二分
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}