During my foray into data structures and algorithms, I've been learning about different structures and efficiency.
There are pros and cons to using various data structures, and I'll be going over some of them regarding arrays.
Arrays
Arrays can hold items of the same size in sequential order. Arrays require a block of uninterrupted space in memory.
An advantage to the array data structure is that it has a fast lookup time of O(1). This is because there is a direct connection between the index and its corresponding value. Instead of having to go through the entire array to find a value, which would be O(n) lookup time, we can use the index to lookup the value directly.
Arrays in low-level languages such as Java and C need to be declared with the array size. In JavaScript, arrays are dynamic arrays, which typically double in capacity when they reach capacity.
Pointer-based Arrays
Pointer-based arrays are just what they sound like, they use pointers to refer to the location of the array items in memory. Using a pointer-based array offers us some advantages over a regular array.
A pro to using pointer based arrays is that large blocks of uninterrupted space in memory are no longer need to store the entire array. This is because each pointer is referencing the location in memory of the element. In essence, this allows the items in the array to be stored in different locations, and they no longer have to be sequential. Another advantage is that since pointers are being used to reference each item in the array, the items no longer have to be the same exact size.
There are tradeoffs, of course. A notable one being that since all of the items in the pointer-based array are not sequential, the array is not cache friendly. When a request for a particular item in the array is made, the nearby addresses will be cached for future lookup. This is one of the main reasons that lookup time for arrays is O(1). However, with pointer based arrays, the lookup time is still O(1), but it's technically slower because caching no longer works. To keep it simple, we say the amortized time or average lookup time for pointer-based arrays is O(1).
As I learn more about data structures, the tradeoffs and costs become more apparent. It's important to draw comparisons between data structures and use those relationships to understand when and why to use the ideal one for a situation.
Latest comments (0)