線性容器

2024-02-16 13:46 更新

線性容器實現(xiàn)能按順序訪問的數(shù)據(jù)結構，其底層主要通過數(shù)組實現(xiàn)，包括ArrayList、Vector、List、LinkedList、Deque、Queue、Stack七種。

線性容器，充分考慮了數(shù)據(jù)訪問的速度，運行時（Runtime）通過一條字節(jié)碼指令就可以完成增、刪、改、查等操作。

ArrayList

ArrayList即動態(tài)數(shù)組，可用來構造全局的數(shù)組對象。 當需要頻繁讀取集合中的元素時，推薦使用ArrayList。

ArrayList依據(jù)泛型定義，要求存儲位置是一片連續(xù)的內存空間，初始容量大小為10，并支持動態(tài)擴容，每次擴容大小為原始容量的1.5倍。

ArrayList進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(element: T)函數(shù)每次在數(shù)組尾部增加一個元素。

通過insert(element: T, index: number)在指定位置插入一個元素。

訪問元素

通過arr[index]獲取指定index對應的value值，通過指令獲取保證訪問速度。

通過forEach(callbackFn: (value: T, index?: number, arrlist?: ArrayList<T>) => void, thisArg?: Object): void訪問整個ArrayList容器的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數(shù)據(jù)訪問。

修改元素

通過arr[index] = xxx修改指定index位置對應的value值。

刪除元素

通過remove(element: T)刪除第一個匹配到的元素。

通過removeByRange(fromIndex: number, toIndex:number)刪除指定范圍內的元素。

Vector

說明

API version 9開始，該接口不再維護，推薦使用ArrayList。

Vector是指連續(xù)存儲結構，可用來構造全局的數(shù)組對象。Vector依據(jù)泛型定義，要求存儲位置是一片連續(xù)的內存空間，初始容量大小為10，并支持動態(tài)擴容，每次擴容大小為原始容量的2倍。

Vector和ArrayList相似，都是基于數(shù)組實現(xiàn)，但Vector提供了更多操作數(shù)組的接口。Vector在支持操作符訪問的基礎上，還增加了get/set接口，提供更為完善的校驗及容錯機制，滿足用戶不同場景下的需求。

Vector進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(element: T)函數(shù)每次在數(shù)組尾部增加一個元素。

通過insert(element: T, index: number)在指定位置插入一個元素。

訪問元素

通過vec[index]獲取指定index對應的value值，通過指令獲取保證訪問速度。

通過get(index: number)獲取指定index位置對應的元素。

通過getLastElement()獲取最后一個元素。

通過getIndexOf(element:T)獲取第一個匹配到元素的位置。

通過getLastIndexOf(element:T)獲取最后一個匹配到元素的位置。

通過forEach(callbackFn: (value: T, index?: number, Vector?: Vector<T>) => void, thisArg?: Object)訪問整個Vector的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數(shù)據(jù)訪問。

修改元素

通過vec[index]=xxx修改指定index位置對應的value值。

通過set(index:number,element:T)修改指定index位置的元素值為element。

通過setLength(newSize:number)設置Vector的長度大小。

刪除元素

通過removeByIndex(index:number)刪除index位置對應的value值。

通過remove(element:T)刪除第一個匹配到的元素。

通過removeByRange(fromIndex:number,toIndex:number)刪除指定范圍內的元素。

List

List可用來構造一個單向鏈表對象，即只能通過頭節(jié)點開始訪問到尾節(jié)點。List依據(jù)泛型定義，在內存中的存儲位置可以是不連續(xù)的。

List和LinkedList相比，LinkedList是雙向鏈表，可以快速地在頭尾進行增刪，而List是單向鏈表，無法雙向操作。

當需要頻繁的插入刪除時，推薦使用List高效操作。

可以通過get/set等接口對存儲的元素進行修改，List進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(element: T)函數(shù)每次在數(shù)組尾部增加一個元素。

通過insert(element: T, index: number)在指定位置插入一個元素。

訪問元素

通過list[index]獲取指定index對應的value值，通過指令獲取保證訪問速度。

通過get(index: number)獲取指定index位置對應的元素。

通過getFirst()獲取第一個元素。

通過getLast()獲取最后一個元素。

通過getIndexOf(element: T)獲取第一個匹配到元素的位置。

通過getLastIndexOf(element: T)獲取最后一個匹配到元素的位置。

通過forEach(callbackfn: (value:T, index?: number, list?: List<T>)=> void,thisArg?: Object)訪問整個List的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數(shù)據(jù)訪問。

修改元素

通過list[index] = xxx修改指定index位置對應的value值。

通過set(index:number, element: T)修改指定index位置的元素值為element。

通過replaceAllElements(callbackFn:(value: T,index?: number,list?: List<T>)=>T,thisArg?: Object)對List內元素進行替換操作。

刪除元素

通過removeByIndex(index:number)刪除index位置對應的value值。

通過remove(element:T)刪除第一個匹配到的元素。

LinkedList

LinkedList可用來構造一個雙向鏈表對象，可以在某一節(jié)點向前或者向后遍歷List。LinkedList依據(jù)泛型定義，在內存中的存儲位置可以是不連續(xù)的。

LinkedList和List相比，LinkedList是雙向鏈表，可以快速地在頭尾進行增刪，而List是單向鏈表，無法雙向操作。

LinkedList和ArrayList相比，插入數(shù)據(jù)效率LinkedList優(yōu)于ArrayList，而查詢效率ArrayList優(yōu)于LinkedList。

當需要頻繁的插入刪除時，推薦使用LinkedList高效操作。

可以通過get/set等接口對存儲的元素進行修改，LinkedList進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(element: T)函數(shù)每次在數(shù)組尾部增加一個元素。

通過insert(index: number, element: T)在指定位置插入一個元素。

訪問元素

通過list[index]獲取指定index對應的value值，通過指令獲取保證訪問速度。

通過get(index: number)獲取指定index位置對應的元素。

通過getFirst()獲取第一個元素。

通過getLast()獲取最后一個元素。

通過getIndexOf(element: T)獲取第一個匹配到元素的位置。

通過getLastIndexOf(element: T)獲取最后一個匹配到元素的位置。

通過forEach(callbackFn: (value: T, index?: number, list?: LinkedList<T>) => void, thisArg?: Object)訪問整個LinkedList的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數(shù)據(jù)訪問。

修改元素

通過list[index]=xxx修改指定index位置對應的value值。

通過set(index: number,element: T)修改指定index位置的元素值為element。

刪除元素

通過removeByIndex(index: number)刪除index位置對應的value值。

通過remove(element: T)刪除第一個匹配到的元素。

Deque

Deque可用來構造雙端隊列對象，存儲元素遵循先進先出以及先進后出的規(guī)則，雙端隊列可以分別從隊頭或者隊尾進行訪問。

Deque依據(jù)泛型定義，要求存儲位置是一片連續(xù)的內存空間，其初始容量大小為8，并支持動態(tài)擴容，每次擴容大小為原始容量的2倍。Deque底層采用循環(huán)隊列實現(xiàn)，入隊及出隊操作效率都比較高。

Deque和Queue相比，Queue的特點是先進先出，只能在頭部刪除元素，尾部增加元素。

Deque和Vector相比，它們都支持在兩端增刪元素，但Deque不能進行中間插入的操作。對頭部元素的插入刪除效率高于Vector，而Vector訪問元素的效率高于Deque。

需要頻繁在集合兩端進行增刪元素的操作時，推薦使用Deque。

Deque進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過insertFront(element: T)函數(shù)每次在隊頭增加一個元素。

增加元素

通過insertEnd(element: T)函數(shù)每次在隊尾增加一個元素。

訪問元素

通過getFirst()獲取隊首元素的value值，但是不進行出隊操作。

通過getLast()獲取隊尾元素的value值，但是不進行出隊操作。

通過popFirst()獲取隊首元素的value值，并進行出隊操作。

通過popLast()獲取隊尾元素的value值，并進行出隊操作。

通過forEach(callbackFn:(value: T, index?: number, deque?: Deque<T>) => void, thisArg?: Object)訪問整個Deque的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數(shù)據(jù)訪問。

修改元素

通過forEach(callbackFn:(value: T, index?: number, deque?: Deque<T>)=> void, thisArg?: Object)對隊列進行修改操作。

刪除元素

通過popFirst()對隊首元素進行出隊操作并刪除。

通過popLast()對隊尾元素進行出隊操作并刪除。

Queue

Queue可用來構造隊列對象，存儲元素遵循先進先出的規(guī)則。

Queue依據(jù)泛型定義，要求存儲位置是一片連續(xù)的內存空間，初始容量大小為8，并支持動態(tài)擴容，每次擴容大小為原始容量的2倍。

Queue底層采用循環(huán)隊列實現(xiàn)，入隊及出隊操作效率都比較高。

Queue和Deque相比，Queue只能在一端刪除一端增加，Deque可以兩端增刪。

一般符合先進先出的場景可以使用Queue。

Queue進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過add(element: T)函數(shù)每次在隊尾增加一個元素。

訪問元素

通過getFirst()獲取隊首元素的value值，但是不進行出隊操作。

通過pop()獲取隊首元素的value值，并進行出隊操作。

通過forEach(callbackFn: (value: T, index?: number, queue?: Queue<T>) => void,thisArg?: Object)訪問整個Queue的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數(shù)據(jù)訪問。

修改元素

通過forEach(callbackFn:(value: T, index?: number, queue?: Queue<T>) => void,thisArg?: Object)對隊列進行修改操作。

刪除元素

通過pop()對隊首進行出隊操作并刪除。

Stack

Stack可用來構造棧對象，存儲元素遵循先進后出的規(guī)則。

Stack依據(jù)泛型定義，要求存儲位置是一片連續(xù)的內存空間，初始容量大小為8，并支持動態(tài)擴容，每次擴容大小為原始容量的1.5倍。Stack底層基于數(shù)組實現(xiàn)，入棧出棧均從數(shù)組的一端操作。

Stack和Queue相比，Queue基于循環(huán)隊列實現(xiàn)，只能在一端刪除，另一端插入，而Stack都在一端操作。

一般符合先進后出的場景可以使用Stack。

Stack進行增、刪、改、查操作的常用API如下：

操作

描述

增加元素

通過push(item: T)函數(shù)每次在棧頂增加一個元素。

訪問元素

通過peek()獲取棧頂元素的value值，但是不進行出棧操作。

通過pop()獲取棧頂?shù)膙alue值，并進行出棧操作。

通過forEach(callbackFn: (value: T, index?: number, stack?: Stack<T>) => void, thisArg?: Object)訪問整個Stack的元素。

通過[Symbol.iterator]():IterableIterator<T>迭代器進行數(shù)據(jù)訪問。

通過locate(element: T)獲取元素對應的位置。

修改元素

通過forEach(callbackFn:(value: T, index?: number, stack?: Stack<T>) => void, thisArg?: Object)對棧內元素進行修改操作。

刪除元素

通過pop()對棧頂進行出棧操作并刪除。

線性容器的使用

此處列舉常用的線性容器ArrayList、Vector、Deque、Stack、List的使用示例，包括導入模塊、增加元素、訪問元素及修改等操作。示例代碼如下所示：

  1. // ArrayList
  2. import ArrayList from '@ohos.util.ArrayList'; // 導入ArrayList模塊
  3. 

  4. let arrayList = new ArrayList();
  5. arrayList.add('a');
  6. arrayList.add(1); // 增加元素
  7. console.info(`result: ${arrayList[0]}`); // 訪問元素
  8. arrayList[0] = 'one'; // 修改元素
  9. console.info(`result: ${arrayList[0]}`);
  10. 

  11. // Vector
  12. import Vector from '@ohos.util.Vector'; // 導入Vector模塊
  13. 

  14. let vector = new Vector();
  15. vector.add('a');
  16. let b1 = [1, 2, 3];
  17. vector.add(b1);
  18. vector.add(false); // 增加元素
  19. console.info(`result: ${vector[0]}`); // 訪問元素
  20. console.info(`result: ${vector.getFirstElement()}`); // 訪問元素
  21. 

  22. // Deque
  23. import Deque from '@ohos.util.Deque'; // 導入Deque模塊
  24. 

  25. let deque = new Deque;
  26. deque.insertFront('a');
  27. deque.insertFront(1); // 增加元素
  28. console.info(`result: ${deque[0]}`); // 訪問元素
  29. deque[0] = 'one'; // 修改元素
  30. console.info(`result: ${deque[0]}`);
  31. 

  32. // Stack
  33. import Stack from '@ohos.util.Stack'; // 導入Stack模塊 
  34. 

  35. let stack = new Stack();
  36. stack.push('a');
  37. stack.push(1); // 增加元素
  38. console.info(`result: ${stack[0]}`); // 訪問元素
  39. stack.pop(); // 刪除棧頂元素并返回該刪除元素
  40. console.info(`result: ${stack.length}`);
  41. 

  42. // List
  43. import List from '@ohos.util.List'; // 導入List模塊
  44. 

  45. let list = new List;
  46. list.add('a');
  47. list.add(1);
  48. let b2 = [1, 2, 3];
  49. list.add(b2); // 增加元素
  50. console.info(`result: ${list[0]}`); // 訪問元素
  51. console.info(`result: ${list.get(0)}`); // 訪問元素
以上內容是否對您有幫助：
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號
微信公眾號

編程獅公眾號