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 optimize 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. To search for a specific element within the List, traversal must start from the head node. Defined by generics, the storage locations of elements in the Link can be non-contiguous in memory.

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, the storage locations of elements in LinkedList can be non-contiguous in memory.

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.

This type is recommended for frequent insertions and deletions when using a doubly linked list.

You can use the get/set APIs to modify the stored elements. 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, increasing its size by 2 times the original capacity 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 than a Vector for inserting and deleting elements at the front, whereas a Vector excels in element access efficiency.

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

Common APIs for adding, deleting, 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 the tail and removal at the head.

Queue is suitable for first-in-first-out 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 removal only from the front and addition only at the rear, Stack supports insertion and removal at one end.

Stack is suitable for first-in-last-out 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 create a global array object. It is defined based on generics and requires that the storage space be contiguous. The initial capacity of Vector is 10, and it supports dynamic resizing, doubling its size each time.

Vector, like ArrayList, is based on arrays but provides more array manipulation APIs, supports operator access, and provides get and set APIs. In addition, Vector provides a more comprehensive verification and fault tolerance mechanism to meet requirements in different scenarios.

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:

import { ArrayList, Deque, Stack, List } from '@kit.ArkTS'; // Import the ArrayList, Deque, Stack, and List modules.

// ...
  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
  // ...
  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
  // ...
  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
  // ...
  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