數據結構--2:ArrayList與順序表

1.順序表的創建? ? ? ? ? ? ? ? ?2.常見操作? ? ? ? ? ? ? ? ? ?3.遍歷? ? ? ? ? ? ? ? ? 4.擴容機制? ? ? ? ? ? ? ? ? 5.例子

1.順序表的創建

在集合框架中,ArrayList是?個普通的類,實現了List接口,具體框架圖如下:

2.常見操作

代碼實現

import java.util.ArrayList;
import java.util.List;public class Test1 {public static void main(String[] args) {//ArrayList<Integer> arrayList1 = new ArrayList<>();List<Integer> list = new ArrayList<>();//尾插   List 是可以直接打印的. 不像數組, 還需要轉成 Stringlist.add(1);list.add(2);list.add(3);list.add(4);list.add(2);System.out.println(list);// add 也可以指定位置來插入. 往下標 2 這個元素之前插入 100. 插入成功之后, 100 元素的下標就是 2 .list.add(2,100);System.out.println(list);// 頭插list.add(0, 200);System.out.println(list);// list.add(100, 300); 顯然不行. 100 下標太大了.下標越界了;但是可以往 6 這個位置插入. 就相當于尾插.list.add(6, 300);System.out.println(list);//插入一組元素List<Integer> list1 = new ArrayList<>();list1.addAll(list);System.out.println(list1);//按照下標刪除  但下標不能超出總長度范圍    也可以同時記錄一下被刪除的元素   返回resultInteger result = list.remove(1);System.out.println(list);System.out.println(result);//按照值來刪除   下標也不能超出指定的范圍  如果 List 中不包含這個值, 就返回 falseboolean isRemoved = list.remove(Integer.valueOf(1));System.out.println(list);System.out.println(isRemoved);// 雖然是刪除 2 這個值, 由于有多個, 實際上只刪除了第一個.list.remove(Integer.valueOf(2));System.out.println(list);//但這樣可以刪除所有2List<Integer> toRemove = new ArrayList<>();toRemove.add(2);list.removeAll(toRemove);System.out.println(list);//獲取元素System.out.println(list.get(1));//修改元素list.set(0,100);System.out.println(list);//清空list1.clear();System.out.println(list1);//判斷某元素是否存在System.out.println(list.contains(3));//返回第一個元素所在的下標System.out.println(list.indexOf(100));//返回最后一個元素所在的下標System.out.println(list.lastIndexOf(100));//截取部分list  subList   [1,3)  前閉后開System.out.println(list.subList(1,3));System.out.println(list);//subList 操作, 并不是創建一個 "副本" (拷貝一份), 而是得到原始 List 的片段.//注:此處 subList 方法的返回值類型是 List<E>,而不是 ArrayList<E>List<Integer> subList = list.subList(1,3);subList.set(0,1);System.out.println(subList);//針對 subList 修改, 也會影響到原始的 ListSystem.out.println(list);//獲取元素個數   sizeSystem.out.println(list.size());list.add(8);System.out.println(list.size());}
}

3.遍歷

ArrayList可以使用三種方式遍歷:for循環+下標、foreach、使用迭代器

import java.util.ArrayList;
import java.util.Iterator;public class Test3 {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(4);for(int i = 0; i < list.size(); i++){System.out.println(list.get(i));// list[i] 這樣的寫法是不行的.}//通過 foreach 遍歷.   num 就會依次被賦值成 list 中的每個元素//這里的 num 只能用來 "讀" 不能用來 "寫"     foreach 本質上就是迭代器寫法的簡化寫法.// 此處 num 是一個臨時變量. 不會影響到 List 中的元素的.for(Integer num: list){System.out.println(num);}//數組不具備的方式, 通過 "迭代器" 來遍歷.  典型的 Java 風格的迭代器寫法. 不僅僅是在集合類里.Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()){//通過 next 獲取到 list 中的每個元素. 通過 hasNext 判定是否遍歷結束.System.out.println(iterator.next());}}}

4.擴容機制

ArrayList是?個動態類型的順序表,即:在插入元素的過程中會自動擴容

5.例子

5.1?模擬撲克牌

import java.util.ArrayList;
import java.util.Collections;// 通過一個類, 表示 "一張牌"
class Card{private String rank; //點數private String suit; //花色public Card(String rank, String suit){this.rank = rank;this.suit = suit;}// 搞一個 toString, 方便后續打印牌的內容public String toString(){return "(" + suit + rank + ")";}
}public class shi_xian_pukepai {// 通過這個方法創建一副撲克牌. 通過 ArrayList 表示了.  deck--一副牌private static ArrayList<Card> creatDeck() {ArrayList<Card> deck = new ArrayList<>();// 把 4 種花色, 每個花色 13 個牌都創建進去.  不包含大小王String[] suits = {"?", "?", "?", "?"};for (String suit : suits) {//處理2-10for (int i = 2; i <= 10; i++) {Card card = new Card("" + i, suit);deck.add(card);}//處理JQKAdeck.add(new Card("J", suit));deck.add(new Card("Q", suit));deck.add(new Card("K", suit));deck.add(new Card("A", suit));}return deck;}public static void main(String[] args) {//Card card = new Card("A", "?");//System.out.println(card);ArrayList<Card> deck = creatDeck();System.out.println(deck);// 洗牌, 標準庫有一個現成的方法, shuffle, 就可以完成洗牌. 打亂 ArrayList 中的順序.// 修改原有的 ArrayList.Collections.shuffle(deck);System.out.println("洗牌后: " + deck);// 發牌, 假設有 3 個玩家, 每個玩家發 5 張牌. (梭哈)   使用三個 ArrayList 表示三個玩家.
//        ArrayList<Card> player1 = new ArrayList<>();
//        ArrayList<Card> player2 = new ArrayList<>();
//        ArrayList<Card> player3 = new ArrayList<>();// 通過類似于 "二維數組" 的方式, 構造二維的 ArrayList.ArrayList<ArrayList<Card>> players = new ArrayList<>();for(int i = 0; i < 3; i++){players.add(new ArrayList<>());}// 發牌, 取出牌堆中的第一張牌, 放到第一個玩家的 ArrayList 中.// 再取出牌堆中的第二張牌, 放到第二個玩家的 ArrayList 中. 以此類推.   發 5 個輪次for(int round = 0; round < 5; round++){for(int i = 0; i < 3; i++){// 取出牌堆中的第一張牌Card card = deck.remove(0);// 放到對應玩家的 ArrayList 中ArrayList<Card> player = players.get(i);player.add(card);}}// 打印每個玩家的牌for(int i = 0; i < 3; i++){ArrayList<Card> player = players.get(i);System.out.println("玩家" + (i+1) + "的牌" + player);}}
}

5.2 楊輝三角

import java.util.ArrayList;
import java.util.List;public class yang_hui_san_jiao {public List<List<Integer>> generate(int numRows) {List<List<Integer>> result = new ArrayList<>();//每次循環,構造一行數據for (int i = 0; i < numRows; i++) {//構造ArrayList 表示當前行List<Integer> row = new ArrayList<>();//填寫若干列for (int j = 0; j <= i; j++) {//針對第一列和最后一列 都是1if (j == 0 || j == i) {row.add(1);}//其他情況  先取出上一行  再找到兩數相加else {List<Integer> lastRow = result.get(i - 1);int curValue = lastRow.get(j - 1) + lastRow.get(j);row.add(curValue);}}//此時這一行構造完 把這一行都添加到 result 中result.add(row);}return result;}
}

6.模擬實現 ArrayList

代碼實現

// 不寫成泛型的方式.  只是保存 String 類型的數據~~
// 泛型方式, 寫起來更麻煩一些. 未來面試的時候, 一般也都不要寫泛型版本的.
public class MyArrayList {private String[] data = null;    // 通過這個數組, 來表示順序表中的元素private int size = 0;    // 表示有效元素的個數.public MyArrayList() {data = new String[10];}  // 默認的初始容量為 10public MyArrayList(int capacity) {if(capacity <= 10) capacity = 10;data = new String[capacity];}@Overridepublic String toString() {// 把有效元素轉為字符串, 并拼接到一起.StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {stringBuilder.append(data[i]);// 如果 i 是 size - 1, 說明是最后一個元素, 不需要加 , 了.if (i < size - 1)  stringBuilder.append(", ");}stringBuilder.append("]");return stringBuilder.toString();}// 實現擴容操作.private void resize() {// 1. 創建更長的數組, 新的數組容量是之前的 1.5 倍.String[] newData = new String[data.length + (data.length >> 1)];// 2. 把舊數組的元素, 復制到新數組上.for (int i = 0; i < size; i++) { newData[i] = data[i]; }// 3. 使用新數組代替舊數組.data = newData;}// 實現尾插操作. 把新的元素添加到順序表末尾.  elem 就是 element(元素) 的縮寫. 時間復雜度 O(1)// 雖然可能觸發擴容 O(N), 但是認為在使用的時候通過設置良好的初始容量, 降低擴容的次數.public void add(String elem) {// 把 elem 放到 data 的最后一個位置上. 也就是下標為 size 的位置.// [0, size) 區間是有效元素.  需要實現擴容邏輯.if (size >= data.length)  resize();  // 擴容操作.data[size] = elem;size++;}// 往中間位置插入. 往 index 元素之前插入, 確保新元素的下標就是 index. 時間復雜度 O(N)public void add(int index, String elem) {// 判定 index 是否合法.  此處是否要寫作 index <= 0  或者 index >= size??  邊界值都需要重點討論.// 如果 index 為 0, 意思是插入完畢后, 元素就處于 0 號位置. 就相當于 "頭插"// 如果 index 為 size, 意思是插入完畢后, 元素處于 size 號位置. 就相當于 "尾插"if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);if (size >= data.length)  resize();   // 擴容操作.// 把元素放到 index 位置上. 進行搬運, 把 index 之后的元素, 都往后移動一個位置.// 需要從后往前遍歷, 代入 size 為 6 的時候, 最后一個元素下標就是 5; 初始的搬運就是把 data[5] 放到 data[6] 上去// 最終的代碼就是 data[i+1] = data[i]是寫作 i >= index 還是 i > index??for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; }// 把新元素放到 index 位置上data[index] = elem;size++;}// 按照下標刪除   返回被刪除的元素的值   時間復雜度 O(N)public String remove(int index){if(index < 0 || index >= size)  throw new IndexOutOfBoundsException("Index: " + index + ", size: " + size);// 提前把刪除的元素的值保存一份. 否則后面搬運的時候就會覆蓋.String elem = data[index];for(int i = index; i < size-1; i++)  data[i] = data[i+1];size--;return elem;}// 按照元素值來刪除  如果刪除成功, 返回 true. 否則, 返回 false.  如果 elem 本身不存在, 就認為是刪除失敗. 時間復雜度 O(N)public boolean remove(String elem) {// 先找到 elem 對應的位置在哪里int removePos = 0;// 找到了. i 這個下標就是要刪除的元素的位置.for (; removePos < size; removePos++) { if (data[removePos].equals(elem)) break; }// 上述循環結束, 有兩種可能:  1. 沒找到 elem, i 和 size 相等了.if (removePos == size) return false;//2. 找到了elem  拿著 removePos 進行刪除  進行搬運操作.for (int i = removePos; i < size - 1; i++)  { data[i] = data[i + 1]; }size--;//第二點也可以直接服用上一個刪除用法  即  remove(removePos)return true;}//獲取下標index的元素   時間復雜度 O(1)public String get(int index){if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);return data[index];}//將下標index位置元素設置為element  時間復雜度 O(1)public void set(int index, String element){if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);data[index] = element;}// 刪除所有元素.  時間復雜度 O(1)  不需要把數組中的每個元素都設為 null 之類的public void clear() { size = 0; }//遍歷, 看 elem 元素是否存在. 存在就返回 true    時間復雜度 O(N)public boolean contains(String elem) {for (int i = 0; i < size; i++) { if(data[i].equals(elem)) return true; }return false;}// 從前往后遍歷, 看 elem 元素是否存在. 存在就返回它的第一個下標. 時間復雜度 O(N)public int indexOf(String elem){for(int i = 0; i < size; i++) { if(data[i].equals(elem)) return i; }return -1;}// 從后往前遍歷, 看 elem 元素是否存在. 存在就返回它的最后一個下標. 時間復雜度 O(N)public int lastIndexOf(String elem){for(int i = size - 1; i >= 0; i--) { if(data[i].equals(elem)) return i; }return -1;}// 截取[fromIndex, toIndex) 區間的元素.   時間復雜度 O(N)// 創建一個新的 MyArrayList 對象. 把上述區間的元素, 添加到新的對象中即可.public MyArrayList subList(int fromIndex, int toIndex){// 注意邊界值. fromIndex 如果為 0, 是合法的情況. toIndex 如果是 size, 也是合法的情況// fromIndex == toIndex 的時候, 也是合法, 得到空的區間.if(fromIndex < 0 || toIndex > size || fromIndex > toIndex)throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ", toIndex: " + toIndex);MyArrayList subList = new MyArrayList(toIndex-fromIndex);for(int i = fromIndex; i < toIndex; i++){String elem = this.get(i);subList.add(elem);}return subList;}// 測試尾插// 測試代碼也很關鍵. 把每個功能點的測試代碼單獨拎出來, 作為一個測試方法.// 這種測試的思路稱為 "單元測試"private static void text1(){MyArrayList list = new MyArrayList();list.add("Hello");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");list.add("word");System.out.println(list);// 還有辦法, 不通過打印, 也能看到 list 中的內容. 借助調試器}// 測試中間位置插入private static void text2(){MyArrayList list = new MyArrayList();list.add(0,"a");list.add(0,"b");list.add(0,"c");list.add(0,"d");list.add(2,"x");System.out.println(list);}// 測試刪除操作private static void test3(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");String elem = list.remove(1);System.out.println(elem);System.out.println(list);}private static void test4(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");boolean ret = list.remove("dd");System.out.println(ret);System.out.println(list);}private static void test5(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");System.out.println(list.contains("bb"));}private static void test6(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");System.out.println(list.indexOf("bb"));}private static void test7(){MyArrayList list = new MyArrayList();list.add("aa");list.add("bb");list.add("cc");list.add("dd");System.out.println(list.subList(1,3));}public static void main(String[] args) {test7();}}







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

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

相關文章

【Kubesphere】K8s容器無法訪問內網xx網絡問題

問題遇到的現象和發生背景 Kubesphere中運行的一個容器&#xff0c;可以ping通我們公司內網網段172.16.XX.XX&#xff0c;但是在容器內無法ping通192.168.5.XX&#xff0c;但是我在宿主機是可以ping通192.168.5.XX&#xff0c;這個192.168.5.XX是通過xx設備接進來的&#xff0c…

【開發語言】Groovy語言:Java生態中的動態力量

博客目錄一、Groovy 的誕生與發展二、核心特性深度解析1. 與 Java 的無縫集成2. 動態類型與可選靜態類型3. 強大的集合操作三、Groovy 在實際開發中的應用場景1. 構建自動化&#xff08;Gradle&#xff09;2. 測試開發&#xff08;Spock 框架&#xff09;3. 腳本任務自動化四、…

Obsidian 1.9.10升級

概述 Obsidian發布了更新版本1.9.10&#xff0c;是一次比較大的升級&#xff0c;尤其是增加了一些以前沒有的核心插件&#xff0c;尤其是重磅的數據庫功能。雖然可能還是比較初期&#xff0c;但是這意味著OB還是往更好的方向進化了。 本文以一些目前的視頻教程加自己的實際上手…

內容審計技術

一、 內容審計需求背景1.網絡安全法要求明確責任人&#xff1a;制定內部安全管理制度和操作規程&#xff0c;落實安全保護責任。監測、記錄并保留日志&#xff1a;采取監測、記錄網絡運行狀態、網絡安全事件的技術措施&#xff0c;并按照規定留存相關網絡日志不少于六個月。采取…

反序列化漏洞

php反序列化 1.什么是序列化和反序列化 office word是程序 doc/docx是數據 保存word文件&#xff1a;程序--保存(序列化)-->數據文件 打開word文件&#xff1a;程序--加載數據文件-->還原(反序列化) 游戲存檔&#xff1a;角色等級&#xff0c;任務&#xff0c;人物坐…

Lecture 4 Mixture of experts課程筆記

什么是MoE?用&#xff08;多個&#xff09;大型前饋網絡和一個選擇器層取代大型前饋網絡。你可以在不影響浮點運算次數的情況下增加專家數量。 MoE受歡迎的原因 相同的浮點運算次數&#xff0c;更多的參數表現更好訓練混合專家模型&#xff08;MoEs&#xff09;速度更快訓練混…

微服務架構的演進:從 Spring Cloud Netflix 到云原生新生態

過去十年,Spring Cloud 憑借 Netflix 全家桶(Eureka、Ribbon、Hystrix、Zuul 等)幾乎成為 Java 微服務的事實標準。但隨著這些核心組件逐步停止更新或進入維護模式,微服務架構正經歷一場深刻的演進。新的微服務架構更加注重 云原生兼容性、社區活躍度、企業級穩定性和低運維…

網絡流量分析——基礎知識

文章目錄所需技能和知識TCP/IP 堆棧和 OSI 模型基本網絡概念常用端口和協議IP 數據包和子層的概念協議傳輸封裝環境與設備常見的流量分析工具BPF 語法執行網絡流量分析NTA工作流程NTA工作流程網絡 - 第 1-4 層OSI / TCP-IP 模型尋址機制MAC地址IP 尋址IPv4IPv6IPv6 尋址類型IPv…

ansible playbook 實戰案例roles | 實現基于 IHS 的 AWStats 訪問監控系統

文章目錄一、核心功能描述二、roles內容2.1 文件結構2.2 主配置文件2.3 tasks文件內容三、files文件內容四、關鍵價值免費個人運維知識庫&#xff0c;歡迎您的訂閱&#xff1a;literator_ray.flowus.cn 一、核心功能描述 這個 Ansible Role 的核心功能是&#xff1a;?實現 ?…

DELL服務器 R系列 IPMI的配置

1、iDRAC功能默認都是關閉&#xff0c;需要在BIOS面啟用&#xff0c;首先重啟計算機&#xff0c;按F2然后進入BIOS&#xff0c;選擇iDRAC Setting進行iDRAC配置 2、重置一下idrac卡-重置才能恢復默認密碼 3、進入iDRAC Setting之后&#xff0c;選擇設置網絡Network 4、啟用iDRA…

模式組合應用-橋接模式(一)

寫在前面Hello&#xff0c;我是易元&#xff0c;這篇文章是我學習設計模式時的筆記和心得體會。如果其中有錯誤&#xff0c;歡迎大家留言指正&#xff01;文章為設計模式間的組合使用&#xff0c;涉及代碼較多&#xff0c;個人覺得熟能生巧&#xff0c;希望自己能從中學習到新的…

【clion】visual studio的sln轉cmakelist并使用clion構建32位

我想在linux上運行,所以先轉為cmake工程 例如可以把exe mfc 部分不構建,這樣ubuntu就不用移植。 先轉cmakelist,而后clion完成win32的構建,與vs構建對比,驗證腳本正確性。 Vcxproj2CMake https://github.com/gns333/Vcxproj2CMake cmakeconverter https://github.com/pave…

MySQL之分區功能

序言 隨著業務發展&#xff0c;我們維護的項目數據庫中的數據可能會越來越大&#xff0c;那么單張表的數據變多后&#xff0c;接口查詢效率可能會變慢&#xff0c;那我們就直接照抄大廠常見的分庫分表嗎&#xff1f;—— 當然不是的&#xff0c;分庫分表不是萬能的。 分庫分表…

java_spring boot 中使用 log4j2 及 自定義layout設置示例

1. log4j2對比 原始Logback 優勢 對于 Spring Boot 3.x&#xff0c;Logback 是默認日志框架&#xff0c;但在高并發、異步日志場景下&#xff0c;Log4j2 通常表現更優。當業務百萬級用戶、微服務、日志量大時&#xff1a; ? 1. Logback&#xff08;默認 Spring Boot 集成&am…

記錄Webapi Excel 導出

文章目錄1、helper2、control3、前端 axios記錄webapi excel 導出File示例.NET8.0 NPOI2.731、helper using NPOI.SS.UserModel; using NPOI.XSSF.UserModel; using System.Data; using System.IO; /// <summary> /// 導出EXCEL /// </summary> public class Exce…

VPS服務器安全審計方案:從風險評估到防護實施

隨著云計算技術的快速發展&#xff0c;VPS服務器已成為企業信息化建設的重要基礎設施。隨之而來的安全威脅也日益增多&#xff0c;如何通過專業的安全審計方案保障VPS服務器的穩定運行成為關鍵課題。本文將系統闡述從漏洞掃描到應急響應的全周期安全審計實施策略&#xff0c;幫…

libmicrohttpd 入門

libmicrohttpd 是一個小型的 C 庫&#xff0c;用于在項目中嵌入 HTTP 服務器功能。它設計簡單、輕量級&#xff0c;適合需要 HTTP 接口但不想要大型 Web 服務器開銷的應用程序。 安裝 libmicrohttpd Linux 系統 在基于 Debian/Ubuntu 的系統上&#xff1a; bash sudo apt-…

【網絡】使用 DNAT 進行負載均衡時,若未配置配套的 SNAT,回包失敗

【網絡】iptables 1 概念 【網絡】iptables 2 查看規則 【網絡】使用 DNAT 進行負載均衡時&#xff0c;若未配置配套的 SNAT&#xff0c;回包失敗 【網絡】回包路由原理 使用 DNAT 進行負載均衡時&#xff0c;若未配置配套的 SNAT&#xff0c;后端服務器將直接回包給客戶端&am…

深入解析GCC:從編譯原理到嵌入式底層實戰

繼續更新編譯器底層系列&#xff01;&#xff01;&#xff01;硬核C語言的屠龍之術&#xff1a;從GCC到匯編的底層征途&#xff08;一&#xff09;總綱&#xff1a; 恭喜你&#xff0c;決定踏上這條通往嵌入式大佬的硬核之路。這條路的起點&#xff0c;不是C語言的語法書&#…

最新MySQL面試題(2025超詳細版)

2025最新超詳細MySQL面試題 文章目錄2025最新超詳細MySQL面試題[toc]一、 SQL 和基本操作1. SQL的執行順序2. 如何優化MySQL查詢3. 常用的聚合函數4. 數據庫事務5. 事務的四大特性(ACID)6. 視圖7. MySQL中使用LIMIT子句進行分頁8. MySQL中使用變量和用戶定義的函數9. MySQL中的…