Interface vs Data Structure
Interfaces also go by Application Programming Interface(APIs) or Abstract Data Types(ADTs).
| Interface | Data structure |
|---|---|
| Is a specification of what you might want to do | Is a representation of how to do something (implementation) |
| Defines what data you can store | Defines how to store the data |
| Defines the supported operations and what they mean | Defines the algorithms to support the operations |
| Is a problem statement | The solution/ algorithm |
Sequence
A sequence a collection of items stored in an order.
There are different data structures that can be used to define and implement a sequence.
Static sequence
aka static array
This is an array with a fixed size/ memory allocated. When the array is created, it can be empty — but the space already allocated in memory. When a value is inserted into the array, it will occupy the available space.
Dynamic sequence/ arrays
Dynamic arrays don’t have a pre-defined size. When a new element is being added to a dynamic array:
- A new array is created in memory
- Data from the previous array is copied over to the new array
- The new element is added to the new array
- The “old” array is freed from memory
The two common implementations of a dynamic sequence are linked lists and dynamic arrays:
- Linked-lists
- Dynamic arrays
Linked-list
Data is stored in a node: containing the element and a pointer to the next element in the list/ array.
Courtesy of https://bodo-schoenfeld.de/ ↗
Dynamic array
In a dynamic array, memory is over-allocated when the array is create, i.e, reserves more memory than it needs. This means that the array will be resized every time memory is allocated is depleted by “booking” more memory.
Other learnings
- Amortized analysis ↗: a method of analyzing a given algorithm’s complexity or the total resources required to execute it. It’s used to get the average cost of a given operation