Linear container

Linear Container Implementation

Linear containers are data structures that allow sequential access to elements. They are primarily implemented using arrays and include several types: ArrayList, Vector, List, LinkedList, Deque, Queue, and Stack.

Linear containers are designed for fast data access, enabling operations like adding, deleting, updating, and querying elements with a single bytecode instruction at runtime.

Comparison of Linear Container Types

Class Name	Characteristics and Recommended Use Cases
ArrayList	Dynamic array, occupies a contiguous memory space. Recommended when frequent element access is needed.
List	Singly linked list, non-contiguous memory. Recommended for frequent insertions/deletions using a singly linked list.
LinkedList	Doubly linked list, non-contiguous memory. Recommended for frequent insertions/deletions using a doubly linked list.
Deque	Double-ended queue, contiguous memory. Allows element operations at both ends. Recommended for frequent access and manipulation of head/tail elements.
Queue	Queue, contiguous memory. Follows FIFO. Elements are added at the tail and removed from the head.
Stack	Stack, contiguous memory. Follows LIFO. Elements are added and removed from one end.
Vector	Dynamic array, contiguous memory. No longer maintained; use ArrayList instead.

ArrayList

ArrayList is a dynamic array suitable for constructing global array objects. It is recommended when frequent element access is required.

Defined by generics, ArrayList requires a contiguous memory space. It has an initial capacity of 10 and dynamically expands by 1.5 times the original capacity when needed.

Common ArrayList operation APIs:

Operation	Method	Description
Add	add(element: T)	Adds an element to the end.
Add	insert(element: T, index: number)	Inserts an element at a specified position.
Access	arr[index: number]	Retrieves the value at the specified index.
Access	forEach(callbackFn: (value: T, index?: number, arrlist?: ArrayList) => void, thisArg?: Object)	Iterates over elements.
Access	Symbol.iterator: IterableIterator	Creates an iterator for data access.
Update	arr[index] = xxx	Updates the value at the specified index.
Delete	remove(element: T)	Removes the first matching element.
Delete	removeByRange(fromIndex: number, toIndex: number)	Removes elements within a specified range.

List

List constructs a singly linked list object, accessed from the head node to the tail. Defined by generics, List elements can be stored in non-contiguous memory locations.

Compared to LinkedList, List is a singly linked list and does not support bidirectional operations. Use List for efficient operations when frequent insertions/deletions are needed using a singly linked list.

Common List operation APIs:

Operation	Method	Description
Add	add(element: T)	Adds an element to the end.
Add	insert(element: T, index: number)	Inserts an element at a specified position.
Access	get(index: number)	Retrieves the element at the specified index.
Access	list[index: number]	Retrieves the element at the specified index (may return undefined).
Access	getFirst()	Retrieves the first element.
Access	getLast()	Retrieves the last element.
Access	getIndexOf(element: T)	Retrieves the first index of a matching element.
Access	getLastIndexOf(element: T)	Retrieves the last index of a matching element.
Access	forEach(callbackfn: (value: T, index?: number, list?: List) => void, thisArg?: Object)	Iterates over elements.
Access	Symbol.iterator: IterableIterator	Creates an iterator for data access.
Update	set(index: number, element: T)	Updates the element at the specified index.
Update	list[index] = element	Updates the element at the specified index (may return undefined).
Update	replaceAllElements(callbackFn: (value: T, index?: number, list?: List) => T, thisArg?: Object)	Replaces elements individually.
Delete	remove(element: T)	Removes the first matching element.
Delete	removeByIndex(index: number)	Removes the element at the specified index.

LinkedList

LinkedList constructs a doubly linked list object, allowing traversal forward or backward from a node. Defined by generics, LinkedList elements can be stored in non-contiguous memory locations.

Compared to List, LinkedList supports bidirectional operations and is more efficient for insertions/deletions. Use LinkedList for efficient operations when frequent insertions/deletions are needed using a doubly linked list.

Common LinkedList operation APIs:

Operation	Method	Description
Add	add(element: T)	Adds an element to the end.
Add	insert(element: T, index: number)	Inserts an element at a specified position.
Access	get(index: number)	Retrieves the element at the specified index.
Access	list[index: number]	Retrieves the element at the specified index (may return undefined).
Access	getFirst()	Retrieves the first element.
Access	getLast()	Retrieves the last element.
Access	getIndexOf(element: T)	Retrieves the first index of a matching element.
Access	getLastIndexOf(element: T)	Retrieves the last index of a matching element.
Access	forEach(callbackFn: (value: T, index?: number, list?: LinkedList) => void, thisArg?: Object)	Iterates over elements.
Access	Symbol.iterator: IterableIterator	Creates an iterator for data access.
Update	set(index: number, element: T)	Updates the element at the specified index.
Update	list[index] = element	Updates the element at the specified index (may return undefined).
Delete	remove(element: T)	Removes the first matching element.
Delete	removeByIndex(index: number)	Removes the element at the specified index.

Deque

Deque constructs a double-ended queue object, allowing element access from both ends. Deque follows FIFO and LIFO principles. Defined by generics, Deque requires contiguous memory, with an initial capacity of 8 and dynamic expansion by doubling the original capacity.

Deque uses a circular queue implementation, offering high efficiency for enqueue and dequeue operations. Unlike Queue, Deque allows element operations at both ends, while Queue only allows additions at the tail and deletions at the head. Compared to Vector, both support end operations, but Deque does not support middle insertions. Deque is more efficient than Vector for head element operations, while Vector offers better element access efficiency.

Use Deque when frequent element operations at both ends are required.

Common Deque operation APIs:

Operation	Method	Description
Add	insertFront(element: T)	Adds an element to the front.
Add	insertEnd(element: T)	Adds an element to the end.
Access	getFirst()	Retrieves the first element without removal.
Access	getLast()	Retrieves the last element without removal.
Access	popFirst()	Retrieves and removes the first element.
Access	popLast()	Retrieves and removes the last element.
Access	forEach(callbackFn: (value: T, index?: number, deque?: Deque) => void, thisArg?: Object)	Iterates over elements.
Access	Symbol.iterator: IterableIterator	Creates an iterator for data access.
Update	forEach(callbackFn: (value: T, index?: number, deque?: Deque) => void, thisArg?: Object)	Updates elements via iteration.
Delete	popFirst()	Removes the front element.
Delete	popLast()	Removes the last element.

Queue

Queue constructs a queue object following the FIFO principle. Defined by generics, Queue requires contiguous memory, with an initial capacity of 8 and dynamic expansion by doubling the original capacity.

Queue uses a circular queue implementation, offering high efficiency for enqueue and dequeue operations. Unlike Deque, Queue only allows additions at the tail and deletions at the head. Use Queue for typical FIFO scenarios.

Common Queue operation APIs:

Operation	Method	Description
Add	add(element: T)	Adds an element to the end.
Access	getFirst()	Retrieves the front element without removal.
Access	pop()	Retrieves and removes the front element.
Access	forEach(callbackFn: (value: T, index?: number, queue?: Queue) => void, thisArg?: Object)	Iterates over elements.
Access	Symbol.iterator: IterableIterator	Creates an iterator for data access.
Update	forEach(callbackFn: (value: T, index?: number, queue?: Queue) => void, thisArg?: Object)	Updates elements via iteration.
Delete	pop()	Removes the front element.