More formally, a data structure is an organization of data elements, a collection of functions that can be applied on the data (such as add, delete, and search) and any relations between the different data elements. The following table shows common operations that some data structures provide:
Operation | Type | Description |
search(key) | Non-modifying | An operation that, given the key to a particular value, will return the value stored in the data structure if it can be found. |
side() | Non-modifying | The total number of values stored in the data structure. |
add(value) | Modifying | Inserts a value in the data structure. |
update(key, value) | Modifying | Updates an existing entry using the provided key and value. |
delete(value) | Modifying | Removes an item of data from the data structure. |
minimum() | Non-modifying | An operation supported only by ordered data structures, which will return the value with the minimal key. |
maximum() | Non-modifying | An operation supported only by ordered data structures, which will return the value with the minimal key. |
Table 2.3: Some common operations on data structures
In this section, we will see various types of dynamic data structures. We will start with linked lists, which are optimized for dynamic growth but are slow while searching. Then, we'll use these linked lists to implement other data structures on top, such as queues and stacks.