Implement a city database using unordered lists. Each database record contains the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x and y coordinates. Your database should allow records to be inserted, deleted by name or coordinate, and searched by name or coordinate. Another operation that should be supported is toprint all records within a given distance of a specified point. Implement the database using an array-based list implementation, and then a linked list implementation. Collect running time statistics for each operation in both implementations. What are your conclusions about the relative advantages and
disadvantages of the two implementations? Would storing records on the list in alphabetical order by city name speed any of the operations? Would keeping the list in alphabetical order slow any of the operations?
To implement a city database using unordered lists, we can first start by defining a data structure for each city record. Each record should contain the name of the city (a string of arbitrary length) and the coordinates of the city expressed as integer x and y coordinates.
Next, we can implement the database using an array-based list implementation. This can be done by creating a dynamic array and initializing it with a default size. As records are inserted, they can be added to the end of the array. If the array becomes full, a new larger array can be created and the records can be copied over. To delete a record by name or coordinate, the array can be searched for the record and subsequently removed. To search by name or coordinate, each record in the array can be checked for a match. To print records within a given distance of a specified point, the distance between each record and the specified point can be calculated and checked against the given distance.
For the linked list implementation, each city record can be represented as a node in the linked list. The linked list can have a head pointer pointing to the first node in the list. Records can be inserted by creating a new node and linking it appropriately. Deleting a record by name or coordinate can be done by traversing the list and unlinking the matching node. Searching can be done by traversing the list and looking for a match. Printing records within a given distance of a specified point can be accomplished in a similar manner as the array-based implementation.
To collect running time statistics for each operation in both implementations, you can use a timing method to measure the elapsed time for each operation. This can be done by recording the start time before the operation and then calculating the time difference after the operation completes. Repeat this process multiple times to get an average running time for each operation.
In terms of the relative advantages and disadvantages of the two implementations:
- The array-based list implementation has advantages in terms of efficient random access, as elements can be accessed directly by their indices. However, it may require resizing the array if there are many insertions, which can lead to additional time complexity.
- The linked list implementation has advantages in terms of efficient inserts and deletes, as it only requires updating pointers. However, it may have slower searching and limited random access, as traversing the list is necessary.
Storing records in alphabetical order by city name can speed up search operations in both implementations, as it allows for binary search when looking for a specific city name. However, keeping the list in alphabetical order may slow down insert and delete operations, as the list needs to be maintained in the correct order when inserting or deleting a record. Additional shifting of elements may be required.
In conclusion, the array-based list implementation has advantages in terms of random access, while the linked list implementation has advantages in terms of efficient inserts and deletes. Storing records in alphabetical order by city name can speed up search operations but may slow down insert and delete operations. Ultimately, the choice of implementation depends on the specific requirements and trade-offs of the application.