1# Linear Containers 2 3 4Linear containers implement a data structure that enables sequential access. The bottom layer of linear containers is implemented through arrays. OpenHarmony provides the following linear containers: **ArrayList**, **Vector**, **List**, **LinkedList**, **Deque**, **Queue**, and **Stack**. 5 6 7Fully considering the data access speed, linear containers support Create, Read, Update, and Delete (CRUD) through a bytecode instruction at runtime. 8 9 10## ArrayList 11 12[ArrayList](../reference/apis/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. 13 14**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. 15 16**ArrayList** provides the following CRUD APIs. 17 18| Operation| Description| 19| --------- | ------- | 20| Adding elements| Use **add(element: T)** to add an element at the end of this container.| 21| Adding elements| Use **insert(element: T, index: number)** to insert an element at a given position (specified by **index**).| 22| Accessing elements| Use **arr\[index]** to obtain the value at a given position (specified by **index**).| 23| Accessing elements| Use **forEach(callbackFn: (value: T, index?: number, arrlist?: ArrayList<T>) => void, thisArg?: Object): void** to traverse the elements in this container.| 24| Accessing elements| Use **\[Symbol.iterator]():IterableIterator<T>** for data access.| 25| Modifying elements| Use **arr\[index] = xxx** to change the value at a given position (specified by **index**).| 26| Deleting elements| Use **remove(element: T)** to remove the first occurrence of the specified element.| 27| Deleting elements| Use **removeByRange(fromIndex: number, toIndex: number)** to remove all of the elements within a range.| 28 29 30## Vector 31 32[Vector](../reference/apis/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. 33 34Both **Vector** and [ArrayList](../reference/apis/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. 35 36The APIs provided by **Vector** are deprecated since API version 9. You are advised to use [ArrayList](../reference/apis/js-apis-arraylist.md). 37 38**Vector** provides the following CRUD APIs. 39 40| Operation| Description| 41| --------- | ------- | 42| Adding elements| Use **add(element: T)** to add an element at the end of this container.| 43| Adding elements| Use **insert(element: T, index: number)** to insert an element at a given position (specified by **index**).| 44| Accessing elements| Use **vec\[index]** to obtain the value at a given position (specified by **index**).| 45| Accessing elements| Use **get(index: number)** to obtain the element at a given position (specified by **index**).| 46| Accessing elements| Use **getLastElement()** to obtain the last element in this container.| 47| Accessing elements| Use **getIndexOf(element: T)** to obtain the index of the first occurrence of the specified element.| 48| Accessing elements| Use **getLastIndexOf(element: T)** to obtain the index of the last occurrence of the specified element.| 49| Accessing elements| Use **forEach(callbackFn: (value: T, index?: number, Vector?: Vector<T>) => void, thisArg?: Object)** to traverse the elements in this container.| 50| Accessing elements| Use **\[Symbol.iterator]():IterableIterator<T>** for data access.| 51| Modifying elements| Use **vec\[index]=xxx** to change the value at a given position (specified by **index**).| 52| Modifying elements| Use **set(index: number, element: T)** to replace an element at a given position (specified by **index**) with a given element.| 53| Modifying elements| Use **setLength(newSize: number)** to set the size of this container.| 54| Deleting elements| Use **removeByIndex(index: number)** to remove the value at a given position (specified by **index**).| 55| Deleting elements| Use **remove(element: T)** to remove the first occurrence of the specified element.| 56| Deleting elements| Use **removeByRange(fromIndex: number, toIndex: number)** to remove all of the elements within a range.| 57 58 59## List 60 61[List](../reference/apis/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. 62 63Unlike [LinkedList](../reference/apis/js-apis-linkedlist.md), which is a doubly linked list, **List** is a singly linked list that does not support insertion or removal at both ends. 64 65You are advised to use **List** for frequent insertion and removal operations. 66 67**List** provides the following CRUD APIs. 68 69| Operation| Description| 70| --------- | ------ | 71| Adding elements| Use **add(element: T)** to add an element at the end of this container.| 72| Adding elements| Use **insert(element: T, index: number)** to insert an element at a given position (specified by **index**).| 73| Accessing elements| Use **list\[index]** to obtain the value at a given position (specified by **index**).| 74| Accessing elements| Use **get(index: number)** to obtain the element at a given position (specified by **index**).| 75| Accessing elements| Use **getFirst()** to obtain the first element in this container.| 76| Accessing elements| Use **getLast()** to obtain the last element in this container.| 77| Accessing elements| Use **getIndexOf(element: T)** to obtain the index of the first occurrence of the specified element.| 78| Accessing elements| Use **getLastIndexOf(element: T)** to obtain the index of the last occurrence of the specified element.| 79| Accessing elements| Use **forEach(callbackfn: (value: T, index?: number, list?: List<T>)=> void, thisArg?: Object)** to traverse the elements in this container.| 80| Accessing elements| Use **\[Symbol.iterator]():IterableIterator<T>** for data access.| 81| Modifying elements| Use **list\[index] = xxx** to change the value at a given position (specified by **index**).| 82| Modifying elements| Use **set(index: number, element: T)** to replace an element at a given position (specified by **index**) with a given element.| 83| Modifying elements| Use **replaceAllElements(callbackFn:(value: T,index?: number,list?: List<T>)=>T,thisArg?: Object)** to replace all elements in this container with new elements.| 84| Deleting elements| Use **removeByIndex(index: number)** to remove the value at a given position (specified by **index**).| 85| Deleting elements| Use **remove(element: T)** to remove the first occurrence of the specified element.| 86 87 88## LinkedList 89 90[LinkedList](../reference/apis/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. 91 92Unlike [List](../reference/apis/js-apis-list.md), which is a singly linked list, **LinkedList** is a doubly linked list that supports insertion and removal at both ends. 93 94**LinkedList** is more efficient in data insertion than [ArrayList](../reference/apis/js-apis-arraylist.md), but less efficient in data access. 95 96You are advised to use **LinkedList** for frequent insertion and removal operations. 97 98**LinkedList** provides the following CRUD APIs. 99 100| Operation| Description| 101| ---------- | ------ | 102| Adding elements| Use **add(element: T)** to add an element at the end of this container.| 103| Adding elements| Use **insert(index: number, element: T)** to insert an element at a given position (specified by **index**).| 104| Accessing elements| Use **list\[index]** to obtain the value at a given position (specified by **index**).| 105| Accessing elements| Use **get(index: number)** to obtain the element at a given position (specified by **index**).| 106| Accessing elements| Use **getFirst()** to obtain the first element in this container.| 107| Accessing elements| Use **getLast()** to obtain the last element in this container.| 108| Accessing elements| Use **getIndexOf(element: T)** to obtain the index of the first occurrence of the specified element.| 109| Accessing elements| Use **getLastIndexOf(element: T)** to obtain the index of the last occurrence of the specified element.| 110| Accessing elements| Use **forEach(callbackFn: (value: T, index?: number, list?: LinkedList<T>) => void, thisArg?: Object)** to traverse the elements in this container.| 111| Accessing elements| Use **\[Symbol.iterator]():IterableIterator<T>** for data access.| 112| Modifying elements| Use **list\[index]=xxx** to change the value at a given position (specified by **index**).| 113| Modifying elements| Use **set(index: number, element: T)** to replace an element at a given position (specified by **index**) with a given element.| 114| Deleting elements| Use **removeByIndex(index: number)** to remove the value at a given position (specified by **index**).| 115| Deleting elements| Use **remove(element: T)** to remove the first occurrence of the specified element.| 116 117 118## Deque 119 120[Deque](../reference/apis/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 the ends. 121 122**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. 123 124[Queue](../reference/apis/js-apis-queue.md) follows the principle of FIFO only and allows element removal at the front and insertion at the rear. 125 126[Vector](../reference/apis/js-apis-vector.md) supports insertion and deletion of elements in between, as well as at both the ends. When compared with **Vector**, **Deque** is more efficient in inserting and removing header elements, but less efficient in accessing elements. 127 128You are advised to use **Deque** when you need to frequently insert or remove elements at both the ends of a container. 129 130**Deque** provides the following CRUD APIs. 131 132| Operation| Description| 133| ---------- | ------ | 134| Adding elements| Use **insertFront(element: T)** to insert an element at the front of this container.| 135| Adding elements| Use **insertEnd(element: T)** to insert an element at the end of this container.| 136| Accessing elements| Use **getFirst()** to obtain the value of the first element in this container, without removing it from the container.| 137| Accessing elements| Use **getLast()** to obtain the value of the last element in this container, without removing it from the container.| 138| Accessing elements| Use **popFirst()** to obtain the value of the first element in this container and remove it from the container.| 139| Accessing elements| Use **popLast()** to obtain the value of the last element in this container and remove it from the container.| 140| Accessing elements| Use **forEach(callbackFn:(value: T, index?: number, deque?: Deque<T>) => void, thisArg?: Object)** to traverse the elements in this container.| 141| Accessing elements| Use **\[Symbol.iterator]():IterableIterator<T>** for data access.| 142| Modifying elements| Use **forEach(callbackFn:(value: T, index?: number, deque?: Deque<T>)=> void, thisArg?: Object)** to modify an element in this container.| 143| Deleting elements| Use **popFirst()** to remove the first element from this container.| 144| Deleting elements| Use **popLast()** to remove the last element from this container.| 145 146 147## Queue 148 149[Queue](../reference/apis/js-apis-queue.md) can be used to construct a queue that follows the FIFO principle. 150 151**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. 152 153The bottom layer of **Queue** is implemented by cyclic queues, delivering a high efficiency in enqueuing and dequeuing. 154 155Unlike [Deque](../reference/apis/js-apis-deque.md), which supports insertion and removal at both the ends, **Queue** supports insertion at one end and removal at the other end. 156 157You are advised to use **Queue** in FIFO scenarios. 158 159**Queue** provides the following CRUD APIs. 160 161| Operation| Description| 162| ---------- | ------ | 163| Adding elements| Use **add(element: T)** to add an element at the end of this container.| 164| Accessing elements| Use **getFirst()** to obtain the value of the first element in this container, without removing it from the container.| 165| Accessing elements| Use **pop()** to obtain the value of the first element in this container and remove it from the container.| 166| Accessing elements| Use **forEach(callbackFn: (value: T, index?: number, queue?: Queue<T>) => void,thisArg?: Object)** to traverse the elements in this container.| 167| Accessing elements| Use **\[Symbol.iterator]():IterableIterator<T>** for data access.| 168| Modifying elements| Use **forEach(callbackFn:(value: T, index?: number, queue?: Queue<T>) => void,thisArg?: Object)** to modify an element in this container.| 169| Deleting elements| Use **pop()** to remove the first element from this container.| 170 171 172## Stack 173 174[Stack](../reference/apis/js-apis-stack.md) can be used to construct a stack that follows the Last Out First In (LOFI) principle. 175 176**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. 177 178Unlike [Queue](../reference/apis/js-apis-queue.md), which is implemented based on the queue data structure and supports insertion at one end and removal at the other end, **Stack** supports insertion and removal at the same end. 179 180You are advised to use **Stack** in LOFI scenarios. 181 182**Stack** provides the following CRUD APIs. 183 184| Operation| Description| 185| ---------- | ------ | 186| Adding elements| Use **push(item: T)** to add an element at the top of this container.| 187| Accessing elements| Use **peek()** to obtain the value of the top element in this container, without removing it from the container.| 188| Accessing elements| Use **pop()** to obtain the value of the top element in this container and remove it from the container.| 189| Accessing elements| Use **forEach(callbackFn: (value: T, index?: number, stack?: Stack<T>) => void, thisArg?: Object)** to traverse the elements in this container.| 190| Accessing elements| Use **\[Symbol.iterator]():IterableIterator<T>** for data access.| 191| Accessing elements| Use **locate(element: T)** to obtain the index of the first occurrence of the specified element.| 192| Modifying elements| Use **forEach(callbackFn:(value: T, index?: number, stack?: Stack<T>) => void, thisArg?: Object)** to modify an element in this container.| 193| Deleting elements| Use **pop()** to remove the top element from this container.| 194 195 196## Use of Linear Containers 197 198Refer to the code snippet below to add, access, and modify elements in **ArrayList**, **Vector**, **Deque**, **Stack**, and **List**. 199 200 201```js 202// ArrayList 203import ArrayList from '@ohos.util.ArrayList'; // Import the ArrayList module. 204 205let arrayList = new ArrayList(); 206arrayList.add('a'); 207arrayList.add(1); // Add an element. 208console.info(`result: ${arrayList[0]}`); // Access an element. 209arrayList[0] = 'one'; // Modify an element. 210console.info(`result: ${arrayList[0]}`); 211 212// Vector 213import Vector from '@ohos.util.Vector'; // Import the Vector module. 214 215let vector = new Vector(); 216vector.add('a'); 217let b1 = [1, 2, 3]; 218vector.add(b1); 219vector.add(false); // Add an element. 220console.info(`result: ${vector[0]}`); // Access an element. 221console.info(`result: ${vector.getFirstElement()}`); // Access an element. 222 223// Deque 224import Deque from '@ohos.util.Deque'; // Import the Deque module. 225 226let deque = new Deque; 227deque.insertFront('a'); 228deque.insertFront(1); // Add an element. 229console.info(`result: ${deque[0]}`); // Access an element. 230deque[0] = 'one'; // Modify an element. 231console.info(`result: ${deque[0]}`); 232 233// Stack 234import Stack from '@ohos.util.Stack'; // Import the Stack module. 235 236let stack = new Stack(); 237stack.push('a'); 238stack.push(1); // Add an element. 239console.info(`result: ${stack[0]}`); // Access an element. 240stack.pop(); // Remove an element. 241console.info(`result: ${stack.length}`); 242 243// List 244import List from '@ohos.util.List'; // Import the List module. 245 246let list = new List; 247list.add('a'); 248list.add(1); 249let b2 = [1, 2, 3]; 250list.add(b2); // Add an element. 251console.info(`result: ${list[0]}`); // Access an element. 252console.info(`result: ${list.get(0)}`); // Access an element. 253``` 254