Java/Python/C# Programs for DLinkedListADT, ConvertToList, ListInsert, QueueADT, and StackADT

Task:

Write separate programs for the following exercises in Java, Python, or C#. Each file should have your name at the top in comment, with short description of what is implemented in that file. Make sure your files have appropriate names as indicated in each exercise. Programs should write output to the Console and have hard coded input in main.

Note 1: If a program is not in approved programming language (or in different language than previous assignment) or has any syntax error, no points will be awarded for that exercise

Note 2: Submitting wrong files or in the wrong format or corrupted files will not be accepted nor will any re-submission be allowed for any such mistake. It is your responsibility to submit the correct files.

a) DLinkedListADT:

Implement doubly linked list ADT using the pseudo code covered in class. The data-type that the ADT should store should be a Trip object with the following attributes/members: id (integer), days (integer), fee (double). You must have all the operations in the pseudo code with the SAME naming convention and statements. The operations for inserting/adding new nodes into the list should not allow duplicate Trip added based on the integer id. The operations printNextList and printPrevList should print all the Trip’s attribute values. Any operation that is implemented differently from the one given (other than changes needed to support Trip as node), will not earn credit.

Add new operation to DLinkedListADT called calculateCost with single parameter for trip’s id. The operation should find the trip associated with the trip id, and then calculate and return the trip’s cost. The cost should be represented as a double (e.g. 105.75 which means $100.75). Cost for the trip is calculated by multiplying the days by the fee.

Add new operation to DLinkedListADT called averageCost with no parameters. The operation should calculate and return the average cost for all the trips in the list.

Analyze and report explaining calculations and final time/space complexity of the new operations

Write test program with main method creating an instance of the DLinkedListADT and calling all the operations to demonstrate they work correctly.

You must implement a class called DLinkedListADT for the ADT implementation in one file and a separate TestDLinkedList class for the test in a different file. You also need a third file with an implementation of Trip class.

Video: Explain the implementation of DLinkedListADT, modifications for Trip, new operation design and implementation, show the program running, and explain output

DLinkedListADT:

b) ConvertToList:

Implement a method that takes an array trips[] which has Trip instances as a parameter. The method then allocates an empty instance of DLinkedListADT called tripList and copies only those elements with trip cost greater than $100, over from the array to the list. The method must check if the array is null/None or empty and throw an exception if it is. The method should return the tripList.

Analyze and report explaining calculations and final time/space complexity of the method.

Write a main method to test the code. The test method should create the trips[] array and populate it with values, then call the convertToList method, and then using the returned list print each element’s data on separate line.

Video: Explain the design and implementation of convertToList method, show the program running, and explain output

c) ListInsert:

Add new linked list operation to DLinkedListADT. The operation is called insertBetween and takes three parameters: insertBetween(int id1, int id2, Trip trip). Then it finds the two nodes in the list that match the given ids and inserts a new node with trip value as next node after node with id1 and before node with id2. The node with id2 does not have to be the next sequential node after node with id1. If the list is null/None or id values are not found it throws an exception with message that the parameters are invalid. If the list is empty it just adds the new node with trip data into the list.

Add test cases to TestDLinkedList class from exercise (a) to demonstrate the code works.

Analyze and report explaining calculations and final time/space complexity of the new operation.

Video: Explain the design and implementation of insertBetween method, show the program running, and explain output

Example 1:

Given linked list with trip elements that have the following order as far as id {101, 151, 110} when we call insertBetween (101, 110, trip) where the trip has the values {105, 5, 10} the updated list will have node elements in the following balance order: {101, 105, 151, 110}

Example 2:

Given linked list with trip elements that have the following order as far as id {101, 151, 110} when we call insertBetween (110, 101, trip) where the trip has the values {105, 5, 10}, the method will throw an exception with message that parameters are invalid.

Implement QueueADT using the DLinkedListADT as underlying storage from previous exercise to store Trip objects as elements and to include all and only operations in the pseudo code.

 Use the given operation names and implementation.
 Modify operations to be able to store and return Trip records
 Add peek operation that has no parameters and returns Trip object that would be deQueued.
 Write test program with main method to demonstrate the correct working of each operation.
 You must implement a class called QueueADT and separate TestQueue class each in a separate file.
 Video: Explain implementation of each operation, discuss time and space analysis of each operation, run program and explain output.

e) StackADT:

 Implement StackADT using the DLinkedListADT as underlying storage from previous exercise to store Account objects as elements and to include all and only operations in the pseudo code.
 Use the given operation names and implementation.
 Modify operations to store and return Trip records
 Add peek operation that has no parameters and returns Trip object that would be pop()ed.
 Write test program with main method to demonstrate the correct working of each operation.
 You must implement a class called StackADT and separate TestStack class each in a separate file.
 Video: Explain implementation of each operation, discuss time and space analysis of each operation, run program and explain output.