1# Linear Containers
2
3
4Linear 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**.
5
6
7To accelerate data access, linear containers support Create, Read, Update, and Delete (CRUD) through a bytecode instruction at runtime.
8
9## Comparison of linear container types
10
11| Class| Characteristics and Recommended Application Scenarios|
12| --------- | ------- |
13| ArrayList | Dynamic array, which occupies a continuous memory space. This method is recommended when elements need to be frequently read.|
14| List | Unidirectional linked list. The occupied space can be discontinuous. This mode is recommended when elements need to be frequently inserted and deleted and a unidirectional linked list is required.|
15| LinkedList | A doubly linked list. The occupied space can be discontinuous. It is recommended when elements need to be frequently inserted and deleted and a doubly linked list is required.|
16| Deque | Dual-ended queue. Elements can be entered and exited from the head and tail of a container, occupying a continuous memory space. It is recommended when the head and tail elements need to be frequently accessed and operated.|
17| Queue | A queue is used to insert elements from the tail of a container and pop elements from the header of the container, occupying a continuous memory space. You are advised to use **Queue** in FIFO scenarios.|
18| Stack | A stack can be inserted or deleted only from one end of a container, occupying a continuous memory space. You are advised to use **Stack** in LOFI scenarios.|
19| Vector | Dynamic array, which occupies a continuous memory space. This type is no longer maintained. You are advised to use ArrayList.|
20
21## ArrayList
22
23[ArrayList](../reference/apis-arkts/js-apis-arraylist.md) 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.
24
25**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.
26
27**ArrayList** provides the following CRUD APIs.
28
29| Operation| API| Description|
30| --------- | ------- | ------- |
31| Create| add(element: T) | // Add an item to the end of the data.|
32| Create| insert(element: T, index: number) |  * Inserts a value to a specified index.|
33| Read| arr\[index: number] | Obtains the value corresponding to a specified index. The value is obtained by running commands to ensure the access speed.|
34| Read| forEach(callbackFn: (value: T, index?: number, arrlist?: ArrayList<T>) => void, thisArg?: Object) | Accesses the elements of the entire ArrayList container.|
35| Read| \[Symbol.iterator]():IterableIterator<T> | Creates an iterator for data access.|
36| Update| arr\[index] = xxx | Modifies the value corresponding to a specified index.|
37| Delete| remove(element: T) | Deletes the first matched element.|
38| Delete| removeByRange(fromIndex: number, toIndex:number) | Removes elements in a specified range from this container.|
39
40## List
41
42[List](../reference/apis-arkts/js-apis-list.md) 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.
43
44Unlike [LinkedList](../reference/apis-arkts/js-apis-linkedlist.md), which is a doubly linked list, **List** does not support insertion or removal at both ends.
45
46If elements need to be frequently inserted and deleted and a unidirectional linked list is required, you are advised to use List to perform efficient operations.
47
48**List** provides the following CRUD APIs.
49
50| Operation| API| Description|
51| --------- | ------- | ------- |
52| Create| add(element: T) | // Add an item to the end of the data.|
53| Create| insert(element: T, index: number) |  * Inserts a value to a specified index.|
54| Read| get(index: number) | Obtains the element corresponding to the specified index.|
55| Read| list\[index: number] | Obtains the element corresponding to the specified index position. However, this will result in undefined results.|
56| Read| getFirst() | Obtains the first element.|
57| Read| getLast() | Obtaining the last element|
58| Read| getIndexOf(element: T) | Obtains the position of the first element that matches the specified element.|
59| Read| getLastIndexOf(element: T) | Obtains the position of the last element that matches the specified element.|
60| Read| forEach(callbackfn: (value:T, index?: number, list?: List<T>)=> void,thisArg?: Object) | Traverses the elements of the entire list container.|
61| Read| \[Symbol.iterator]():IterableIterator<T> | Creates an iterator for data access.|
62| Update| set(index:number, element: T) | Changes the value of an element with a specified index to element.|
63| Update| list\[index] = element | Changes the value of an element at the specified index position to element. However, the result is not defined.|
64| Update| replaceAllElements(callbackFn:(value: T,index?: number,list?: List<T>)=>T,thisArg?: Object) | Replaces elements in a list one by one.|
65| Delete| remove(element: T) | Deletes the first matched element.|
66| Delete| removeByIndex(index:number) | Deletes the element corresponding to the index position.|
67
68## LinkedList
69
70[LinkedList](../reference/apis-arkts/js-apis-linkedlist.md) 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.
71
72Unlike [List](../reference/apis-arkts/js-apis-list.md), which is a singly linked list, **LinkedList** supports insertion and removal at both ends.
73
74**LinkedList** is more efficient in data insertion than [ArrayList](../reference/apis-arkts/js-apis-arraylist.md), but less efficient in data access.
75
76If elements need to be frequently inserted and deleted and a doubly linked list is required, you are advised to use LinkedList to perform efficient operations.
77
78**LinkedList** provides the following CRUD APIs.
79
80| Operation| API| Description|
81| --------- | ------- | ------- |
82| Create| add(element: T) | // Add an item to the end of the data.|
83| Create| insert(element: T, index: number) |  * Inserts a value to a specified index.|
84| Read| get(index: number) | Obtains the element corresponding to the specified index.|
85| Read| list\[index: number] | Obtains the element corresponding to the specified index position. However, this will result in undefined results.|
86| Read| getFirst() | Obtains the first element.|
87| Read| getLast() | Obtaining the last element|
88| Read| getIndexOf(element: T) | Obtains the position of the first element that matches the specified element.|
89| Read| getLastIndexOf(element: T) | Obtains the position of the last element that matches the specified element.|
90| Read| forEach(callbackFn: (value: T, index?: number, list?: LinkedList<T>) => void, thisArg?: Object) | Traverses the elements of the entire LinkedList container.|
91| Read| \[Symbol.iterator]():IterableIterator<T> | Creates an iterator for data access.|
92| Update| set(index:number, element: T) | Changes the value of an element with a specified index to element.|
93| Update| list\[index] = element | Changes the value of an element at the specified index position to element. However, the result is not defined.|
94| Delete| remove(element: T) | Deletes the first matched element.|
95| Delete| removeByIndex(index:number) | Deletes the element corresponding to the index position.|
96
97## Deque
98
99[Deque](../reference/apis-arkts/js-apis-deque.md) 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.
100
101**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.
102
103Compared with [Queue](../reference/apis-arkts/js-apis-queue.md), Deque allows you to add or delete elements at both ends. Queue allows you to delete elements only at the beginning and add elements at the end.
104
105Unlike [Vector](../reference/apis-arkts/js-apis-vector.md), **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.
106
107You are advised to use **Deque** when you need to frequently insert or remove elements at both the ends of a container.
108
109**Deque** provides the following CRUD APIs.
110
111| Operation| API| Description|
112| --------- | ------- | ------- |
113| Create| insertFront(element: T) | Adds an element to the header.|
114| Create| insertEnd(element: T) | Adds an element to the end.|
115| Read| getFirst() | Obtains the first element and does not dequeue the element.|
116| Read| getLast() | Obtains the last element and does not dequeue the element.|
117| Read| popFirst() | Obtains the first element and dequeues it.|
118| Read| popLast() | Obtains the last element and dequeues it.|
119| Read| forEach(callbackFn:(value: T, index?: number, deque?: Deque<T>) => void, thisArg?: Object) | Traverses the elements of the entire Deque container.|
120| Read| \[Symbol.iterator]():IterableIterator<T> | Creates an iterator for data access.|
121| Update| forEach(callbackFn:(value: T, index?: number, deque?: Deque<T>)=> void, thisArg?: Object) | Modify the elements of the entire Deque container through traversal.|
122| Delete| popFirst() | Dequeues and deletes the head element.|
123| Delete| popLast() | Dequeues and deletes the tail element.|
124
125## Queue
126
127[Queue](../reference/apis-arkts/js-apis-queue.md) can be used to construct a queue that follows the FIFO principle.
128
129**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.
130
131The bottom layer of **Queue** is implemented by cyclic queues, delivering a high efficiency in enqueuing and dequeuing.
132
133Unlike [Deque](../reference/apis-arkts/js-apis-deque.md), which supports insertion and removal at both the ends, **Queue** supports insertion at one end and removal at the other.
134
135You are advised to use **Queue** in FIFO scenarios.
136
137**Queue** provides the following CRUD APIs.
138
139| Operation| API| Description|
140| --------- | ------- | ------- |
141| Create| add(element: T) | Adds an element to the end.|
142| Read| getFirst() | Obtains the head element of a queue and does not dequeue the element.|
143| Read| pop() | Obtains the head element and dequeues it.|
144| Read| forEach(callbackFn: (value: T, index?: number, queue?: Queue<T>) => void,thisArg?: Object) | Traverses and accesses the elements of the entire queue container.|
145| Read| \[Symbol.iterator]():IterableIterator<T> | Creates an iterator for data access.|
146| Update| forEach(callbackFn: (value: T, index?: number, queue?: Queue<T>) => void,thisArg?: Object) | Modify the elements of the entire queue container through traversal.|
147| Delete| pop() | Dequeues and deletes the head element.|
148
149## Stack
150
151[Stack](../reference/apis-arkts/js-apis-stack.md) can be used to construct a stack that follows the Last Out First In (LOFI) principle.
152
153**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.
154
155Unlike [Queue](../reference/apis-arkts/js-apis-queue.md), which supports insertion at one end and removal at the other, **Stack** supports insertion and removal at the same end.
156
157You are advised to use **Stack** in LOFI scenarios.
158
159**Stack** provides the following CRUD APIs.
160
161| Operation| API| Description|
162| --------- | ------- | ------- |
163| Create| push(item: T) | Adds an element to the top of the stack.|
164| Read| peek() | Obtains the top element of the stack and does not dequeue the element.|
165| Read| pop() | Obtains the top element of the stack and dequeues it.|
166| Read| locate(element: T) | Obtains the position of an element.|
167| Read| forEach(callbackFn: (value: T, index?: number, stack?: Stack<T>) => void, thisArg?: Object) | Traverses and accesses the elements of the entire stack container.|
168| Read| \[Symbol.iterator]():IterableIterator<T> | Creates an iterator for data access.|
169| Update| forEach(callbackFn: (value: T, index?: number, stack?: Stack<T>) => void, thisArg?: Object) | Modify the elements of the entire stack container through traversal.|
170| Delete| pop() | Dequeues and deletes the top element from the stack.|
171
172## Vector
173
174> **NOTE**
175>
176> The APIs provided by **Vector** are deprecated since API version 9. You are advised to use [ArrayList](../reference/apis-arkts/js-apis-arraylist.md).
177
178[Vector](../reference/apis-arkts/js-apis-vector.md) 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.
179
180Both **Vector** and [ArrayList](../reference/apis-arkts/js-apis-arraylist.md) 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.
181
182**Vector** provides the following CRUD APIs.
183
184| Operation| API| Description|
185| --------- | ------- | ------- |
186| Create| add(element: T) | // Add an item to the end of the data.|
187| Create| insert(element: T, index: number) |  * Inserts a value to a specified index.|
188| Read| get(index: number) | Obtains the element corresponding to the specified index.|
189| Read| vec\[index: number] | Obtains the element corresponding to the specified index position. The access speed is ensured by obtaining the element by using instructions.|
190| Read| getFirst() | Obtains the first element.|
191| Read| getLastElement() | Obtaining the last element|
192| Read| getIndexOf(element: T) | Obtains the position of the first element that matches the specified element.|
193| Read| getLastIndexOf(element: T) | Obtains the position of the last element that matches the specified element.|
194| Read| forEach(callbackFn: (value: T, index?: number, Vector?: Vector<T>) => void, thisArg?: Object) | Traverses the elements of the entire Vector container.|
195| Read| \[Symbol.iterator]():IterableIterator<T> | Creates an iterator for data access.|
196| Update| set(index:number, element: T) | Changes the value of an element with a specified index to element.|
197| Update| vec\[index] = element | Changes the value of an element with a specified index to element.|
198| Update| replaceAllElements(callbackFn:(value: T,index?: number,list?: List<T>)=>T,thisArg?: Object) | Replaces elements in a vector one by one.|
199| Update| setLength(newSize:number) | Sets the vector length.|
200| Delete| remove(element: T) | Deletes the first matched element.|
201| Delete| removeByIndex(index:number) | Deletes the element corresponding to the index position.|
202| Delete| removeByRange(fromIndex:number,toIndex:number) | Removes elements in a specified range from this container.|
203
204## Use of Linear Containers
205
206Refer to the code snippet below to add, access, and modify elements in **ArrayList**, **Deque**, **Stack**, and **List**.
207
208
209```ts
210// ArrayList
211import { ArrayList } from '@kit.ArkTS'; // Import the ArrayList module.
212
213let arrayList1: ArrayList<string> = new ArrayList();
214arrayList1.add ('a'); // Add an element whose value is'a'.
215let arrayList2: ArrayList<number> = new ArrayList();
216arrayList2.add (1); // Add an element whose value is 1.
217console.info ('result: ${arrayList2[0]}'); // Access the element whose index is 0. Output: result: 1
218arrayList1[0] = 'one'; // Modify the element whose index is 0.
219console.info ('result: ${arrayList1[0]}'); // Output: result: one
220
221// Deque
222import { Deque } from '@kit.ArkTS'; // Import the Deque module.
223
224let deque1: Deque<string> = new Deque();
225deque1.insertFront ('a'); // Add an element whose value is'a' to the header.
226let deque2: Deque<number> = new Deque();
227deque2.insertFront (1); // Add an element whose value is 1 to the header.
228console.info ('result: ${deque2.getFirst () }'); // Access the element in the queue header. Output: result: 1
229deque1.insertEnd ('one'); // Add an element whose value is'one' to the end.
230console.info ('result: ${deque1.getLast () }'); // Access the element at the end of the queue. Output: result: one
231
232// Stack
233import { Stack } from '@kit.ArkTS'; // Import the Stack module.
234
235let stack1: Stack<string> = new Stack();
236stack1.push ('a'); // Add an element whose value is'a' to the stack.
237let stack2: Stack<number> = new Stack();
238stack2.push (1); // Add an element whose value is 1 to the stack.
239console.info ('result: ${stack1.peek () }'); // Access the top element of the stack. Output: result: a
240console.info ('result: ${stack2.pop () }'); // Delete the top element of the stack and return the deleted element. Output: result: 1
241console.info ('result: ${stack2.length}'); // Output: result: 0
242
243// List
244import { List } from '@kit.ArkTS'; // Import the List module.
245
246let list1: List<string> = new List();
247list1.add ('a'); // Add an element whose value is'a'.
248let list2: List<number> = new List();
249list2.insert (0, 0); // Insert (add) an element whose value is 0 at position 0.
250let list3: List<Array<number>> = new List();
251let b2 = [1, 2, 3];
252list3.add (b2); // Add an element of the Array type.
253console.info ('result: ${list1[0]}'); // Access the element whose index is 0. Output: result: a
254console.info ('result: ${list3.get (0) }'); // Access the element whose index is 0. Output: result: 1,2,3
255```
256