詳解Java中List接口底層實(shí)現(xiàn)原理
前言
Java是一種廣泛應(yīng)用的編程語言,被廣泛應(yīng)用于各種平臺和應(yīng)用領(lǐng)域。List接口是Java中最重要的數(shù)據(jù)結(jié)構(gòu)之一,它為我們提供了一種靈活、高效、可擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)。
當(dāng)我們使用List接口時,我們經(jīng)常需要了解它的底層實(shí)現(xiàn)原理,以便對其進(jìn)行優(yōu)化和調(diào)試。因此,本篇文章將深入研究Java中List接口的底層實(shí)現(xiàn)原理,幫助讀者更好地理解List接口的使用和優(yōu)化。
摘要
本篇文章將首先介紹Java中List接口的基本特性和使用方法,然后深入研究List接口的底層實(shí)現(xiàn)原理,包括ArrayList和LinkedList兩種實(shí)現(xiàn)方式。接著,我們將討論List接口的應(yīng)用場景和優(yōu)缺點(diǎn),并提供一些常用的測試用例和總結(jié)。
List
概述
List是Java中最常用的數(shù)據(jù)結(jié)構(gòu)之一。它提供了一種有序集合,可以按照添加的順序進(jìn)行訪問,并且允許重復(fù)元素。
Java中的List接口是一個標(biāo)準(zhǔn)接口,定義了一系列方法,可以用于訪問和操作List中的數(shù)據(jù)。List接口有多種實(shí)現(xiàn)方法,每種實(shí)現(xiàn)方法都有不同的優(yōu)缺點(diǎn)。
在下面的章節(jié)中,我們將重點(diǎn)講解Java中List接口的兩種主要實(shí)現(xiàn)方式:ArrayList和LinkedList。
源代碼解析
ArrayList
ArrayList是Java中常用的數(shù)組實(shí)現(xiàn)方式。它使用一個數(shù)組來保存List中的元素,支持動態(tài)擴(kuò)展。
ArrayList的源代碼可以在Java SDK中的java.util包中找到,其主要方法包括:
public boolean add(E e); public E get(int index); public int size(); public boolean isEmpty(); public boolean contains(Object o); public int indexOf(Object o); public E remove(int index); public E set(int index, E element);
這些方法可以用于添加、獲取、刪除和修改List中的元素。
在ArrayList中,數(shù)組的默認(rèn)大小為10,當(dāng)元素個數(shù)超出數(shù)組大小時,會自動擴(kuò)展數(shù)組的容量,以便可以繼續(xù)添加元素。例如:
List<Integer> list = new ArrayList<>(); for (int i = 0; i < 100; i++) { list.add(i); }
在上面的例子中,我們用ArrayList保存了100個整數(shù)。由于ArrayList會自動擴(kuò)展數(shù)組的大小,我們可以在不知道元素個數(shù)的情況下,隨意添加元素。
如下是部分源碼截圖:
LinkedList
LinkedList是Java中另一種常用的List實(shí)現(xiàn)方式。它使用一個雙向鏈表來保存List中的元素。每個元素節(jié)點(diǎn)都包含一個指向前一個元素和后一個元素的指針。
LinkedList的源代碼可以在Java SDK中的java.util包中找到,其主要方法包括:
public boolean add(E e); public E get(int index); public int size(); public boolean isEmpty(); public boolean contains(Object o); public int indexOf(Object o); public E remove(int index); public E set(int index, E element); public void addFirst(E e); public void addLast(E e); public E getFirst(); public E getLast(); public E removeFirst(); public E removeLast();
LinkedList的節(jié)點(diǎn)結(jié)構(gòu)如下所示:
+------+ +------+ +------+ --->| prev |<---| data |--->| next |--- +------+ +------+ +------+
在LinkedList中,每個節(jié)點(diǎn)包含一個數(shù)據(jù)項(xiàng)和兩個指針,一個指向前一個元素,一個指向后一個元素。這種雙向鏈表的結(jié)構(gòu),使得LinkedList可以支持快速添加和刪除元素。
下面的代碼演示了如何使用LinkedList:
List<Integer> list = new LinkedList<>(); for (int i = 0; i < 100; i++) { list.add(i); }
在上面的例子中,我們同樣用LinkedList保存了100個整數(shù)。由于LinkedList使用鏈表結(jié)構(gòu),它可以快速添加和刪除元素,因此在某些場景下,它可能比ArrayList更加適用。
如下是部分源碼截圖:
應(yīng)用場景案例
List接口的應(yīng)用場景非常廣泛,可以用于各種數(shù)據(jù)處理和存儲場景。
ArrayList
ArrayList適用于需要在List中快速訪問元素的場景。由于ArrayList使用數(shù)組來存儲元素,可以通過下標(biāo)訪問和修改元素,因此在需要頻繁讀取和修改List中元素的場景中,ArrayList是一種很好的選擇。
另外,由于ArrayList支持動態(tài)擴(kuò)展數(shù)組大小,因此在不知道元素個數(shù)的情況下,也可以用ArrayList來保存元素。
LinkedList
LinkedList適用于需要在List中快速添加和刪除元素的場景。由于LinkedList使用鏈表結(jié)構(gòu)來存儲元素,可以快速添加和刪除元素,因此在需要頻繁添加和刪除元素的場景中,LinkedList是一種很好的選擇。
另外,由于LinkedList支持在鏈表頭和尾部添加和刪除元素的方法,因此在需要快速訪問第一個和最后一個元素的場景中,LinkedList也是一種很好的選擇。
優(yōu)缺點(diǎn)分析
ArrayList
優(yōu)點(diǎn):
- 由于ArrayList使用數(shù)組來存儲元素,可以通過下標(biāo)訪問和修改元素。因此在需要頻繁讀取和修改List中元素的場景中,ArrayList是一種很好的選擇。
- ArrayList支持動態(tài)擴(kuò)展數(shù)組大小,因此在不知道元素個數(shù)的情況下,也可以用ArrayList來保存元素。
缺點(diǎn):
- 當(dāng)元素個數(shù)超過數(shù)組大小時,ArrayList會自動擴(kuò)展數(shù)組的容量,這會導(dǎo)致一定的性能損失。
- 由于數(shù)組在內(nèi)存中是連續(xù)的,因此在插入和刪除元素時,需要移動數(shù)組中的其他元素,這會導(dǎo)致一定的時間復(fù)雜度。
LinkedList
優(yōu)點(diǎn):
- 由于LinkedList使用鏈表結(jié)構(gòu)來存儲元素,可以快速添加和刪除元素。因此在需要頻繁添加和刪除元素的場景中,LinkedList是一種很好的選擇。
- LinkedList支持在鏈表頭和尾部添加和刪除元素的方法,因此在需要快速訪問第一個和最后一個元素的場景中,LinkedList也是一種很好的選擇。
缺點(diǎn):
- 由于LinkedList使用鏈表結(jié)構(gòu)來存儲元素,無法通過下標(biāo)訪問和修改元素。因此在需要頻繁讀取和修改元素的場景中,LinkedList可能不是最優(yōu)選擇。
- 在需要訪問中間元素時,LinkedList的訪問性能較差,因?yàn)樾枰獜逆湵眍^或尾遍歷到目標(biāo)元素。
類代碼方法介紹
ArrayList
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { public ArrayList(); public ArrayList(int initialCapacity); public ArrayList(Collection<? extends E> c); public void trimToSize(); public void ensureCapacity(int minCapacity); public int size(); public boolean isEmpty(); public boolean contains(Object o); public int indexOf(Object o); public int lastIndexOf(Object o); public Object clone(); public Object[] toArray(); public <T> T[] toArray(T[] a); public E get(int index); public E set(int index, E element); public boolean add(E e); public void add(int index, E element); public E remove(int index); public boolean remove(Object o); public void clear(); public boolean addAll(Collection<? extends E> c); public boolean addAll(int index, Collection<? extends E> c); }
代碼分析
該代碼展示了 Java 中 ArrayList 類的方法聲明。ArrayList 類實(shí)現(xiàn)了 List 接口,是一個可變大小的數(shù)組實(shí)現(xiàn),支持隨機(jī)訪問和快速插入和刪除元素。其中,包含以下主要方法:
- 構(gòu)造方法:默認(rèn)構(gòu)造方法、指定初始容量的構(gòu)造方法、從 Collection 中構(gòu)造方法。
- 容量操作方法:trimToSize(),確保該 ArrayList 實(shí)例的容量最小。
- 容量增長方法:ensureCapacity(int minCapacity),調(diào)整該 ArrayList 實(shí)例的容量,以確保它最少能容納指定最小容量的元素。
- 查詢方法:size(),返回列表中元素的數(shù)量;isEmpty(),如果列表為空,則返回 true;contains(Object o),如果此列表中包含指定元素,則返回 true;indexOf(Object o),返回此列表中指定元素的第一次出現(xiàn)的索引,如果此列表不包含元素,則返回 -1;lastIndexOf(Object o),返回此列表中指定元素的最后一次出現(xiàn)的索引,如果此列表不包含元素,則返回 -1。
- 元素操作方法:get(int index),返回列表中指定位置的元素;set(int index, E element),用指定元素替換此列表中指定位置上的元素,并返回替換前的元素;add(E e),將指定元素追加到此列表的末尾;add(int index, E element),在列表的指定位置插入指定元素;remove(int index),刪除列表中指定位置的元素,并返回被刪除的元素;remove(Object o),從此列表中刪除指定元素的第一個出現(xiàn)(如果存在);clear(),從列表中移除所有元素。
- 其他方法:clone(),返回此 ArrayList 實(shí)例的副本;toArray(),返回一個包含此列表中所有元素的數(shù)組;toArray(T[] a),返回一個包含此列表中所有元素的數(shù)組,數(shù)組類型為指定數(shù)組的運(yùn)行時類型;addAll(Collection<? extends E> c),將指定集合中的所有元素添加到列表的末尾;addAll(int index, Collection<? extends E> c),在列表的指定位置插入指定的集合中的所有元素。
這些方法使得 ArrayList 可以高效地進(jìn)行常見的列表操作,例如添加、刪除和搜索元素。
LinkedList
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { public LinkedList(); public LinkedList(Collection<? extends E> c); public int size(); public boolean isEmpty(); public boolean contains(Object o); public Iterator<E> iterator(); public Iterator<E> descendingIterator(); public boolean add(E e); public boolean remove(Object o); public void clear(); public E get(int index); public E set(int index, E element); public void add(int index, E element); public E remove(int index); public boolean addAll(Collection<? extends E> c); public boolean addAll(int index, Collection<? extends E> c); public boolean removeAll(Collection<?> c); public boolean retainAll(Collection<?> c); public E getFirst(); public E getLast(); public E removeFirst(); public E removeLast(); public void addFirst(E e); public void addLast(E e); public boolean offer(E e); public boolean offerFirst(E e); public boolean offerLast(E e); public E peek(); public E peekFirst(); public E peekLast(); public E poll(); public E pollFirst(); public E pollLast(); public E element(); public void push(E e); public E pop(); public boolean removeFirstOccurrence(Object o); public boolean removeLastOccurrence(Object o); public Object[] toArray(); public <T> T[] toArray(T[] a); private Entry<E> addBefore(E e, Entry<E> entry); private E remove(Entry<E> e); private Entry<E> entry(int index); private void linkFirst(E e); private void linkLast(E e); private void linkBefore(E e, Entry<E> succ); private E unlinkFirst(Entry<E> f); private E unlinkLast(Entry<E> l); E unlink(Entry<E> e); private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } } }
LinkedList實(shí)現(xiàn)了List、Deque和Cloneable等接口,提供了一些常用方法,如add、remove、get和set等。同時,LinkedList還提供了一些與雙向鏈表相關(guān)的方法,如linkFirst、linkLast、linkBefore、unlinkFirst和unlinkLast等。
代碼分析
這是一個泛型的雙向鏈表實(shí)現(xiàn),實(shí)現(xiàn)了 List、Deque 接口,并繼承了 AbstractSequentialList 抽象類。其中包含了鏈表的基本操作,如添加、移除、查詢元素等等。同時還包含了一些特殊的操作,如獲取頭尾元素、在頭尾添加元素、彈出元素等。內(nèi)部使用了 Entry 類來表示鏈表節(jié)點(diǎn),其中包含了元素、前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。同時還實(shí)現(xiàn)了一些私有方法來輔助鏈表的操作。
測試用例
測試代碼演示
以下是一個簡單的測試用例:
package com.demo.javase.day56.collection; import java.util.ArrayList; import java.util.List; /** * @Author bug菌 * @Date 2023-11-05 23:32 */ public class ListTest { public static void main(String[] args) { // 創(chuàng)建一個列表 List<String> list = new ArrayList<>(); // 添加元素到列表 list.add("A"); list.add("B"); list.add("C"); // 輸出列表長度 System.out.println("Size of list: " + list.size()); // 輸出列表中的元素 System.out.println("List contents: "); for (String s : list) { System.out.println(s); } // 刪除第一個元素 list.remove(0); // 輸出修改后的列表中的元素 System.out.println("List contents after removing first element: "); for (String s : list) { System.out.println(s); } // 判斷列表中是否包含指定元素 if (list.contains("A")) { System.out.println("List contains A"); } else { System.out.println("List does not contain A"); } // 清空列表 list.clear(); // 輸出清空后的列表長度 System.out.println("Size of list after clearing: " + list.size()); } }
此測試用例演示了如何創(chuàng)建List對象,添加元素,刪除元素,檢查列表是否包含特定元素以及清空列表。
測試結(jié)果
根據(jù)如上測試用例,本地測試結(jié)果如下,僅供參考,你們也可以自行修改測試用例或者添加更多的測試數(shù)據(jù)或測試方法,進(jìn)行熟練學(xué)習(xí)以此加深理解。
測試代碼分析
根據(jù)如上測試用例,在此我給大家進(jìn)行深入詳細(xì)的解讀一下測試代碼,以便于更多的同學(xué)能夠理解并加深印象。
如上測試用例介紹了Java中List(列表)的基本用法。List可以存儲一組有序的元素,在添加、刪除、修改和查詢元素時非常方便。可以使用ArrayList實(shí)現(xiàn)List接口。常用的方法包括add()、remove()、contains()和clear()。在使用List時,可以通過迭代器或者for循環(huán)遍歷列表中的元素。需要注意的是,在刪除元素時可能會導(dǎo)致元素位置變化,因此在迭代器中刪除元素時必須使用iterator.remove()方法,否則會拋出ConcurrentModificationException異常。
小結(jié)
本篇文章對Java中List接口的底層實(shí)現(xiàn)原理進(jìn)行了探討,介紹了ArrayList和LinkedList兩種主要實(shí)現(xiàn)方式的特點(diǎn)和應(yīng)用場景,并分析了它們的優(yōu)缺點(diǎn)。
在實(shí)際使用中,我們應(yīng)該根據(jù)場景的不同,選擇最合適的List實(shí)現(xiàn)方式,以達(dá)到最佳的性能和應(yīng)用體驗(yàn)。
總結(jié)
本篇文章介紹了Java中List接口的基本特性和使用方法,并深入研究了List接口的底層實(shí)現(xiàn)原理,包括ArrayList和LinkedList兩種實(shí)現(xiàn)方式。在實(shí)際應(yīng)用中,如果需要頻繁讀取和修改元素,可以使用ArrayList;如果需要頻繁添加和刪除元素,可以使用LinkedList。此外,本文還分析了它們的優(yōu)缺點(diǎn),提供了一些常用的測試用例和總結(jié)。
以上就是詳解Java中List接口底層實(shí)現(xiàn)原理的詳細(xì)內(nèi)容,更多關(guān)于Java List接口底層實(shí)現(xiàn)的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Java編寫實(shí)現(xiàn)坦克大戰(zhàn)小游戲
這篇文章主要為大家詳細(xì)介紹了Java編寫實(shí)現(xiàn)坦克大戰(zhàn)小游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-01-01Servlet實(shí)現(xiàn)共享數(shù)據(jù)JavaWeb組件的幾種方法
本文將結(jié)合實(shí)例代碼,介紹Servlet實(shí)現(xiàn)共享數(shù)據(jù)JavaWeb組件的幾種方法,具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-07-07Java服務(wù)器主機(jī)信息監(jiān)控工具類的示例代碼
這篇文章主要介紹了Java服務(wù)器主機(jī)信息監(jiān)控工具類的示例代碼,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-04-04Java實(shí)現(xiàn)Excel轉(zhuǎn)PDF的兩種方法詳解
使用具將Excel轉(zhuǎn)為PDF的方法有很多,在這里我給大家介紹兩種常用的方法:使用spire轉(zhuǎn)化PDF、使用jacob實(shí)現(xiàn)Excel轉(zhuǎn)PDF,分別應(yīng)對兩種不一樣的使用場景,需要的可以參考一下2022-01-01springMVC攔截器HandlerInterceptor用法代碼示例
這篇文章主要介紹了springMVC攔截器HandlerInterceptor用法代碼示例,具有一定借鑒價值,需要的朋友可以參考下2017-12-12