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.

To accelerate data access, linear containers support Create, Read, Update, and Delete (CRUD) through a bytecode instruction at runtime.

ArrayList

ArrayList is a dynamic array that can be used to construct a global array object. You are advised to use ArrayList when elements in a container need to be frequently read.

ArrayList uses generics and must be stored in a contiguous memory space. Its initial capacity is 10, and it increases capacity 1.5-fold in each dynamic expansion.

ArrayList provides the following CRUD APIs.

Vector

Vector is a continuous storage structure that can be used to construct a global array object. Vector uses generics and must be stored in a contiguous memory space. Its initial capacity is 10, and it has capacity doubled in each dynamic expansion.

Both Vector and ArrayList are implemented based on arrays, but Vector provides more interfaces for operating the arrays. In addition to operator access, Vector provides the getter and setter to provide a more complete verification and error tolerance mechanism.

The APIs provided by Vector are deprecated since API version 9. You are advised to use ArrayList.

Vector provides the following CRUD APIs.

List

List can be used to construct a singly linked list, which supports access only through the head node to the tail node. List uses generics and can be stored in a non-contiguous memory space.

Unlike LinkedList, which is a doubly linked list, List does not support insertion or removal at both ends.

You are advised to use List for frequent insertion and removal operations.

List provides the following CRUD APIs.

LinkedList

LinkedList can be used to construct a doubly linked list, which can be traversed at both ends. LinkedList uses generics and can be stored in a non-contiguous memory space.

Unlike List, which is a singly linked list, LinkedList supports insertion and removal at both ends.

LinkedList is more efficient in data insertion than ArrayList, but less efficient in data access.

You are advised to use LinkedList for frequent insertion and removal operations.

LinkedList provides the following CRUD APIs.

Deque

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

Deque uses generics and must be stored in a contiguous memory space. Its initial capacity is 8, and it has capacity doubled in each dynamic expansion. The bottom layer of Deque is implemented by cyclic queues, delivering a high efficiency in enqueuing and dequeuing.

Different from Deque, Queue follows the principle of FIFO only and allows element removal at the front and insertion at the rear.

Unlike Vector, Deque does not support insertion and deletion of elements in between. When compared with Vector, Deque is more efficient in inserting and removing header elements, but less efficient in accessing elements.

You are advised to use Deque when you need to frequently insert or remove elements at both the ends of a container.

Deque provides the following CRUD APIs.

Queue

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

Queue uses generics and must be stored in a contiguous memory space. Its initial capacity is 8, and it has capacity doubled in each dynamic expansion.

The bottom layer of Queue is implemented by cyclic queues, delivering a high efficiency in enqueuing and dequeuing.

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

You are advised to use Queue in FIFO scenarios.

Queue provides the following CRUD APIs.

Stack

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

Stack uses generics and must be stored in a contiguous memory space. Its initial capacity is 8, and it increases capacity 1.5-fold in each dynamic expansion. The bottom layer of Stack is implemented based on arrays. It supports data insertion and removal at one end.

Unlike Queue, which supports insertion at one end and removal at the other, Stack supports insertion and removal at the same end.

You are advised to use Stack in LOFI scenarios.

Stack provides the following CRUD APIs.

Use of Linear Containers

Refer to the code snippet below to add, access, and modify elements in ArrayList, Vector, Deque, Stack, and List.

// ArrayList
import ArrayList from '@ohos.util.ArrayList'; // Import the ArrayList module.

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

// Vector
import Vector from '@ohos.util.Vector'; // Import the Vector module.

let vector1: Vector<string> = new Vector();
vector1.add('a');
let vector2: Vector<Array<number>> = new Vector();
let b1 = [1, 2, 3];
vector2.add(b1);
let vector3: Vector<boolean> = new Vector();
vector3.add(false); // Add an element.
console.info(`result: ${vector1[0]}`); // Access an element.
console.info(`result: ${vector2.getFirstElement()}`); // Access an element.

// Deque
import Deque from '@ohos.util.Deque'; // Import the Deque module.

let deque1: Deque<string> = new Deque();
deque1.insertFront('a');
let deque2: Deque<number> = new Deque();
deque2.insertFront(1); // Add an element.
console.info(`result: ${deque1[0]}`); // Access an element.
deque1[0] = 'one'; // Modify an element.
console.info(`result: ${deque2[0]}`);

// Stack
import Stack from '@ohos.util.Stack'; // Import the Stack module.

let stack1: Stack<string> = new Stack();
stack1.push('a');
let stack2: Stack<number> = new Stack();
stack2.push(1); // Add an element.
console.info(`result: ${stack1[0]}`); // Access an element.
stack2.pop(); // Remove the top element from this container.
console.info(`result: ${stack2.length}`);

// List
import List from '@ohos.util.List'; // Import the List module.

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