文章目錄
- 前言
- ArrayList和LinkedList
-
- List的方法
- ArrayList
-
- add
- remove
- LinkedList
-
- remove
- get和peek
- push
- ArrayList和LinkedList的使用場景和差別
前言
最近參加了21天打卡活動,希望可以讓自己養成寫部落格的習慣…
ArrayList和LinkedList
ArrayList和LinkedList都是常用的List類型,兩者都繼承了AbstratctList,并實作List接口。
List的方法
列舉一些常見的方法,ArrayList和LinkedList會實作List裡面的方法
方法 | 描述 |
---|---|
boolean isEmpty() | 判斷目前清單是否為空 |
boolean contains(Object o) | 是否包含這個元素 |
T[] toArray(T[] a) | |
boolean add(E e) | 添加一個元素 |
boolean remove(Object o) | 移除 |
boolean containsAll(Collection<?> c) | |
void add(int index, E element) | 在固定位置添加元素 |
int indexOf(Object o) | 定位元素 |
ListIterator listIterator() | 周遊清單 |
上述的方法都是List的常用方法,相信大家都非常的熟悉。
ArrayList
ArrayList是實作List接口的可擴容數組(動态數組),它的内部是基于數組實作的,數組這個結構具有的特點
随機存取:随機存取就是可以通過索引直接通路清單的元素
可以實作動态擴容,下面我們來看一下它的源碼實作
屬性 | 描述 |
---|---|
size | 清單的元素個數 |
DEFAULT_CAPACITY | 建立一個空對象時的預設大小 |
我們來看一下ArrayList是怎麼實作動态擴容的。
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);
}
如果當容量比初始容量大時,新的容量相當于是原來的1.5倍這裡
add
ArrayList重載了List的add方法,這裡面重寫的方法有直接添加,和在某一個位置添加一個元素,這裡就可以看出ArrayList的底層是由數組實作的了
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++;
}
這裡采用的是System.arraycopy來進行數組的拷貝,屬于深度拷貝,效率很高。
remove
這裡的移除也是有直接移除某個索引下的資料,但是這裡面有兩個不同的方式移除資料,一個是remove,一個是fastRemove兩種方式移除元素,remove和fastRemove不同的是一個是需要傳回删除的元素,一個是不傳回的。
LinkedList
LinkedList是基于雙向連結清單來實作的,是屬于鍊式存儲,隻能順序存取元素,不能随機存取。
LinkedList的結點結構,包括指向下一個結點的指針next和指向上一個結點的指針prev
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;
}
}
屬性包括
名稱 | 描述 |
---|---|
size | 元素個數 |
first | 頭節點 |
last | 尾節點 |
remove
移除頭節點,需要更新size大小和把删除的節點為NULL,裡面還有removeRange方法,可以把從fromIndex到toIndex的全部節點釋放掉
public E remove() {
return removeFirst();
}
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;
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
get和peek
下面可以來看看LinkedList的通路元素的形式,前面說了這個結構是隻能順序周遊的,不能随機進行通路,需要周遊整個清單,但是我們使用的是雙向連結清單,由于我們維護了頭節點和尾節點,當需要通路元素時,如果根據的是下标(這裡的下标不是數組的下标),先判斷和頭節點近還是和尾節點近,然後再進行順序周遊。
peek方法是通路頭節點。
Node<E> node(int index) {
// assert isElementIndex(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;
}
}
push
向清單中添加元素,我們可以采用offerFirst和offerLast往清單頭部添加元素或者往尾部添加元素,push方法調用的是addFrist方法,采用的是頭插法,删除也是才有删除頭部元素;
ArrayList和LinkedList的使用場景和差別
前面也提到兩者的存取結構是不同的,一個是用數組來操作,一個采用的是雙向連結清單,一般ArrayList用在通路更加多的情況下,由于插入會相對較慢,但是LinkedList采用的是順序通路,在插入和删除較多的場景會更加适用。