contains()
public boolean contains(Object o) { return indexOf(o) >= 0; } 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; }不难看出, 这需要遍历整个数组才能实现. 最坏情况下需要N次才能实现.
同时从这里也能看出 ArrayList的另一个要点, 必须实现或重写 equals()方法, 否则的话很容易找不到对应元素.
iterator()
至于这个方法, 就不多说, 遍历一个数组还是很简单的, 其中有一个地方, 通过modCount判断在遍历过程中是否修改, 限制修改. 因此如果需要修改的话, 需要调用 iterator.remove() 方法, 至于如何放开修改限制:
public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }值得一提的是, 在 遍历的过程中, 仅仅是阻止增删操作, 其 修改操作即 set()操作, 和修改元素本身的操作都是开放的.
总结
还有一个很重要的点, 在各个 Collection之间的相互转换得以实现的关键因素, 是因为 统一实现了 toArray() 方法, 同时在 Arrays.asList() 可以将数组转换为集合.
ArrayList本身是无序的, 元素可为空, 遍历的时候不支持增删操作, 如果删除的话, 需要调用返回对象的 remove方法.
如果需要排序的话, 则可以调用 ArrayList的 sort()方法, 而无需自己转换.
那在什么时候使用它呢?
明显的在增删次数较多的时候, 不适合, 同时必须注意它的无序性, 即使存在 sort()方法, 或者自己进行排序, 但必须注意的是, 在以后的任何一次增删操作, 并不维持新数组的有序性. 所以说, 对ArrayList进行持续性的操作是不划算的.
存在的另一个问题是, 底层是数组, 当数据量过大的时候, 需要更大的数组, 相比于使用 散列表实现的, 优点并不多.
优点不多, 查询速度较快, 如果一次性放入, 且数据量并不大的情况下还是比较合适的. 这里的查询也仅仅是指按照下标进行查询.
最后:
所以在我看来, ArrayList更适合将本身有序的数据存入, 否则的话 无论是他的 contains方法, get(Object o)都是效率相当低下的方式. 更不用说 add() 和 remove操作.
LinkedList
Node
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; } }从核心数据结构来看, 采用的是双向链表.
变量
transient int size = 0; transient Node<E> first; transient Node<E> last; protected transient int modCount = 0;和常规一样, 需要三个变量, 分别为容器存量, 头尾. 因为是双向链表, 自然要记录头尾的节点. 同样的, 维护了一个变量, modCount, 用以记录被更改的次数. 至于这个变量, 在两种数据结构中 都只是为了 遍历时保证数据的一致性.
add()
public boolean add(E e) { linkLast(e); return true; } 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++; }
remove()
public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } 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; }首先要提到的一点是, 同样的在删除的时候采用了equals() 这也就意味着我们同样要重写 equals()方法.
值得一提的是, 在删除当前节点的时候, 将被删除节点的三个属性都置空, 这是我在自己实现的时候, 所未考虑到的.
另外则是, 在删除的时候要从头到尾的遍历这个集合进行删除.
在删除的时候还需要注意到的一点是, 集合中是允许存在相同元素的, 因此在删除的时候, 特别是删除 Object的时候, 并不会删除所有相同元素.