【Java心得总结六】Java容器中——Collection在前面自己总结的一篇博文中对Collection的框架结构做了整理，这里深究一下Java中list的实现方式
1.动态数组
In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages.
A dynamic array is not the same thing as a dynamically allocated array, which is a fixed-size arraywhose size is fixed when the array is allocated, although a dynamic array may use such a fixed-size array as a back end.
——*
我们可以看出动态数组在动态分配数组（固定大小数组）的基础上实现的可随机存取大小可变的一种数据结构
2.Java中ArrayList实现
我截取了部分ArrayList的Java实现：
代码段1
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private transient Object[] elementData; private int size; public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
} public ArrayList() {
this(10);
} public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} 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);
// minCapacity is usually close to size, so this is a win:
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;
} /* 增加元素 */
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
} public void add(int index, E element) {
rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} /* 删除元素 */
public E remove(int index) {
rangeCheck(index); modCount++;
E oldValue = elementData(index); int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work return oldValue;
} public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
} /* 查找元素 */
public E get(int index) {
rangeCheck(index); return elementData(index);
} public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
} public boolean contains(Object o) {
return indexOf(o) >= 0;
} private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
} /* 修改元素 */
public E set(int index, E element) {
rangeCheck(index); E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
}
代码段2
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
- 代码4行，可以看出Java利用了一个Object数组来支持动态数组ArrayList的存取，Object[]的初始大小可以利用构造函数来进行设置
- 在代码28行，可以看出当Object数组不够用的时候，Java会利用grow函数对原有数组进行扩展。查看Java Arrays类会找到copyOf静态方法，会发现Java会新开辟一段更大的存储空间(newLength)，然后再将原有数组的数据全部复制到新的数组中，并返回新的引用。之后grow会将elementData指向新的数组。
- 而接下来我按照增删查改的顺序对Java中的函数进行了列举，基本就是普通的动态数组操作，就不一一说明。
3.Java中LinkedList实现
Java中LinkedList就是用双向链表来实现的，我截取了部分代码：
代码段1：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0; transient Node<E> first; transient Node<E> last; public LinkedList() {
} public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/* 链表基本操作 */
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++;
} void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
} void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
} private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
} private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
} E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev; if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
} if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
} x.item = null;
size--;
modCount++;
return element;
} /* 查找操作 */
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
} public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
} /*添加操作*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false; Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
} for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
} if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
} size += numNew;
modCount++;
return true;
} public boolean add(E e) {
linkLast(e);
return true;
} /* 删除操作 */
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
} public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
} /* 修改操作 */
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
}
代码段2：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
- 代码段1的7行和9行，我们可以看到Java中LinkedList的实现就是我们所熟知的双向链表数据结构，并且声明了头指针和尾指针分别指向链表的头和尾
- 每个节点的结构见代码段2，发现是基本的双向链表节点结构
- 而从代码18行开始就是常规的链表操作，包括插入结点和删除结点的操作
- 而之后的增删查改操作大都是利用基本的链表操作实现的
- 另外，值得注意的是LinkedList在Java中还有一个特殊功效就是通过向上转型当做队列Queue来使用
如下面这段代码
Queue<Integer> queue = new LinkedList<Integer>();
这里向上转型无非是将LinkedList限制为头尾读取。
Java中的动态数组实现，比较简单，复习回顾下，做下记录^v^