EBK DATA STRUCTURES AND ALGORITHMS IN C
4th Edition
ISBN: 9781285415017
Author: DROZDEK
Publisher: YUZU
expand_more
expand_more
format_list_bulleted
Videos
Question
Chapter 3, Problem 1E
Program Plan Intro
Circular doubly linked list:
- In a circular doubly linked list, the last node’s “Next” pointer points to first node and “Prev” pointer of first node points to last node making the list circular from both of the directions.
- The “Next” of last link points to first link of list
- The “Prev” of first link points to last of list.
- A circular doubly linked list is shown below:
Expert Solution
Explanation of Solution
Modification of linked list:
Refer figure 3.29 from chapter 3 for the given circular doubly linked list.
Assignment 1
- In the given list list->next denotes first element of list whose value is 1.
- In the given list list->next->next denotes second element of list whose value is 2.
- In the given list list->next->next->next denotes the third element of list whose value is 3
- In the given list list->prev denotes the last element of list whose value is 5, as the list is circular doubly linked list.
- Hence, assignment 1 would make the “Next” of node 3 to point to node 5. Hence, the result is “node 3 to node 5”.
Explanation of Solution
Assignment 2
- In the given list list->prev denotes first element of list whose value is 1.
- In the given list list->prev->prev denotes last element of list whose value is 5.
- In the given list list->prev->prev->prev denotes the fourth element of list whose value is 4
- In the given list list->next denotes first element of list whose value is 1
- In the given list list->next->next denotes second element of list whose value is 2
- In the given list list->next->next->next denotes the third element of list whose value is 3
- In the given list list->next->next->next->prev denotes the “Prev” of fourth element of list
- Hence, assignment 2 would make node 4 point to node 4 itself. Hence, the result is “node 4 to node 4”.
Explanation of Solution
Assignment 3
- In the given list list->next denotes first element of list whose value is 1.
- In the given list list->next->next denotes second element of list whose value is 2.
- In the given list list->next->next->next denotes the third element of list whose value is 3
- In the given list list->next->next->next->prev denotes the previous of fourth element of list
- In the given list list->prev denotes the last element of list whose value is 5, as list is circular linked list.
- In the given list list->prev->prev denotes the fourth element of list whose value is 4.
- In the given list list->prev->prev->prev denotes the previous of fourth element of list
- Hence, assignment 3 would denote same thing and list remains the same. Hence, the result is “No change”.
Explanation of Solution
Assignment 4
- In the given list list->next denotes the first element of list whose value is 1.
- In the given list list->next->next denotes the third element of list whose value is 3.
- Hence, assignment 4 would make the node 1 point to node 3. Hence, the result is “node 1 to node 3”.
Explanation of Solution
Assignment 5
- In the given list list->next denotes the first element of list whose value is 1.
- In the given list list->next->next denotes the second element of list whose value is 2.
- In the given list list->next->next->next denotes the “next” of second element of list whose value is 2.
- In the given list list->next denotes the second element of list whose value is 2.
- In the given list list->next ->prev->next denotes the first element of list whose value is 1.
- Hence, assignment 5 would make the “next” node 2 point to node 1. Hence, the result is “node 2 to node 1”.
Want to see more full solutions like this?
Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!
Students have asked these similar questions
There are some differences between the linked list and the array but the main difference between the list and the array is
a.
List is a dynamic data structure while an array is also dynamic data
b.
Array is a dynamic data structure while a List is a static data because it has a fixed size
c.
List is a static data structure while an array is also a static data because it has a variable size
d.
List is a dynamic data structure while an array is a static data because it has a fixed size
The definition of linked list is given as follows:
struct Node {
ElementType Element ;
struct Node *Next ;
} ;
typedef struct Node *PtrToNode, *List, *Position;
If L is head pointer of a linked list, then the data type of L should be ??
Max Absolute In List Function Lab
Description
Implement function max_abs_val(lst), which returns the maximum absolutevalue of the elements in list.For example, given a list lst: [-19, -3, 20, -1, 0, -25], the functionshould return 25.
The name of the method should be max_abs_val and the method should take one parameter which is the list of values to test. Here is an example call to the function
print(max_abs_val([-19, -3, 20, -1, 0, -25]))
File Name
maxabsinlst.py
Score
There are three tests each worth 2 points
Note: You do not need any other code including the main method or any print statements. ONLY the max_abs_val method is required. Otherwise, the autograder will fail and be unable to grade your code. (I.e., do not include the above example in your code.) The above example should be used be test your code but deleted or comment out upon submission.
PYTHON LAB
Chapter 3 Solutions
EBK DATA STRUCTURES AND ALGORITHMS IN C
Ch. 3 - Prob. 1ECh. 3 - Prob. 2ECh. 3 - Prob. 3ECh. 3 - Prob. 4ECh. 3 - Prob. 5ECh. 3 - Prob. 6ECh. 3 - Prob. 7ECh. 3 - Prob. 8ECh. 3 - Prob. 9ECh. 3 - Prob. 10E
Ch. 3 - Prob. 11ECh. 3 - Prob. 12ECh. 3 - Prob. 13ECh. 3 - Prob. 14ECh. 3 - Prob. 15ECh. 3 - Prob. 16ECh. 3 - Prob. 17ECh. 3 - Prob. 18ECh. 3 - Prob. 19ECh. 3 - Prob. 20ECh. 3 - Prob. 21ECh. 3 - Prob. 22ECh. 3 - Prob. 23ECh. 3 - Prob. 24ECh. 3 - Prob. 25ECh. 3 - Prob. 1PACh. 3 - Prob. 2PACh. 3 - Prob. 3PACh. 3 - Prob. 5PACh. 3 - Prob. 7PA
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- Add the following functions and write a program to test these functions in the classlinkedListType:a. Write the definition of a function that returns the data of the kth element of the linked list. If suchelement is not exist in the list, exit the program. (05)b. Write the definition of a function that deletes the kth element of the linked list. If such element isnot exist in the list, exit the program and display message as output.arrow_forwardConcatenate Map This function will be given a single parameter known as the Map List. The Map List is a list of maps. Your job is to combine all the maps found in the map list into a single map and return it. There are two rules for addingvalues to the map. You must add key-value pairs to the map in the same order they are found in the Map List. If the key already exists, it cannot be overwritten. In other words, if two or more maps have the same key, the key to be added cannot be overwritten by the subsequent maps. Signature: public static HashMap<String, Integer> concatenateMap(ArrayList<HashMap<String, Integer>> mapList) Example: INPUT: [{b=55, t=20, f=26, n=87, o=93}, {s=95, f=9, n=11, o=71}, {f=89, n=82, o=29}]OUTPUT: {b=55, s=95, t=20, f=26, n=87, o=93} INPUT: [{v=2, f=80, z=43, k=90, n=43}, {d=41, f=98, y=39, n=83}, {d=12, v=61, y=44, n=30}]OUTPUT: {d=41, v=2, f=80, y=39, z=43, k=90, n=43} INPUT: [{p=79, b=10, g=28, h=21, z=62}, {p=5, g=87, h=38}, {p=29,…arrow_forwardstruct node{ int a; struct node * nextptr; }; Write two functions. One for inserting new values to a link list that uses the given node structure. void insert(struct node **head, int value); Second function is called to count the number of even numbers in the link list. It returns an integer that represents the number of even numbers. int countEvenNumbers(struct node *head); Write a C program that reads a number of integers from the user and insert those integers into a link list (use insert function). Later pass the head pointer of this link list to a function called countEvenNumbers. This function counts and returns the number of even numbers in the list. The returned value will be printed on the screen. Note 1: Do not modify the function prototypes. Sample Input1: Sample Output1: 45 23 44 12 37 98 33 35 -1 3 Sample Input2: Sample Output2: 11 33 44 21 22 99 123 122 124 77 -1 4arrow_forward
- Write the DLList member function DLList rmv_ret_negative() which should remove nodes with negative values from the original list, add them to another temporary list, and return that list. Example: If the list list1 has [10, -5, -2, 20, 90, -25, 50] then after calling: list1.rmv_ret_negative() list1 should contain [10, 20, 90, 50]arrow_forwardAdd the following functions and write a program to test these functions in the class linkedListType: a. Write the definition of a function that returns the data of the kth element of the linked list. If such element is not exist in the list, exit the program. b. Write the definition of a function that deletes the kth element of the linked list. If such element does not exist in the list, exit the program and display message as output.arrow_forwardQuestion 20 A list is a collection with additional index- and iteration- related operations. True False Question 21 O(N) is the order of growth execution time of the size operation when using the SortedArrayCollection class, assuming a collection size of N. True False Question 22 If N represents the number of elements in the list, then the index-based set method of the ABList class is O(1). True False Question 23 O(N) is the order of growth execution time of the remove operation when using the LinkedCollection class, assuming a collection size of N. True False Question 24 It is not possible to use an array to implement a linked list. True False Question 25 O(N) is the order of growth execution time of the remove operation when using the ArrayCollection class, assuming a collection size of N. True False Question 26 Our linked implementation of lists implements a bounded list. True False Question 27 O(N) is the order of growth execution time of the contains operation…arrow_forward
- Question 40 An application can indicate a specific way to order the elements of a SortedABList list by passing a(n) Comparator object to a constructor of the list class. True False Question 41 A header node is a placeholder node at the beginning of a list, used to simplify list processing. True False Question 42 O(N) is the order of growth execution time of the indexOf operation when using the ABList class, assuming a list size of N. True False Question 43 A trailer node is a placeholder node at the end of a list, used to simplify list processing. True False Question 44 O(1) is the order of growth execution time of the indexOf operation when using the LBList class, assuming a list size of N. True False Question 45 Recall that within the ABList the numElements variable holds the number of elements currently in the list, and the elements array stores those elements. Assuming that a legal index is used, which of the following represents the code for the index-based T…arrow_forwardReplace XXX in the following function header for a doubly-linked list: ListInsertAfter(listName, currentNode, XXX) Group of answer choices headNode tailNode middleNode newNodearrow_forwardhi I really need help with this assignment problem flip_matrix(mat:list)->list You will be given a single parameter a 2D list (A list with lists within it) this will look like a 2D matrix when printed out, see examples below. Your job is to flip the matrix on its horizontal axis. In other words, flip the matrix horizontally so that the bottom is at top and the top is at the bottom. Return the flipped matrix. To print the matrix to the console: print('\n'.join([''.join(['{:4}'.format(item) for item in row]) for row in mat])) Example: Matrix:W R I T XH D R L GL K F M VG I S T CW N M N FExpected:W N M N FG I S T CL K F M VH D R L GW R I T X Matrix:L CS PExpected:S PL C Matrix:A D JA Q HJ C IExpected:J C IA Q HA D Jarrow_forward
- When traversing a single- or double-linked list, you should be careful not to fall off the end of the list or you'll get a type your answer.arrow_forwardWith Head node or not? statement is: if(p->rlink != first) p = p->rlink; O a. It is a Doubly linked list without Head node. O b. It is a Doubly linked list with Head node.arrow_forwardstruct insert_at_back_of_sll { // Function takes a constant Book as a parameter, inserts that book at the // back of a singly linked list, and returns nothing. void operator()(const Book& book) { /// TO-DO (3) /// // Write the lines of code to insert "book" at the back of "my_sll". Since // the SLL has no size() function and no tail pointer, you must walk the // list looking for the last node. // // HINT: Do not attempt to insert after "my_sll.end()". // ///// END-T0-DO (3) ||||// } std::forward_list& my_sll; };arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Introduction to Linked List; Author: Neso Academy;https://www.youtube.com/watch?v=R9PTBwOzceo;License: Standard YouTube License, CC-BY
Linked list | Single, Double & Circular | Data Structures | Lec-23 | Bhanu Priya; Author: Education 4u;https://www.youtube.com/watch?v=IiL_wwFIuaA;License: Standard Youtube License