List接口介紹
List接口是有序的collection(也稱為序列,這個有序不是指的自然順序,而是指添加進集合中的順序與元素出來的順序一緻),使用者可以對清單中每個元素的插入位置進行精确地控制。使用者可以根據元素的整數索引(在清單中的位置)通路元素,并搜尋清單中的元素。
主要的實作類有如下三個:
ArrayList :底層是維護了一個Objecy數組實作的,特點:查詢速度快,增删慢;
LinkedList:底層是使用了連結清單資料結構實作的,特點:查詢速度慢,增删塊;
Vector:底層維護了一個Object的數組實作的,實作與ArratList是一樣的,但是Vector是線程安全的,同步的,操作效率低
實作方法
除了Collection接口實作的一些方法外,List接口有一些特有的方法,可以使用索引index快速操作,
-
1:增加
void add(int index, E element) 指定位置添加元素
boolean addAll(int index, Collection c) 指定位置添加集合
-
2:删除
E remove(int index) 删除指定位置元素
-
3:修改
E set(int index, E element) 傳回的是需要替換的集合中的元素
-
4:查找:
E get(int index) 注意: IndexOutOfBoundsException
int indexOf(Object o) // 找不到傳回-1
lastIndexOf(Object o)
-
5:求子集合
List subList(int fromIndex, int toIndex) // 不包含toIndex
-
6.疊代器
listIterator(int index)
List接口還提供了特殊的疊代器,稱為ListIterator,除了允許Iterator接口提供的正常操作外,該疊代器還允許元素的差入和替換,以及雙向通路,還提供了一個方法來擷取從清單中指定位置開始的清單疊代器。
ListIterator疊代器特有方法:
hasPrevious() 判斷是否存在上一個元素
previous:指針先向上移動一個機關,然後取出目前指向的元素
next():先取出目前指向的元素,然後指針向下移動一個機關
set(E e) :用指定元素替換next或previous傳回的最後一個元素
周遊集合的方法
使用三種方法周遊集合的元素:
- 1.使用get方法周遊
- 2.使用疊代器正序周遊
- 3.使用疊代器逆序周遊
//get方法周遊 for(int i = 0 ; i<list.size() ; i++){ System.out.print(list.get(i)+","); } //使用疊代器正序周遊 ListIterator it = list.listIterator(); //擷取到疊代器 while(it.hasNext()){ System.out.print(it.next()+","); } //使用疊代器逆序周遊 while(it.hasPrevious()){ System.out.print(it.previous()+","); }
注意:
在使用疊代器疊代元素的過程中,不允許使用集合對象改變集合中的元素個數,若需要添加或删除隻能使用疊代器的方法進行操作;若使用了集合對象改變,則會報ConcurrentModificationException異常。
實作類ArrayList使用
ArrayList實作類是類似于一個可變數組,長度可動态變化,允許包含null元素。此實作類不是同步的,若有多個線程同時通路一個ArrayList執行個體,而其中有一個線程從結構上修改了清單,那麼它必須保持外部同步。(結構上的修改是指任何添加或删除一個或多個元素的操作,或者顯式調整底層數組的大小,僅僅設定元素的值不是結構上的修改)
ArrayList實作類的定義源碼如下:
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { private static final long serialVersionUID = 8683452581122892189L; private transient Object[] elementData; //存儲ArrayList内的元素,transient 關鍵字關閉序列化 private int size; //表示ArrayList内的元素個數 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) { //構造一個具有指定collection的元素的清單 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); }
ArrayList類繼承了AbstractList(此類提供了List接口的主要實作),實作了List接口;
RandomAccess是一個标記接口,用來表明其支援快速(通常是固定時間)随機通路(在這裡的快速随機通路我的了解就是可以通過下标直接通路數組,已達到快速通路);
實作Cloneable接口,以訓示 Object.clone() 方法可以合法地對該類執行個體進行按字段複制;
實作java.io.Serializable接口,這意味着ArrayList支援序列化,能通過序列化去傳輸,所謂的序列化就是将實作了Serializable接口的對象轉換成一個位元組序列,并能夠在以後将這個位元組序列完全恢複為原來的對象,可以通過網絡進行,序列化機制能自動彌補不同作業系統之間的差異。(對于序列化的了解,參看https://my.oschina.net/u/1382972/blog/170148 )
transient 關鍵字:若是實作了Serializable接口進行序列化功能,那麼所有序列化操作都會自動進行,對于這些序列化處理的資訊可以通過讀取檔案或者攔截網絡傳輸的方式通路,因而為了保護資訊安全(比如密碼資訊)或者有某個特定的子對象不想被Java序列化機制自動儲存,就可以使用transient關鍵字關閉序列化。
如上源碼可知ArrayList底層是維護了一個Object數組實作的,有三個預設構造函數,使用無參構造函數時,Object數組預設容量是10,當長度不夠時,自動增長0.5倍,查詢速度快。對于增删操作,因為牽扯到元素的拷貝(增加時,會申請一個更大的數組,将原有數組的元素拷貝至新的數組),速度慢。
示例
/* * 思路:建立一個新的集合,将舊集合中的元素一次複制到新集合,複制的前提是新集合中不存在該元素,就可以删除重複的 */ import java.util.ArrayList; import java.util.Iterator; class Book{ int id; String name;// 名字 public Book(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "{ 書号:"+ this.id+" 書名:"+ this.name+" }"; } @Override public boolean equals(Object obj) { Book book =(Book)obj; return this.id==book.id; } } // 需求: 編寫一個函數清除集合中重複元素。 如果書号是一樣就視為重複元素。 要求: 周遊集合元素的時候必須使用疊代器。 java程式設計思想和java探秘書号一樣,第二個java探秘會被清除 public class Test { public static void main(String[] args) { ArrayList list= new ArrayList(); list.add(new Book(110,"java程式設計思想")); list.add(new Book(220,"java核心技術")); list.add(new Book(330,"JVM虛拟機")); list.add(new Book(110,"java探秘")); ArrayList list2 = clearRepeat(list); System.out.println("新集合的元素是:"+ list2); } public static ArrayList clearRepeat(ArrayList list){ //建立一個新的集合 ArrayList newList = new ArrayList(); //擷取疊代器 Iterator it = list.iterator(); while(it.hasNext()){ Book book = (Book) it.next(); //從舊集合中擷取的元素 if(!newList.contains(book)){ //如果新集合沒有包含該書籍,那麼就存儲到新集合中 newList.add(book); } } return newList; } }
實作類LinkedList使用
LinkedList實作類内部實作主要是以指針方式連接配接的,相鄰的兩個元素位址不一樣相鄰。此實作不是同步的。如果多個線程同時通路一個連結清單,而其中至少一個線程從結構上修改了該清單,則它必須 保持外部同步。
檢視LinkedList函數定義實作:
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
LinkedList 是一個繼承于AbstractSequentialList的雙向連結清單。它也可以被當作堆棧、隊列或雙端隊列進行操作。
LinkedList 實作了:
List 接口,能對它進行隊列操作。
Deque 接口,即能将LinkedList當作雙端隊列使用,支援在兩端插入和移除元素。
Cloneable接口,即覆寫了函數clone(),能克隆。
java.io.Serializable接口,這意味着LinkedList支援序列化,能通過序列化去傳輸。
執行個體
import java.util.LinkedList; /* 使用LinkedList模拟堆棧的資料結構存儲方式 1:棧 : 主要是用于實作堆棧資料結構的存儲方式。 先進後出 push() pop() 2:隊列: 主要是為了讓你們可以使用LinkedList模拟隊列資料結構的存儲方式。 先進先出 offer() poll() */ class StackList{ LinkedList list; public StackList(){ list = new LinkedList(); } //進棧 public void add(Object o){ list.push(o); } //彈棧 : 把元素删除并傳回。 public Object pop(){ return list.pop(); } //擷取元素個數 public int size(){ return list.size(); } } //使用LinkedList模拟隊列的存儲方式 class TeamList{ LinkedList list; public TeamList(){ list = new LinkedList(); } public void add(Object o){ list.offer(o); } public Object remove(){ return list.poll(); } //擷取元素個數 public int size(){ return list.size(); } } public class LinkedListTest { public static void main(String[] args) { TeamList list= new TeamList(); list.add("張三"); list.add("李四"); list.add("王五"); int size = list.size(); for(int i = 0 ; i<size ; i++){ System.out.println(list.remove()); } } }