[Interview]|[Interview] Java Basic - Data Structure
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.Locality of Reference
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.
- 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.
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.
- It means instruction or data near to the current memory location that is being fetched, may be needed soon in the near future.
- 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 | 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. |
推荐阅读
- 掌握JavaScript中的迭代器和生成器,顺便了解一下async、await的原理
- Java学习笔记(韩顺平教育|Java学习笔记(韩顺平教育 b站有课程)
- 学习|java-->方法案例(公司迟到措施)
- java|争分夺秒!这所211大学调剂系统只开通14小时!
- javascript实现输入框内容提示及隐藏功能
- 使用JavaScript实现轮播图效果
- JavaScript实现数组去重的7种方法
- JAVASE
- 笔记|JAVA中的练习
- 数据结构|Java实现常见的排序算法