Linear Containers

Linear containers, underpinned by arrays, implement a data structure that enables sequential access. There are several types of linear containers: ArrayList, Vector, List, LinkedList, Deque, Queue, and Stack.

Linear containers prioritize data access speed, enabling operations such as adding, removing, modifying, and accessing elements with a single bytecode instruction at runtime.

Comparison of Linear Container Types

ArrayList

ArrayList is a dynamic array used to construct a global array object. It is recommended for frequent element access.

Defined by generics, ArrayList requires a contiguous block of memory for storage, with an initial capacity of 10 and supports dynamic resizing, increasing its size by 1.5 times the original capacity each time.

Common APIs for adding, removing, modifying, and accessing elements in ArrayList are as follows:

List

List is used to construct a singly linked list, which supports access only through the head node to the tail node. Defined by generics, List’s storage locations in memory can be non-contiguous.

Unlike LinkedList, which is a doubly linked list and allows quick insertions and deletions at both ends, List is a singly linked list and does not support bidirectional operations.

If elements need to be frequently inserted and deleted and a singly linked list is required, you are advised to use List.

Common APIs for adding, removing, modifying, and accessing elements in List are as follows:

LinkedList

LinkedList is used to construct a doubly linked list, which can be traversed in both directions from any node. Defined by generics, LinkedList’s storage locations in memory can be non-contiguous.

Unlike List, which is a singly linked list and does not support bidirectional operations, LinkedList is a doubly linked list and allows quick insertions and deletions at both ends.

Compared with ArrayList, LinkedList is more efficient for inserting data, whereas ArrayList is more efficient for querying data.

If elements need to be frequently inserted and deleted and a doubly linked list is required, you are advised to use LinkedList.

Common APIs for adding, removing, modifying, and accessing elements in LinkedList are as follows:

Deque

Deque is used to construct a double-ended queue (deque) that follows the principles of FIFO and LIFO. It allows insertion and removal of elements at both ends.

Defined by generics, Deque requires a contiguous block of memory for storage, with an initial capacity of 8 and supports dynamic resizing, doubling its size each time. Deque is implemented using a circular queue, ensuring efficient enqueue and dequeue operations.

Unlike Queue, which only allows element removal at the head and insertion at the tail, Deque allows operations at both ends.

Compared with Vector, both support element operations at both ends, but Deque does not allow insertions in the middle. Deque is more efficient for inserting and deleting elements at the head, whereas Vector is more efficient for accessing elements.

Deque is recommended for frequent insertions and deletions at both ends of the container.

Common APIs for adding, removing, modifying, and accessing elements in Deque are as follows:

Queue

Queue is used to construct a queue that follows the FIFO principle.

Defined by generics, Queue requires a contiguous block of memory for storage, with an initial capacity of 8 and supports dynamic resizing, doubling its size each time.

Queue is implemented using a circular queue, ensuring efficient enqueue and dequeue operations.

Unlike Deque, which supports insertion and removal at both the ends, Queue supports insertion at one end and removal at the other.

Queue is suitable for FIFO scenarios.

Common APIs for adding, removing, modifying, and accessing elements in Queue are as follows:

Stack

Stack is used to construct a stack that follows the Last Out First In (LOFI) principle.

Defined by generics, Stack requires a contiguous block of memory for storage, with an initial capacity of 8 and supports dynamic resizing, increasing its size by 1.5 times the original capacity each time. Stack is implemented using an array, with all operations performed at one end.

Unlike Queue, which is implemented using a circular queue and allows insertion at one end and removal at the other, Stack supports insertion and removal at one end.

Stack is suitable for LOFI scenarios.

Common APIs for adding, removing, modifying, and accessing elements in Stack are as follows:

Vector

NOTE

Since API version 9, this API is no longer maintained. Use ArrayList instead.

Vector is a continuous storage structure used to construct a global array object. Defined by generics, Vector requires a contiguous block of memory for storage, with an initial capacity of 10 and supports dynamic resizing, doubling its size each time.

Vector, like ArrayList, is based on arrays but provides more array manipulation interfaces. In addition to operator access, Vector provides the getter and setter to provide more comprehensive verification and error tolerance mechanisms.

Common APIs for adding, removing, modifying, and accessing elements in Vector are as follows:

Use of Linear Containers

This section provides usage examples for common linear containers, including ArrayList, Deque, Stack, and List, covering importing modules, adding elements, accessing elements, and modifying elements. The example code is as follows:

// ArrayList
import { ArrayList } from '@kit.ArkTS'; // Import the ArrayList module.

let arrayList1: ArrayList<string> = new ArrayList();
arrayList1.add('a'); // Add an element with the value 'a'.
let arrayList2: ArrayList<number> = new ArrayList();
arrayList2.add(1); // Add an element with the value 1.
console.info(`result: ${arrayList2[0]}`); // Access the element at index 0. Output: result: 1
arrayList1[0] = 'one'; // Modify the element at index 0.
console.info(`result: ${arrayList1[0]}`); // Output: result: one

// Deque
import { Deque } from '@kit.ArkTS'; // Import the Deque module.

let deque1: Deque<string> = new Deque();
deque1.insertFront('a'); // Add an element with the value 'a' to the header.
let deque2: Deque<number> = new Deque();
deque2.insertFront(1); // Add an element with the value 1 to the header.
console.info(`result: ${deque2.getFirst()}`); // Access the first element. Output: result: 1
deque1.insertEnd('one'); // Add an element with the value 'one'.
console.info(`result: ${deque1.getLast()}`); // Access the last element. Output: result: one

// Stack
import { Stack } from '@kit.ArkTS'; // Import the Stack module.

let stack1: Stack<string> = new Stack();
stack1.push('a'); // Add an element with the value 'a' to the Stack.
let stack2: Stack<number> = new Stack();
stack2.push(1); // Add an element with the value 1 to the Stack.
console.info(`result: ${stack1.peek()}`); // Access the top element of the Stack. Output: result: a
console.info(`result: ${stack2.pop()}`); // Remove and return the top element. Output: result: 1
console.info(`result: ${stack2.length}`); // Output: result: 0

// List
import { List } from '@kit.ArkTS'; // Import the List module.

let list1: List<string> = new List();
list1.add('a'); // Add an element with the value 'a'.
let list2: List<number> = new List();
list2.insert(0, 0); // Insert an element with the value 0 at index 0.
let list3: List<Array<number>> = new List();
let b2 = [1, 2, 3];
list3.add(b2); // Add an element of the Array type.
console.info(`result: ${list1[0]}`); // Access the element at index 0. Output: result: a
console.info(`result: ${list3.get(0)}`); // Access the element at index 0. Output: result: 1,2,3

你可能感兴趣的鸿蒙文章

harmony 鸿蒙ArkTS

harmony 鸿蒙Configuring arkOptions in build-profile.json5

harmony 鸿蒙Asynchronous Lock

harmony 鸿蒙Ark Bytecode File Format

harmony 鸿蒙Naming Conventions for Ark Bytecode Functions

harmony 鸿蒙Ark Bytecode Fundamentals

harmony 鸿蒙Overview of Ark Bytecode

harmony 鸿蒙Shared Container

harmony 鸿蒙Asynchronous Waiting

harmony 鸿蒙ArkTS Cross-Language Interaction