Lab 3: Ordered Doubly Linked List Objectives: 1. To introduce the doubly linked list data structure. 2. Converting an im

[answerhappygod]

Lab 3 Ordered Doubly Linked List Objectives 1 To Introduce The Doubly Linked List Data Structure 2 Converting An Im 1 (45.73 KiB) Viewed 39 times

Lab 3 Ordered Doubly Linked List Objectives 1 To Introduce The Doubly Linked List Data Structure 2 Converting An Im 2 (54.2 KiB) Viewed 39 times

Lab 3 Ordered Doubly Linked List Objectives 1 To Introduce The Doubly Linked List Data Structure 2 Converting An Im 3 (37.34 KiB) Viewed 39 times

Lab 3 Ordered Doubly Linked List Objectives 1 To Introduce The Doubly Linked List Data Structure 2 Converting An Im 4 (33.16 KiB) Viewed 39 times

Lab 3 Ordered Doubly Linked List Objectives 1 To Introduce The Doubly Linked List Data Structure 2 Converting An Im 5 (38.84 KiB) Viewed 39 times

Lab 3 Ordered Doubly Linked List Objectives 1 To Introduce The Doubly Linked List Data Structure 2 Converting An Im 6 (29.78 KiB) Viewed 39 times

Lab 3: Ordered Doubly Linked List Objectives: 1. To introduce the doubly linked list data structure. 2. Converting an implementation of singly-linked lists to an implementation of doubly-linked lists. 3. Strengthen the students understanding of the implementation and use of linked lists. Background: A doubly linked list is a variants of linked list structures with additional links that allows for a more efficient insertion or removal of elements from any position in the sequence. Each node contains, besides the next-node link, a second link field pointing to the previous node in the sequence. The two links may be called forward(s) and backwards, or next and previous. Example: The following figure shows a doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node. Lab Exercise: 12 99 Implement the following classes: 1. class Course that includes four instance variables: ID #course ID Name #course name next #link next prev #link previous 37 Your class should have the following: • A constructor that initializes the two instance variables id and name. • Set and get methods for each instance variable. 2. class Department that includes three instance variables: deptName head tail 13
Your class should have the following: • a constructor that initializes the department name • exist (id) that checks whether the course object with id passed as parameter exists in the linked list or not. .insert(id, n) that creates and adds the course if the course with id passed as parameter does not exist in the linked list. The course must be added in ascending order. The method will return false if the id was a duplicate. remove (id) that deletes a course if it exists in the linked list and return true. The method will return false if the id was not found in the list. • • findCourse (id) that returns a course name if the id exists in the linked list. • print () that prints the department name and all the courses in the linked list in ascending order. • printReverse() that prints the department name and all the courses in the linked list in descending order. Write the expected time and space complexity as a comment at the beginning of each method of your class. 3. Write a test program named Lab3Test. Do the following: • Input the department name then create a department object. • Display a menu to the user asking for a choice to be entered as follows: The program can perform the following: 1- insert a course 2- remove a course 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: • The program will perform the action selected by the user and display a proper message when necessary. • The program will repeat these actions until the user terminates the program (Hint: Use a loop). Sample Output: Please enter the name of the department: Computer Engineering The program can perform the following: 1- insert a course 2- remove a course 3- search for a course 4- print courses 14
5- print courses in reverse 6- exit Please enter your selection: 30 Error! Incorrect choice. The program can perform the following: 1- insert a course 2- remove a course 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 4 Computer Engineering department does not have any courses. The program can perform the following: 1- insert a course 2- remove a course 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 1 Enter the course number or -1 to stop: 300 Enter the course name: Design and Analysis of Algorithms Enter the course number or -1 to stop: 356 Enter the course name: Computer Networks I Enter the course number or -1 to stop: 300 Enter the course name: testing duplicate Error! duplicate ID number... Enter the course number or -1 to stop: 325 Enter the course name: Human-Computer Interaction Enter the course number or -1 to stop: 262 Enter the course name: Fundamentals of Digital Logic Enter the course number or -1 to stop: -1 The program can perform the following: 1- insert a course 2- remove a course. 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 4 15
Courses in Computer Engineering department are: 1- 262 Fundamentals of Digital Logic 2 3 325 Human-Computer Interaction 4- 356 Computer Networks I 300 Design and Analysis of Algorithms The program can perform the following: 1- insert a course 2- renove a course 3- search for a course 4- print courses 5- print courses in reverse. 6- exit Please enter your selection: 5 Courses in Computer Engineering department printed in reverse are: 1- 356 Computer Networks I 2- 325 Human-Computer Interaction 3 4 262 Fundamentals of Digital Logic The program can perform the following: 1- insert a course 300 Design and Analysis of Algorithms 2- remove a course 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 2 Enter the course number: 325 The course was removed The program can perform the following: 1- insert a course 2- remove a course 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 2 Enter the course number: 325 The course is not in the list The program can perform the following: 1- insert a course 2- remove a course 3- search for a course 16
4- print courses 5- print courses in reverse 6- exit Please enter your selection: 4 Courses in Computer Engineering department are: 1 - 262 Fundamentals of Digital Logic 2- 300 Design and Analysis of Algorithms 3 356 Computer Networks I The program can perform the following: 1- insert a course 2- renove a course. 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 5 Courses in Computer Engineering department printed in reverse are: 1 356 Computer Networks I 2- 300 Design and Analysis of Algorithms 3 262 Fundamentals of Digital Logic The program can perform the following: 1- insert a course 2- renove a course 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 3 Enter the course number: 300 The id: 300 corresponds to Design and Analysis of Algorithms The program can perform the following: 1- insert a course 2- renove a course. 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 3 Enter the course number: 325 The id: 325 does not correspond to any course in the department The program can perform the following: 1- insert a course 17
2- remove a course 3- search for a course 4- print courses 5- print courses in reverse 6- exit Please enter your selection: 6 Exiting the program... Additional Exercise: Write the following classes that implement a double Linked List of Strings: 1) Class Word that includes three instance variables: - word next prev It contains the following methods: - A constructor that initializes the instance variable word. Set and get method for each instance variable. 2) Class Double Linked List that includes two instance variables: head and tail. - It contains the following methods: - insert (n) that creates and adds a Word at the end of the linked List. -printForward() that prints the content of the linked list forward. -printBackward() that prints the content of the linke list backward. remove (n) that removes a word if it exists in the list. Write a Test program. Do the following: - Create an object of class Doublelinkedlist. -Read a sentence from the user and store it in a variable (for example, String sentence). **** Split the sentence into words and store the words in an array. (Hint: use method split) Insert each word of the array in the linked list by calling method insert. Call method printForward() Call method printBackward() Read a String from the user, call method remove and then call method printForward() Sample Output Enter a String: I like data structures Printing the linked list forward: I like data structures Printing the linked list backward: structures data like I Enter a word to be removed: structures Printing the linked list forward: I like data