共计 3490 个字符，预计需要花费 9 分钟才能阅读完成。
Array vs Linked List
Size
Since data can only be stored in contiguous blocks of memory in an array, its size cannot be altered at runtime due to the risk of overwriting other data. However, in a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses; this allows for a dynamic size that can change at runtime.
Memory allocation
For arrays at compile time and at runtime for linked lists. but, a dynamically allocated array also allocates memory at runtime.
Memory efficiency
For the same number of elements, linked lists use more memory as a reference to the next node is also stored along with the data. However, size flexibility in linked lists may make them use less memory overall; this is useful when there is uncertainty about size or there are large variations in the size of data elements; memory equivalent to the upper limit on the size has to be allocated (even if not all of it is being used) while using arrays, whereas linked lists can increase their sizes step-by-step proportionately to the amount of data.
Execution time
Any element in an array can be directly accessed with its index; however in the case of a linked list, all the previous elements must be traversed to reach any element. Also, better cache locality in arrays (due to contiguous memory allocation) can significantly improve performance. As a result, some operations (such as modifying a certain element) are faster in arrays, while some others (such as inserting/deleting an element in the data) are faster in linked lists.
Arrays are contiguous memory blocks, so large chunks of them will be loaded into the cache upon first access. This makes it comparatively quick to access future elements of the array.
Linked lists, on the other hand, aren’t necessarily in contiguous blocks of memory, and could lead to more cache misses, which increases the time it takes to access them.
Locality of Reference
- Refers to a phenomenon in which a computer program tends to access same set of memory locations for a particular time period.
- In other words, refers to the tendency of the computer program to access instructions whose addresses are near one another.
- The property of locality of reference is mainly shown by loops and subroutine calls in a program.
There are two ways with which data or instruction is fetched from main memory and get stored in cache memory:
Temporal Locality
- It means current data or instruction that is being fetched may be needed soon. So we should store that data or instruction in the cache memory so that we can avoid again searching in main memory for the same data.
- In other words, if some data is referenced, then there is a high probability that it will be referenced again in the near future.
Spatial Locality
- It means instruction or data near to the current memory location that is being fetched, may be needed soon in the near future.
Cache Performance
- The performance of the cache is measured in terms of hit ratio.
- When CPU refers to memory and find the data or instruction within the Cache Memory, it is known as cache hit.
- If the desired data or instruction is not found in the cache memory and CPU refers to the main memory to find that data or instruction, it is known as a cache miss.
ArrayList vs LinkedList
| ArrayList | LinkedList |
|---|---|
| Internally uses a dynamic array to store the elements. | Internally uses a doubly linked list to store the elements. |
| If any element is removed from the array, all the other elements are shifted in memory. | Faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory. |
| An ArrayList class can act as a list only because it implements List only. | LinkedList class can act as a list and queue both because it implements List and Deque interfaces. |
| Better for storing and accessing data. | Better for manipulating data. |
| The memory location for the elements of an ArrayList is contiguous. | The location for the elements of a linked list is not contiguous. |
| Generally, when an ArrayList is initialized, a default capacity of 10 is assigned to the ArrayList. | There is no case of default capacity in a LinkedList. In LinkedList, an empty list is created when a LinkedList is initialized. |
