JAVA中ArrayList與順序表舉例詳解
前言
在 Java 的集合框架中，ArrayList 是最常用的數(shù)據(jù)結(jié)構(gòu)之一，它以動(dòng)態(tài)數(shù)組為底層實(shí)現(xiàn)，提供了靈活的元素存取與自動(dòng)擴(kuò)容機(jī)制。而在數(shù)據(jù)結(jié)構(gòu)課程中，順序表（Sequential List） 作為線性表的一種典型實(shí)現(xiàn)，同樣以數(shù)組為存儲(chǔ)基礎(chǔ)。兩者在原理上有諸多相似之處，但在實(shí)現(xiàn)策略、內(nèi)存管理、擴(kuò)容機(jī)制以及時(shí)間復(fù)雜度控制等方面卻各有差異。本文將從底層原理出發(fā)，深入分析 ArrayList 的實(shí)現(xiàn)細(xì)節(jié)，并將其與順序表進(jìn)行對(duì)比，以幫助讀者更好地理解二者的聯(lián)系與區(qū)別，從而在實(shí)際開(kāi)發(fā)與算法設(shè)計(jì)中更合理地選擇合適的數(shù)據(jù)結(jié)構(gòu)。
一、什么是線性表
線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表：順序表、鏈表、棧、隊(duì)列…
線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
二、順序表
順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。(即邏輯上連續(xù)，物理上也連續(xù)的數(shù)據(jù)結(jié)構(gòu))
2.1 順序表接口的實(shí)現(xiàn)
2.2 ArrayList簡(jiǎn)介
在集合框架中，ArrayList是一個(gè)普通的類，實(shí)現(xiàn)了List接口，具體框架圖如下：
總結(jié)：
- ArrayList是以泛型方式實(shí)現(xiàn)的，使用時(shí)必須要先實(shí)例化
- ArrayList實(shí)現(xiàn)了RandomAccess接口，表明ArrayList支持隨機(jī)訪問(wèn)
- ArrayList實(shí)現(xiàn)了Cloneable接口，表明ArrayList是可以clone的
- ArrayList實(shí)現(xiàn)了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者CopyOnWriteArrayList
- ArrayList底層是一段連續(xù)的空間，并且可以動(dòng)態(tài)擴(kuò)容，是一個(gè)動(dòng)態(tài)類型的順序表
2.3 ArrayList的構(gòu)造
package demo2;
import java.util.ArrayList;
public class Test {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(list);
ArrayList<Integer> list2 = new ArrayList<>(list);
list2.set(2,50);
System.out.println(list2);
ArrayList<String> list3 = new ArrayList<>(2);
list3.add("hhh");
list3.add("ddd");
list3.add("aaa");
System.out.println(list3);
}
}
2.4 ArrayList常見(jiàn)操作
ArrayList雖然提供的方法比較多，但是常用方法如下所示，需要用到其他方法時(shí)，同學(xué)們自行查看ArrayList的幫助文檔。
package demo3;
import demo1.MyArrayList;
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
ArrayList<String> list2 = new ArrayList<>(list);
list2.add("hhh");
list2.add("hhh");
list2.add("hhh");
list.add("dzj");
list.add("hzp");
list.add("xrx");
list.add("xx");
list.add("lyy");
list.add("lwm");
list.add(1,"sb");
System.out.println(list);
list.addAll(4,list2);
System.out.println(list);
list.remove(1);
System.out.println(list);
System.out.println(list.get(6));
list.set(6,"xxx");
System.out.println(list);
list.clear();
System.out.println(list);
list.addAll(list2);
System.out.println(list);
System.out.println(list.contains("hh"));
System.out.println(list.indexOf("hhh"));
System.out.println(list.lastIndexOf("hhh"));
list.addAll(list2);
list.addAll(list2);
list.addAll(list2);
System.out.println(list);
list.clear();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
System.out.println(list);
List<String> sub=list.subList(1,4);
sub.set(0,"dzj");
System.out.println(list);
System.out.println(sub);
List<String> newList=new ArrayList<>(list.subList(1,4));
System.out.println(newList);
}
}
其中對(duì)于subList方法有一個(gè)小坑，請(qǐng)看如下代碼：
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
System.out.println(list);
List<String> sub=list.subList(1,4);
sub.set(0,"dzj");
System.out.println(list);
System.out.println(sub);
也就是說(shuō)sub和原來(lái)的list實(shí)際上用的是同一塊空間，這和我們的正常認(rèn)知有所不同，所以這通常是一種不安全的方式，請(qǐng)安全保險(xiǎn)的方式如下：
List<String> newList=new ArrayList<>(list.subList(1,4));
System.out.println(newList);
2.5 ArrayList的遍歷方式
ArrayList 可以使用三方式遍歷：for循環(huán)+下標(biāo)、foreach、使用迭代器
package demo4;
import java.util.ArrayList;
import java.util.Iterator;
public class Test {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
System.out.println();
for (Integer x : list) {
System.out.print(x+" ");
}
System.out.println();
Iterator<Integer> it = list.iterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
}
}
2.6 ArrayList的擴(kuò)容機(jī)制
關(guān)于這一點(diǎn)只需要了解以下內(nèi)容即可。
無(wú)參創(chuàng)建的 ArrayList 初始并不開(kāi)辟實(shí)際存儲(chǔ)空間，只有在第一次添加元素時(shí)才分配默認(rèn)容量（10個(gè)），后續(xù)擴(kuò)容為1.5倍擴(kuò)容。
具體的實(shí)現(xiàn)細(xì)節(jié)可以參照其源碼，這一點(diǎn)大家自己感興趣的可以自行查閱。
2.7 ArrayList的應(yīng)用
2.7.1 楊輝三角
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list=new ArrayList<>();
for (int i = 0; i < numRows; i++) {
list.add(new ArrayList<>());
}
for (int i = 0; i < numRows; i++) {
for (int j = 0; j <=i; j++) {
if(j==0||j==i){
list.get(i).add(1);
}else{
int x = list.get(i-1).get(j);
int y = list.get(i-1).get(j-1);
list.get(i).add(x+y);
}
}
}
return list;
}
}
2.7.2 簡(jiǎn)單的洗牌算法
package demo5;
public class Card {
int rank;
String suit;
public Card(int rank, String suit){
this.rank=rank;
this.suit=suit;
}
@Override
public String toString() {
return "{" +
rank +
", " + suit + '\'' +
'}';
}
}package demo5;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class CardDemo {
public static final String[] suits={"?", "?", "?", "?"};
List<Card> deck = new ArrayList<>(52);
public void createDeck(){
for (int i = 0; i < suits.length; i++) {
for (int j = 0; j < 13; j++) {
Card card = new Card(j+1, suits[i]);
deck.add(card);
}
}
}
public void swapCards(int i,int j){
Card temp = deck.get(i);
deck.set(i, deck.get(j));
deck.set(j, temp);
}
public void shuffleDeck(){
Random random=new Random();
int count = 1;
for (int i = deck.size()-1; i >0 ;i--) {
int j = random.nextInt(deck.size()-count);
swapCards(i,j);
count++;
}
}
}package demo5;
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) {
CardDemo cardDemo=new CardDemo();
cardDemo.createDeck();
System.out.println(cardDemo.deck);
cardDemo.shuffleDeck();
System.out.println(cardDemo.deck);
List<List<Card>> persons=new ArrayList<>();
persons.add(new ArrayList<>());
persons.add(new ArrayList<>());
persons.add(new ArrayList<>());
for (int i = 0; i < 10; i++) {
for (int j = 0; j < persons.size(); j++) {
persons.get(j).add(cardDemo.deck.get(i));
cardDemo.deck.remove(i);
}
}
for(List<Card> person:persons){
System.out.println(person);
}
System.out.println(cardDemo.deck);
}
}
2.8 小結(jié)
1. ArrayList底層使用連續(xù)的空間，任意位置插入或刪除元素時(shí)，需要將該位置后序元素整體往前或者往后搬移，故時(shí)間復(fù)雜度為O(N)
2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
3. 增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們?cè)倮^續(xù)插入了5個(gè)數(shù)據(jù)，后面沒(méi)有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間。
總結(jié)
通過(guò)對(duì)比可以發(fā)現(xiàn)，順序表是理論基礎(chǔ)，而 ArrayList 是工程化實(shí)現(xiàn)。順序表強(qiáng)調(diào)抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)和基本操作原理，而 ArrayList 則在此基礎(chǔ)上進(jìn)行了面向?qū)ο笈c動(dòng)態(tài)內(nèi)存管理的優(yōu)化，具備更高的靈活性與可擴(kuò)展性。理解 ArrayList 的底層機(jī)制不僅有助于掌握其性能特征（如時(shí)間復(fù)雜度與擴(kuò)容策略），也能加深對(duì)數(shù)組式線性存儲(chǔ)結(jié)構(gòu)的理解。無(wú)論是數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)者還是 Java 開(kāi)發(fā)者，深入理解二者的內(nèi)在聯(lián)系，都能在實(shí)際編程中寫(xiě)出更高效、更穩(wěn)定的代碼。
到此這篇關(guān)于JAVA中ArrayList與順序表的文章就介紹到這了,更多相關(guān)JAVA ArrayList與順序表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java之注解@Data和@ToString(callSuper=true)解讀
在使用Lombok庫(kù)的@Data注解時(shí),若子類未通過(guò)@ToString(callSuper=true)注明包含父類屬性,toString()方法只打印子類屬性,解決方法：1. 子類重寫(xiě)toString方法；2. 子類使用@Data和@ToString(callSuper=true),父類也應(yīng)使用@Data2024-11-11
Maven 或 Gradle 下載和添加 jar 文件的最佳方式
Maven是一個(gè)Java項(xiàng)目管理工具,它可以幫助你管理項(xiàng)目的依賴、編譯、打包、測(cè)試和部署等過(guò)程,下面給大家介紹Maven或Gradle下載和添加jar文件的最佳方式,感興趣的朋友一起看看吧2024-10-10
Java設(shè)計(jì)模式之解釋器模式_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
解釋器模式是一個(gè)比較少用的模式，本人之前也沒(méi)有用過(guò)這個(gè)模式。下面我們就來(lái)一起看一下解釋器模式2017-08-08
這篇文章主要介紹了java包本質(zhì)及命名規(guī)范,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-03-03
SpringCloud feign無(wú)法注入接口的問(wèn)題
這篇文章主要介紹了SpringCloud feign無(wú)法注入接口的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-06-06
Java中import java.util.Scanner的用處詳解
文章主要介紹Java中的Scanner類及其常用方法next()和nextLine()的區(qū)別,next()方法在遇到空格、Tab鍵、回車鍵等分隔符時(shí)結(jié)束輸入,而nextLine()方法則接收所有輸入,直到遇到回車鍵2024-11-11
基于SpringBoot使用Tika實(shí)現(xiàn)文檔解析
Apache?Tika是開(kāi)源內(nèi)容分析工具,支持多格式文本提取與元數(shù)據(jù)解析,具備語(yǔ)言檢測(cè)和MIME類型識(shí)別功能,適用于搜索引擎、數(shù)據(jù)分析等場(chǎng)景,在SpringBoot中集成需注意性能及配置問(wèn)題,支持流式處理和自定義擴(kuò)展,下面介紹SpringBoot使用Tika實(shí)現(xiàn)文檔解析,感興趣的朋友一起看看吧2025-07-07
在mybatis 中使用if else 進(jìn)行判斷的操作
這篇文章主要介紹了在mybatis 中使用if else 進(jìn)行判斷的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-02-02
這篇文章主要介紹了java RMI詳細(xì)介紹及實(shí)例講解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
Java基于ReadWriteLock實(shí)現(xiàn)鎖的應(yīng)用
這篇文章主要介紹了Java基于ReadWriteLock實(shí)現(xiàn)鎖的應(yīng)用,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10