Data Structures for Storing an Airline System

Part 1 - Choosing the Best Data Structure

Your task is to decide what data structure/s would be best to store this information. This can include any of the data structures studied in the module, e.g. graphs, hash maps, linked lists, trees. When selecting a data structure, think about what operations the company might want to perform with the data, and which structures would be more efficient for these operations.

(A) Explain any decisions you made or assumptions about the airline system, e.g. whether or not there can be more than one flight operating between the same two cities. This explanation is very important to allow us to judge whether your solution correctly handles the scenario you have chosen, so make sure that you explain it clearly.

(B) Explain which data structure/s you chose and how it would store the information. The task is to explain how it will be used for this particular problem, not just generic information about the data structure. Be as specific as possible, e.g. if you chose to use a graph, explain details such as what type of graph you are using, whether it will be implemented as an adjacency matrix or adjacency lists, what the vertices represent, what the edges represent, what any weightings on the edges represent, etc.

If you used a hash map, state what type the keys and values are, what the keys and values represent, etc. Note that these are just examples of the kind of information required. What you will need to describe will depend on your chosen solution. The idea is to make it clear what the solution is and how the information is going to be represented.

(C) Show, with the aid of diagrams or tables if appropriate, how the information would be stored in your chosen structure. The information you show on your diagrams should include at least six flights and five cities.

Justification of the choice Explain the reasons behind your choice. This might include issues like the time complexity of operations that will be used on your structure/s, the space complexity, the ability of your chosen structure to handle a particular kind of information, or any other reasons you had. If relevant, compare it with alternative choices to explain the advantages of your solution.

Operations Give two examples of operations that can be performed using your data structure. Here are some suggestions: Finding whether it is possible to travel directly from a given city to another given city. Finding the cities that can be reached directly from a given city. Listing all the flights and their start and destination cities. Finding all the cities that can reach a given city. You are welcome to think of other similar operations that would work with your solution.

Note that this does not include generic low-level operations that are commonly used on your data structure but are not particular to this problem, e.g. insert or delete in a linked list. For each of the example operations you choose:

(i)  Explain how it would work using the data structure/s you chose and

(ii) State what time complexity it would have.