Container (computer science)
A container (also known as a collection ) in computer science is an abstract object that stores elements of the same type. Depending on the requirements, different data structures are used to implement a container. Examples of containers are arrays or lists ; a more detailed list can be found on the data structures page.
Storage and computing time requirements
| Array | Dynamic array |
Linked list |
Balanced tree |
Hash table | |
|---|---|---|---|---|---|
| Random access | O (1) | O (1) | O ( n ) | O ( log n ) | N / A |
| Insert / delete at the beginning | N / A | O (1) | O (1) | O ( log n ) | O ( 1 ) |
| Insert / delete at the end | N / A | O (1) | O (1) | ||
| Insert / delete in the middle | N / A | O ( n ) | search + O (1) |
||
| search | O ( n ) | O ( n ) | O ( n ) | O ( log n ) | O ( 1 ) |
| Medium storage space requirement | 0 | O ( n ) | O ( n ) | O ( n ) | O ( n ) |
The various data structures have different properties in terms of memory and computing time requirements when inserting new elements, deleting elements already present in the data structure or searching for a specific element. New items can be inserted into arrays and lists at a constant time - in Landau notation - but the search for data already stored in the container can, in the worst case , require viewing the entire database.
If, on the other hand, a balanced tree , such as AVL or red-black trees , is used as the container, all operations require time . Only a small part of the database needs to be viewed for a search, but adding new data requires a little more effort.
Notes and individual references
- ↑ If via key or index .
- ↑ Not possible because the order in the hash table depends on the hash function.
- ↑ a b amortized
- ↑ If a cyclic array is used.
- ↑ amortized expected runtime, for example with cuckoo hashing .
- ↑ Assuming that the linked list remembers a pointer of the data end position, otherwise the end of the list with the time O ( n ) must first be determined.
- ↑ Gerald Kruse. CS 240 Lecture Notes ( page no longer available , search in web archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. : Linked Lists Plus: Complexity Trade-offs ( page no longer available , search in web archives ) Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice. . Juniata College. Spring 2008.
- ↑ What is meant is the additional storage space required. It is usually a fraction of the storage space required anyway by O ( n ).
