Abstract
- A Linear collection of elements of the same Datatype that are stored in Continuous Memory. The next node is obtained by adding a constant value to the Memory Address of current node
- Can be used to implement Hash Map when keys are fixed
- Leetcode questions
Cache Hit
Elements of array are stored in Main Memory in a compact manner, thus making great use of Cache Locality
Fixed Size
If we want to expand, we have to create another bigger array & copy all the elements to the new array which is very time consuming
Element Removal
We can’t delete elements in arrays, we can only overwrite
Time Complexity
Search
to search for a value.
Indexing
It is to index any elements in an array. The indexing formula is
elementAddr = firtstElementAddr + elementLength * elementIndex,elementIndexis when we try to access the first element.
Insert, Delete
at the 2 ends of the array
in the middle of the array
- For insert, we have to move all the elements next to the new element one step to right
- For delete, we have move all element next to the deleted element one step to left
Performance comparison with Linked List when going through all elements
Array is much faster if there is CPU Cache, otherwise it may be slightly slower. Because Array has to calculate the address of the next element, while Linked List is already calculated.
The reason why array is faster with CPU Cache is because array is stored in a Continuous Memory manner. Thus array is able to take advantage of Cache Locality
Contiguous Segment
- A continuous range of Array
Dynamic Array
- Also known as List
- A Datatype that contains a Pointer to the underlying Array and other metadata like the capacity of the array and the current size of the array. As shown above, the purple blocks contain the metadata of the dynamic array. The yellow blocks are the actually array that hold the elements
Dynamic array mechanism visualisation
Convenient
Developers don’t need to re-write battle-tested logic of re-sizeing Array etc, battery-packed with best practices.
Secure
With the built-in expansion mechanism and
lengthmetadata, we are sure new elements aren’t added into Memory Address that belong to other parts of the Process (进程). Thus, ensuring Memory Safety.
More Resource Intense
We can’t fine tune every Array operations because the implementation details are abstracted away. We only have a limited interface to interact with it. And Dynamic array comes with metadata to support the different functionalities it offers.
Minimise re-sizing
If you know how big an array you want, it is usually recommended to set it as the capacity of your dynamic array. This reduce the need of frequent re-sizing operations which mean fewer allocation on Heap Segment. Thus, better performance.
Circular Array
- Connect the start and end of the Array to form a loop
- With taking remainder from
frontIndex % arrayCapacity, we are able to implement circular array on an array. Take a look at Visual for better understanding - Used to implement Queue
Front Index
A variable to keep track the index for the start of the circular array.
Rear Index
A variable to keep track the index of the slot after the last element of the circular array, Can be obtained with
frontIndex + arraySize.
JavaScript Array
Inserting a big index without the memory sacrifice
When inserting at a big index. We don’t need allocate an array in the Virtual Memory that large. It is just another key-value pair in the hash map!
