List 集合(實現(xiàn)類有ArrayList和LinkedList)
它是單身住宿的，一次存儲一個對象。它擁有 Collection 規(guī)定的所有方法的實現(xiàn)；同時它可以擁有自身獨特的規(guī)定的方法。
List集合的特點：
1.有索引：List 集合是有索引的
2.有序性：List 集合是有序的保證了裝入集合時的順序
3.重復(fù)性：List 集合允許存儲重復(fù)的元素
List 集合的三個典型實現(xiàn)：
1、List list1 = new ArrayList();
底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快，增刪慢；線程不安全，效率高。
2、List list3 = new LinkedList();
底層數(shù)據(jù)結(jié)構(gòu)是鏈表，查詢慢，增刪快；線程不安全，效率高。
3、List list2 = new Vector();
底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，查詢快，增刪慢；線程安全，效率低，這個集合幾乎被淘汰。
List 常用方法學習
public class TestList {
public static void main(String[] args) {
List list = new ArrayList();
Collection list2 = new ArrayList();
//增加元素
list.add("1");
list.add("2");
list.add("3");
list.add("5");
list.add("4");
list.add("5");
//增加元素
list.remove("1");
//改變元素
list.set(4,"被修改了");
System.out.println(list);
//構(gòu)造 List 的迭代器
Iterator it = list.iterator();
//通過迭代器遍歷元素
while(it.hasNext()){
Object obj = it.next();
System.out.println(obj);
}
// List 獨有的 遍歷方式
for(int i = 0 ; i < list.size() ; i++){
System.out.println(list.get(i));
}
/**
List<E> subList(int fromIndex, int toIndex)
獲取一個子集合
參數(shù)1 是開始截取的索引
參數(shù)2 是結(jié)束截取的索引
包含參數(shù)1 不包含參數(shù)2*/
List li = list.subList(2, list.size());
System.out.println(li);
}
}
int indexOf(Object o) 查看 o 第一次出現(xiàn)的索引位置
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;
}
int lastIndexOf(Object o ) 查看o 最后一次出現(xiàn)的索引位置
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
ArrayList--底層是數(shù)組
底層學習
觀察所有的構(gòu)造器 發(fā)現(xiàn)都是在為 ElementData 賦值 由此得出 ElementData 就是底層實現(xiàn)，ElementData 本身是 Object[] ElementData;
增加元素
每增加一個元素，就會判斷數(shù)組是否需要擴容，拿現(xiàn)在size + 1 去判斷，如果需要擴容，那就擴容1.5倍。
int newCapacity = oldCapacity + (oldCapacity >> 1);然后
elementData[size++] = 要添加的元素
public boolean add(Object obj){
ensureCapacityInternal(size+1)//擴容
elementData[size++] = obj;
return ture;
}
刪減元素
每移除一個元素，會先確定元素的位置，確定元素的值，然后把 要刪除的位置之前的，之后的copy到新數(shù)組，新數(shù)組替換 elementData ，然后把最后一位size賦值為null size也要 --
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;
return oldValue;
}
LinkedList--底層是鏈表
什么是鏈表
鏈式存儲的線性表
LinkedList 存儲的是什么
Node 對象：Node對象有 三個屬性
item :要存儲的對象
next : 下一個元素對象 (last 的next 一般為 null)
prev :上一個元素對象 (first 的prev 一般為 null)
LinkedList 的 add 原理
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++;
}
首先增加到 last，先記錄住當前 last 的對象，然后根據(jù)當前的 last(prev) 對象和要添加的元素(item) 和 null(next) 創(chuàng)建一個 newNode ，last 重新賦值 賦值為 newNode，添加元素之前的 last , 已經(jīng)被記錄了 ,并且參與了構(gòu)建新對象 然后再把它的 next 指向新對象，然后 size++。
LinkedList 的 remove 原理
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;
}
1. 根據(jù)索引找出要移除的對象
2. 記錄 要移除的對象的 上一個指向(prev) 存儲的值(value) 下一個指向(next)
3. prev 代表的對象 next 屬性不再指向被移除的對象 改為指向 next代表的對象
4. next 代表的對象 它的 prev 屬性不要指向被移除的對象 改為指向 prve代表的對象
同時要考慮 被移除對象可能是 first 或 last , 處理方式會有所不同
LinkedList 的 遍歷
要得到第一個 Node對象，然后不停的尋找下一個對象即 next 屬性，然后一直尋找到最后的，中間地址跳轉(zhuǎn)頻繁 ：
