JAVA中ArrayList與順序表舉例詳解
前言
在 Java 的集合框架中，ArrayList 是最常用的數(shù)據(jù)結構之一，它以動態(tài)數(shù)組為底層實現(xiàn)，提供了靈活的元素存取與自動擴容機制。而在數(shù)據(jù)結構課程中，順序表（Sequential List） 作為線性表的一種典型實現(xiàn)，同樣以數(shù)組為存儲基礎。兩者在原理上有諸多相似之處，但在實現(xiàn)策略、內(nèi)存管理、擴容機制以及時間復雜度控制等方面卻各有差異。本文將從底層原理出發(fā)，深入分析 ArrayList 的實現(xiàn)細節(jié)，并將其與順序表進行對比，以幫助讀者更好地理解二者的聯(lián)系與區(qū)別，從而在實際開發(fā)與算法設計中更合理地選擇合適的數(shù)據(jù)結構。
一、什么是線性表
線性表（linear list）是n個具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實際中廣泛使用的數(shù)據(jù)結構，常見的線性表：順序表、鏈表、棧、隊列…
線性表在邏輯上是線性結構，也就說是連續(xù)的一條直線。但是在物理結構上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈式結構的形式存儲。
二、順序表
順序表是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結構，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。(即邏輯上連續(xù)，物理上也連續(xù)的數(shù)據(jù)結構)
2.1 順序表接口的實現(xiàn)
2.2 ArrayList簡介
在集合框架中，ArrayList是一個普通的類，實現(xiàn)了List接口，具體框架圖如下：
總結：
- ArrayList是以泛型方式實現(xiàn)的，使用時必須要先實例化
- ArrayList實現(xiàn)了RandomAccess接口，表明ArrayList支持隨機訪問
- ArrayList實現(xiàn)了Cloneable接口，表明ArrayList是可以clone的
- ArrayList實現(xiàn)了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者CopyOnWriteArrayList
- ArrayList底層是一段連續(xù)的空間，并且可以動態(tài)擴容，是一個動態(tài)類型的順序表
2.3 ArrayList的構造
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常見操作
ArrayList雖然提供的方法比較多，但是常用方法如下所示，需要用到其他方法時，同學們自行查看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);
}
}
其中對于subList方法有一個小坑，請看如下代碼：
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);
也就是說sub和原來的list實際上用的是同一塊空間，這和我們的正常認知有所不同，所以這通常是一種不安全的方式，請安全保險的方式如下：
List<String> newList=new ArrayList<>(list.subList(1,4));
System.out.println(newList);
2.5 ArrayList的遍歷方式
ArrayList 可以使用三方式遍歷：for循環(huán)+下標、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的擴容機制
關于這一點只需要了解以下內(nèi)容即可。
無參創(chuàng)建的 ArrayList 初始并不開辟實際存儲空間，只有在第一次添加元素時才分配默認容量（10個），后續(xù)擴容為1.5倍擴容。
具體的實現(xiàn)細節(jié)可以參照其源碼，這一點大家自己感興趣的可以自行查閱。
2.7 ArrayList的應用
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 簡單的洗牌算法
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 小結
1. ArrayList底層使用連續(xù)的空間，任意位置插入或刪除元素時，需要將該位置后序元素整體往前或者往后搬移，故時間復雜度為O(N)
2. 增容需要申請新空間，拷貝數(shù)據(jù)，釋放舊空間。會有不小的消耗。
3. 增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100，滿了以后增容到200，我們再繼續(xù)插入了5個數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費了95個數(shù)據(jù)空間。
總結
通過對比可以發(fā)現(xiàn)，順序表是理論基礎，而 ArrayList 是工程化實現(xiàn)。順序表強調(diào)抽象數(shù)據(jù)類型的邏輯結構和基本操作原理，而 ArrayList 則在此基礎上進行了面向對象與動態(tài)內(nèi)存管理的優(yōu)化，具備更高的靈活性與可擴展性。理解 ArrayList 的底層機制不僅有助于掌握其性能特征（如時間復雜度與擴容策略），也能加深對數(shù)組式線性存儲結構的理解。無論是數(shù)據(jù)結構學習者還是 Java 開發(fā)者，深入理解二者的內(nèi)在聯(lián)系，都能在實際編程中寫出更高效、更穩(wěn)定的代碼。
到此這篇關于JAVA中ArrayList與順序表的文章就介紹到這了,更多相關JAVA ArrayList與順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Spring Boot是由Pivotal團隊提供的全新框架,其設計目的是用來簡化新Spring應用的初始搭建以及開發(fā)過程,下面這篇文章主要給大家介紹了一個簡單的SpringBoot項目快速搭建詳細步驟,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-08-08
這篇文章主要介紹了基于java使用JavaMail發(fā)送郵件 ,非常具有實用價值，需要的朋友可以參考下。2016-12-12
SpringBoot?main方法結束程序不停止的原因分析及解決方法
Spring?Boot啟動內(nèi)嵌Tomcat時,main方法啟動非daemon線程執(zhí)行await()死循環(huán),使JVM保持運行,通過發(fā)送關機指令可終止程序,下面通過本文給大家介紹SpringBoot?main方法結束程序不停止的原因分析及解決方法,感興趣的朋友一起看看吧2025-07-07
使用Java?Socket實現(xiàn)GPS定位數(shù)據(jù)處理
在許多應用場景中,如車輛追蹤、移動設備定位等,GPS定位數(shù)據(jù)的實時獲取和處理至關重要,本文將介紹如何使用Java?Socket編程來接收GPS設備發(fā)送的數(shù)據(jù)并進行處理,需要的朋友可以參考下2024-07-07
SpringBoot對數(shù)據(jù)訪問層進行單元測試的方法詳解
我們公司作為一個面向銀行、金融機構的TO B類企業(yè),頻繁遇到各個甲方爸爸提出的國產(chǎn)化數(shù)據(jù)庫的改造需求,包括OceanBase, TiDB,geldenDB等等,本文就介紹一種快高效、可復用的解決方案——對數(shù)據(jù)訪問層做單元測試,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了什么是構造方法？能否被重寫或重載問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-04-04
Swagger現(xiàn)在已經(jīng)成了最流行的接口文檔生成與管理工具,但是你是否在用的時候也在吐槽,它是真的不好看,接口測試的json數(shù)據(jù)沒法格式化,測試地址如果更改了還要去改配置,接口測試時增加token驗證是真的麻煩…針對Swagger的種種缺點,Knife4j就呼之欲出了.需要的朋友可以參考下2021-05-05
緩存是內(nèi)存當中一塊存儲數(shù)據(jù)的區(qū)域，目的是提高查詢效率，降低服務器和數(shù)據(jù)庫的壓力，這篇文章主要介紹了Mybatis一級緩存和二級緩存，感興趣的同學可以參考閱讀本文2023-04-04
這篇文章主要介紹了Spring Boot 打包與熱部署的操作方法,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
解決java.lang.NoClassDefFoundError:lombok/Data報錯問題
在Java開發(fā)中,使用Lombok庫簡化代碼非常普遍,今天在啟動拉取的git代碼時,遇到了java.lang.NoClassDefFoundError:lombok/Data的報錯,經(jīng)過檢查,發(fā)現(xiàn)錯誤的原因是將Date誤寫為Data,且錯誤地引用了lombok.Data包2024-09-09