Data Structures
There is a famous saying that
“Algorithms + Data Structures = Programs” (Wirth)
“For many applications, the choice of the proper data structure is the only major decision involving the implementation: once the choice is made, the necessary algorithms are simple.” (Sedgewick)
Suppose we have a list of sorted data on which we have to perform the following operations:
Search for an item
Delete a specified item
Insert (add) a specified item
Example: Suppose we begin with the following list:
data: 345 358 490 501 513 555 561 701 724 797
location: 0 1 2 3 4 5 6 7 8 9
What is a list?
A list is a data structure where data is represented linearly
Finite sequence of items from the same data type
If arrays are used, items are stored contiguously in the memory