【Java 數據結構】List，ArrayList與順序表

目錄

一. List

1.1 什么是List

1.2 List 的常見方法

1.3 List 的使用

二. 順序表

2.1 什么是順序表

2.2?實現自己的順序表

2.2.1 接口實現

2.2.2 實現順序表

三. ArrayList

3.1?ArrayList簡介

3.2 ArrayList的三個構造方法

3.2.1 無參構造方法

3.2.2 帶一個參數的構造方法

3.3 ArrayList的常見方法

3.4?ArrayList 的遍歷

3.4.1 直接打印

3.4.2?for循環遍歷

3.4.3 借助for-each遍歷

3.4.4 迭代器遍歷

一. List

1.1 什么是List

在集合框架中，List是一個接口，繼承自Collect

站在數據結構的角度來看，List就是一個線性表，即n個具有相同類型元素的有限序列，在該序列上可以執行增刪改查以及變量等操作

1.2 List 的常見方法

下面是List接口中的一些常見方法

1.3 List 的使用

由于List 是一個接口，不能直接實例化對象，但是在集合框架中，ArrayList和LinkedList都實現了List接口

二. 順序表

2.1 什么是順序表

順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般采用數組存儲，ArrayList就是順序表的一種實現形式

2.2?實現自己的順序表

在學習ArrayList之前，我們可以先試著寫一個自己實現的順序表，能幫助我們在使用ArrayList的方法以及了解它時更加得心應手

2.2.1 接口實現

public class IList {public void add(int data) { }// 在 pos 位置新增元素public void add(int pos, int data) { }// 判定是否包含某個元素public boolean contains(int toFind) { return true; }// 查找某個元素對應的位置public int indexOf(int toFind) { return -1; }// 獲取 pos 位置的元素public int get(int pos) { return -1; }// 給 pos 位置的元素設為 valuepublic void set(int pos, int value) { }//刪除第?次出現的關鍵字keypublic void remove(int toRemove) { }// 獲取順序表?度public int size() { return 0; }// 清空順序表public void clear() { }// 打印順序表，注意：該?法并不是順序表中的?法，為了?便看測試結果給出的public void display() { }
}

下面，我們自己的順序表將會實現并重寫IList中的所有方法

2.2.2 實現順序表

import java.util.Arrays;class EmptyListException extends RuntimeException{public EmptyListException(String message) {super(message);}
}class IndexException extends RuntimeException{public IndexException(String message) {super(message);}
}
public class MyArrayList implements IList{public int arr[];public final int Initial_Capacity=10;public int Used_size;public MyArrayList() {this.arr = new int [Initial_Capacity];}@Overridepublic void add(int data) {if(is_full()){grow();}this.arr[Used_size]=data;Used_size++;}@Overridepublic void add(int pos, int data) {if(is_full()){grow();}checkPos(pos);for (int i =Used_size-1; i>=pos; i--) {arr[i+1]=arr[i];}arr[pos]=data;Used_size++;}public boolean is_full(){if(arr.length==Used_size){return true;}return false;}public void grow(){this.arr= Arrays.copyOf(arr,arr.length*2);}@Overridepublic boolean contains(int toFind) {for (int i = 0; i <arr.length; i++) {if(arr[i]==toFind){return true;}}return false;}@Overridepublic int indexOf(int toFind) {for (int i = 0; i <arr.length; i++) {if (arr[i] == toFind) {return i;}}return -1;}@Overridepublic int get(int pos) {check(pos);isEmpty();return arr[pos];}public void check(int pos){if(pos<0||pos>=Used_size){throw new IndexException(pos+"位置下標訪問不合法");}}public void checkPos(int pos){if(pos<0||pos>Used_size){throw new IndexException(pos+"位置下標訪問不合法");}}public void isEmpty(){if(Used_size==0){throw new EmptyListException("該表為空表");}}@Overridepublic void set(int pos, int value) {check(pos);arr[pos]= value;}@Overridepublic void remove(int toRemove) {int index=indexOf(toRemove);if(index==-1){System.out.println("沒有要刪除的元素");return;}for (int i =index; i <Used_size-1; i++) {arr[i]=arr[i+1];}Used_size--;}@Overridepublic int size() {return Used_size;}@Overridepublic void clear() {for (int i = 0; i <Used_size; i++) {arr[i]=0;}Used_size=0;//如果數組中的是引用數據類型的元素時，一定要將其全部置為null（避免空間造成浪費）}@Overridepublic void display() {for (int i = 0; i <this.Used_size; i++) {System.out.print(arr[i]+" ");}System.out.println();}
}

注意：

  • 在刪除和特定位置添加元素的方法中采用的是覆蓋的思想，下面是添加元素到特定位置的流程圖（將6添加到3下標位置）

  • 在 clear（）中如果要清空的順序表是存放引用數據類型的話，一定要將其全部設置為null

三. ArrayList

3.1?ArrayList簡介

在集合框架中，ArrayList是一個普通的類，實現了List接口。具體框架如下：

注意：

  • ArrayList是以泛型的形式實現的，使用時必須要先實例化
  • ArrayList底層是一段連續的空間，并且可以動態擴容，是一個動態類型的順序表

3.2 ArrayList的三個構造方法

3.2.1 無參構造方法

下面是ArrayList類中的源碼截取：

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1           /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}public void add(int index, E element) {rangeCheckForAdd(index);modCount++;final int s;Object[] elementData;if ((s = size) == (elementData = this.elementData).length)elementData = grow();System.arraycopy(elementData, index,elementData, index + 1,s - index);elementData[index] = element;size = s + 1;}

解釋：

這里的 elementData 是 ArrayList 內部用于存儲元素的數組，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一個空數組。當使用無參構造方法創建 ArrayList 時，實際上只是將 elementData 初始化為一個空數組。當向 ArrayList 中添加第一個元素（僅限添加的第一個元素）時， ArrayList 會自動擴容，將數組容量擴展為默認容量（通常是10）。

3.2.2 帶一個參數的構造方法

  • ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}

解釋：通過這個構造方法，當傳入一個大于0的整數作為參數時， ArrayList 會創建一個具有指定容量的數組來存儲元素，這樣可以在已知元素大概數量的情況下，減少數組擴容的次數，提高性能。如果傳入0，則使用一個空數組。如果傳入負數，會拋出異常，因為容量不能為負

  • ArrayList(Collection<? extends E> c)
 public ArrayList(Collection<? extends E> c) {Object[] a = c.toArray();if ((size = a.length) != 0) {if (c.getClass() == ArrayList.class) {elementData = a;} else {elementData = Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData = EMPTY_ELEMENTDATA;}}

解釋：使用集合類來構造ArrayList，將該集合類中的所有元素用來構造ArrayList，和ArrayList中的 addAll（Collection<? extends E> c）的作用類似，其中Collection<? extends E> c?表示可以傳入實現了Collection接口并且泛型參數類型是E/E子類的集合類，下面是一個例子：這里不是一個集合類一個元素（與List的嵌套不同）

public static void main(String[] args) {ArrayList<Integer> list0=new ArrayList<>();list0.add(1);list0.add(2);ArrayList<Integer> list1=new ArrayList<>();list1.add(1);list1.add(2);ArrayList<Integer> list=new ArrayList<>(list0);//使用List0這個集合類來構造listlist.add(100);//向list中添加元素list.addAll(list1); //向list中來添加集合類System.out.println(list);System.out.println(list.size());}打印結果：
[1, 2, 100, 1, 2]
5
public static void main(String[] args) {ArrayList<ArrayList<Integer>> lists=new ArrayList<>();ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);lists.add(list3);System.out.println(lists.size());}打印結果：1

3.3 ArrayList的常見方法

ArrayList的方法很多，以下只列舉常見的幾種：

注意：

  • LIst<E>subList(int formIndex,int toIndex) 這個方法要重點注意（是個坑），1. 這個方法的返回值實際上是截取list部分的首地址，如果改變subList中的元素，被截取的原list中的元素也會發生改變，2. 截取部分是[? )

3.4?ArrayList 的遍歷

3.4.1 直接打印

 public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);System.out.println(list3);}打印結果：[1,2,3]

3.4.2?for循環遍歷

public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();for (int i = 0; i <list3.size(); i++) {System.out.print(list3.get(i)+" ");}System.out.println();}打印結果：1 2 3

3.4.3 借助for-each遍歷

public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);for(Integer integer: list3){System.out.print(integer+" ");}}打印結果：1 2 3

3.4.4 迭代器遍歷

 public static void main(String[] args) {ArrayList<Integer> list3=new ArrayList<>();list3.add(1);list3.add(2);list3.add(3);Iterator<Integer> it=list3.iterator();while(it.hasNext()){System.out.print(it.next()+" ");}System.out.println();ListIterator<Integer> it2=list3.listIterator(list3.size());while(it2.hasPrevious()){  //倒著打印System.out.print(it2.previous()+" ");}System.out.println();ListIterator<Integer> it3=list3.listIterator(1);while(it3.hasNext()){   //從指定位置打印System.out.print(it3.next()+" ");}}打印結果：
1 2 3 
3 2 1 
2 3

注意：

  • 原理：Arraylist中重寫了literable接口中iterator（）方法（），該方法的返回值是一個實現了Iterator接口的類Itr（Itr類是一個定義在ArrayList類內部的的一個私有內部類）的實例化對象（Iterator接口沒有繼承任何接口），通過這個對象可以調用Iterator接口的各種方法進行遍歷
  • ListIterator接口?實際上擴展了 Iterator接口，新增hasPrevious（）和Previous（）等方法，且在調用ListIterator（）可傳入參數，從特定位置進行打印，使得打印更加靈活
  • ArrayList的擴容機制是擴1.5倍

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/77760.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/77760.shtml
英文地址，請注明出處：http://en.pswp.cn/web/77760.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

18.第二階段x64游戲實戰-MFC列表框

18.第二階段x64游戲實戰-MFC列表框

免責聲明&#xff1a;內容僅供學習參考&#xff0c;請合法利用知識&#xff0c;禁止進行違法犯罪活動&#xff01; 本次游戲沒法給 內容參考于&#xff1a;微塵網絡安全 上一個內容&#xff1a;17.第二階段x64游戲實戰-人工遍歷二叉樹結構 現在找到了附近npc列表&#xff0…
閱讀更多...
如何解決 Xcode 簽名證書和 Provisioning Profile 過期問題

如何解決 Xcode 簽名證書和 Provisioning Profile 過期問題

在 iOS 應用開發過程中&#xff0c;簽名證書和 Provisioning Profile 是確保應用安全性和合法性的關鍵組件。然而&#xff0c;當這些證書或配置文件過期時&#xff0c;開發者可能會遇到編譯或歸檔失敗的問題。本文將詳細介紹如何解決 Xcode 中“iOS Distribution”證書未找到和…
閱讀更多...
SpringBoot Actuator未授權訪問漏洞的全面解析與解決方案

SpringBoot Actuator未授權訪問漏洞的全面解析與解決方案

引言 SpringBoot Actuator 作為應用監控與管理的核心組件，為開發者提供了豐富的系統自省和運維能力。然而，其默認配置中可能存在的未授權訪問漏洞，已成為企業安全防護的潛在風險。本文將從漏洞原理、影響范圍、檢測方法到解決方案，系統性地剖析該問題，并提供覆蓋開發、運維…
閱讀更多...
gin框架學習筆記

gin框架學習筆記

Gin 是一個基于 Go 語言的高性能 Web 框架 gin下載 在已有的go項目直接終端輸入 go get -u github.com/gin-gonic/gin hello world快速上手 package mainimport ("github.com/gin-gonic/gin" )func main() {router : gin.Default()router.GET("/", func…
閱讀更多...
linux中由于編譯選項-D_OS64BIT導致的核心已轉儲問題

linux中由于編譯選項-D_OS64BIT導致的核心已轉儲問題

linux中由于編譯選項-D_OS64BIT導致的核心已轉儲問題排查解決&#xff1a; 原因&#xff1a; a.so b.so a.so使用b.so 程序1 程序2 使用a.so 程序1運行正常&#xff0c;程序2啟動后提示核心已轉儲。 程序1和程序2運行的代碼都一致&#xff0c;只執行創建xApplication app&…
閱讀更多...
什么是ICSP編程

什么是ICSP編程

ICSP編程介紹 ICSP 編程&#xff08;In-Circuit Serial Programming&#xff09;&#xff0c;即“在線串行編程”&#xff0c;是一種通過 SPI 協議 直接對微控制器&#xff08;如 Arduino 的 ATmega328P&#xff09;進行編程的技術&#xff0c;無需移除芯片。它常用于以下場景…
閱讀更多...
基于Vue3和OpenLayers的WebGIS示例程序

基于Vue3和OpenLayers的WebGIS示例程序

筆記參考教程來源于B站UP主znlgis的視頻合集&#xff1a;https://space.bilibili.com/161342702&#xff0c;直播使用的源碼地址&#xff1a;https://github.com/OpenGisToolbox。 Demo合集分為5大部分&#xff0c;分別是&#xff1a;基礎環境搭建、項目搭建、GeoServer Rest A…
閱讀更多...
UBUS 通信接口的使用——添加一個object對象（ubus call）

UBUS 通信接口的使用——添加一個object對象（ubus call）

1&#xff0c;引入 ubus提供了一種多進程通信的機制。存在一個守護進程ubusd&#xff0c;所以進程都注冊到ubusd&#xff0c;ubusd進行消息的接收、分發管理。 ubus對多線程支持的不好&#xff0c;例如在多個線程中去請求同一個服務&#xff0c;就有可能出現不可預知的結果。 …
閱讀更多...
【Python魔法方法（特殊方法）】

【Python魔法方法（特殊方法）】

在 Python 中&#xff0c;許多運算符都可以進行重載&#xff0c;以下是一些常見運算符及其對應的魔法方法&#xff08;特殊方法&#xff09;&#xff1a; 算術運算符 加法 &#xff1a;__add__ 用于定義對象相加的行為。例如&#xff0c;當你對兩個自定義類的實例使用 運算符…
閱讀更多...
（三十二）Android開發中AppCompatActivity和Activity之間的詳細區別

（三十二）Android開發中AppCompatActivity和Activity之間的詳細區別

在 Android 開發中&#xff0c;AppCompatActivity 和 Activity 是兩個核心類&#xff0c;用于創建和管理應用程序的用戶界面。盡管它們功能上有重疊&#xff0c;但它們之間存在顯著的區別。本文將詳細講解 AppCompatActivity 和 Activity 的區別&#xff0c;并結合代碼示例和具…
閱讀更多...
【 C++核心知識點面試準備：從內存管理到STL與模板 】

【 C++核心知識點面試準備：從內存管理到STL與模板 】

一、動態內存管理&#xff1a;new/delete與底層原理 核心問題1&#xff1a;new/delete vs malloc/free 區別對比&#xff1a; 特性new/deletemalloc/free類型安全自動推導類型&#xff0c;無需轉型返回void*&#xff0c;需強制轉型生命周期自動調用構造/析構函數需手動初始化…
閱讀更多...
軟考高項（信息系統項目管理師）第 4 版全章節核心考點解析（第4版課程精華版）

軟考高項（信息系統項目管理師）第 4 版全章節核心考點解析（第4版課程精華版）

一、核心輸入輸出速記體系&#xff08;力揚老師獨家口訣&#xff09; &#xff08;一&#xff09;規劃階段萬能輸入&#xff08;4 要素&#xff09; 口訣&#xff1a;章程計劃&#xff0c;組織事業 ? 精準對應&#xff08;ITTO 核心輸入&#xff09;&#xff1a; 章程&#…
閱讀更多...
ASP.NET CORE部署IIS的三種方式

ASP.NET CORE部署IIS的三種方式

ASP.NET Core 部署方式對比 本文檔對比了三種常見的 ASP.NET Core 應用&#xff08;如你的 DingTalkApproval 項目&#xff09;部署到 Windows 10 上 IIS 服務器的方式&#xff1a;dotnet publish&#xff08;手動部署&#xff09;、Web Deploy&#xff08;直接發布到 IIS&…
閱讀更多...
基于共享上下文和自主協作的 RD Agent 生態系統

基于共享上下文和自主協作的 RD Agent 生態系統

在llmangentmcp這個框架中&#xff1a; LLM&#xff1a; 依然是智能體的“大腦”&#xff0c;賦予它們理解、推理、生成和規劃的能力&#xff0c;并且也用于處理和利用共享上下文。Agent&#xff1a; 具備特定 R&D 職能的自主單元&#xff0c;它們感知共享上下文&#xff0…
閱讀更多...
zephyr架構下Bluetooth advertising接口

zephyr架構下Bluetooth advertising接口

目錄 概述 1 函數接口 2 主要函數介紹 2.1 bt_le_adv_start函數 2.1.1 函數功能介紹 2.1.2 典型使用示例 2.1.3 廣播間隔 2.1.4 注意事項 2.2 bt_le_adv_stop 函數 2.2.1 函數功能 2.2.2 使用方法介紹 2.2.3 實際應用示例 2.2.4 關鍵注意事項 2.2.5 常見問題解決 …
閱讀更多...
8、HTTPD服務--ab壓力測試

8、HTTPD服務--ab壓力測試

一、ab壓力測試 # ab ‐c 100 ‐n 1000 http://vedio.linux.com/index.html 2 This is ApacheBench, Version 2.3 <$Revision: 1430300 $> 3 Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/ 4 Licensed to The Apache Software Foundation,…
閱讀更多...
E2E 測試

E2E 測試

以下是關于端到端（E2E）測試的基本知識總結： 一、E2E 測試核心認知 1. 定義與價值定位 "模擬真實用戶在完整應用環境中的操作流程"核心價值： 驗證跨系統/模塊的集成功能檢測用戶流程中的關鍵路徑保障核心業務場景的可用性測試金字塔定位：單元測試（70%） → 集…
閱讀更多...
python之數字類型的操作

python之數字類型的操作

Python數據類型與操作符完全指南&#xff1a;詳解各類數據操作技巧 目錄 數字類型 字符串 列表 元組 字典 集合 布爾 通用操作符 注意事項 1. 數字類型&#xff08;int, float, complex&#xff09; 數字類型是Python中最基礎的數據類型&#xff0c;支持多種數學運算…
閱讀更多...
基于Spring Boot+Vue 網上書城管理系統設計與實現(源碼+文檔+部署講解）

基于Spring Boot+Vue 網上書城管理系統設計與實現(源碼+文檔+部署講解）

技術范圍&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬蟲、數據可視化、小程序、安卓app、大數據、物聯網、機器學習等設計與開發。 主要內容&#xff1a;免費功能設計、開題報告、任務書、中期檢查PPT、系統功能實現、代碼編寫、論文編寫和輔導、論文…
閱讀更多...
從拒絕采樣到強化學習，大語言模型推理極簡新路徑！

從拒絕采樣到強化學習，大語言模型推理極簡新路徑！

大語言模型&#xff08;LLMs&#xff09;的推理能力是當下研究熱點&#xff0c;強化學習在其復雜推理任務微調中廣泛應用。這篇論文深入剖析了相關算法&#xff0c;發現簡單的拒絕采樣基線方法表現驚人&#xff0c;還提出了新算法。快來一探究竟&#xff0c;看看這些發現如何顛…
閱讀更多...
最新文章

Copyright @ 2022~2023