2. Basic Data Structures
Data structures are very concrete and foundational to the study of abstract data types. They represent the actual layout of the data in computer memory. ADT are implemented using these data structures.
Functionality of Basic Data Structures:
- Get: grabs and element by an index.
- Search: finds a position of a target element.
- Add: adds a new element at a given position.
- Remove: removes an element at a given position.
Array
If you are accessing your data more often than adding data, you should probably use an array1. An array is a contiguous area of memory containing equal-size elements indexed by contiguous integers.
Get/Assignment
Finding an address of A[i] is as simple as computing $arrayAddr + elemSize \cdot i$ and we can jump to that address to get the element or assign a new element to that address.
Complexity: $O(1)$
Search
Finding an element generally requires linear search, however, we can use binary search if the data is sorted to find the index of the element.
Complexity (linear): $O(n)$
Complexity (binary): $O(log(n))$
Add
When adding elements, we may need to shift the array depending on the position. Furthermore, we may also need to increase the capacity of the array if the size would be greater than capacity and if we allow a dynamic array. Adding at the end of the array is simple, just assign a new element to the address.
Complexity (end of array, no resize): $O(1)$
Complexity (resize with any operation): $O(n)$
Complexity (shifting elements): $O(n)$
Remove
Essentially the same deal with add, minus the dynamic array part. We may have to shift elements, but if we are removing the end, we don't need to shift.
Complexity (removing the end): $O(1)$
Complexity (shifting): $O(n)$
Linked-List
If you are adding data more often than accessing data, you should probably use a linked list1. A linked-list uses nodes to link data in sequental order.
Get
To get an element, you must transverse the linked-list until you get that element at the position. This is obviously slower than an array which only requires a formula instead of a loop.
Complexity: $O(n)$
Search
Same deal with the get and array search, we must transverse the linked list to find the element we want. Unforunately we can not use a binary search if the linked-list is sorted because of the slow access times.
Complexity: $O(n)$
Add
Adding elements to linked lists is generally fast. When adding to the front or end (if the linked-list has head and tail references), we can add elements with simple operations. When adding to the middle of the list, we must transverse the list then its as simple as a couple of operations to add the element.
Complexity (middle): $O(n)$ then $O(1)$
Complexity (front & end): $O(1)$
Remove
Same deal as above, however, removing the tail element is requires us to transverse the list because we do not know the previous element.
Complexity (front): $O(1)$
Complexity (middle & end): $O(n)$ then $O(1)$