Dynamic data structures (based on objects)
Dynamic data structures: nodes and chains of nodes
Dynamic1. An object A_{1} of the Node class is given. The class contains public properties Data (of integer type) and Next (of Node type). The given object is linked by its Next property with the next object of the same type (that is, the Next property of the given object contains the reference to the next object). Output the value of the Data property for each object, and also output a reference to the object A_{2} that follows the given object.
Dynamic2°. An object A_{1} of Node type is given. The object is linked by its Next property with the next object of the same type, that object is linked with the next one, and so on, until the last object whose Next property equals null (as a result, we obtain a chain of linked objects). Output the value of the Data property for each chain component, the chain length (that is, the amount of its components) and a reference to the last chain component.
Dynamic data structures: stack
Dynamic3°. An integer D and the top A_{1} of a nonempty stack are given. Push a component with the value D onto the stack and output a reference A_{2} to a new top of the stack.
Dynamic4. An integer N (> 0) and a sequence of N integers are given. Create a stack that contains N components with the given values (a component with the last value must be the top of the stack) and output a reference to the top of the stack.
Dynamic5°. The top A_{1} of a nonempty stack is given. Pop the top component off the stack and output its value D and a reference A_{2} to a new top of the stack. If the stack will be empty after popping the component then A_{2} must be equal to null. After popping the component release resources allocated for this component; for this purpose call its Dispose method.
Dynamic6. The top A_{1} of a stack is given; the stack contains at least ten components. Pop the first nine components off the stack and output their values and a reference A_{2} to a new top of the stack. After popping components release resources allocated for these components; for this purpose call the Dispose method for each of them.
Dynamic7. The top A_{1} of a stack is given (if the stack is empty then A_{1} equals null). Pop all components off the stack and output their values. Also output the amount of popped components (if the stack is empty then output 0). After popping components release resources allocated for these components; for this purpose call the Dispose method for each of them.
Dynamic8°. The tops A_{1} and A_{2} of two nonempty stacks are given. Move all components from the first stack into the second one (as a result, all components of the first stack will be contained within the second stack in inverse order). Output a reference to a new top of the second stack. Do not create new instances of the Node class.
Dynamic9°. The tops A_{1} and A_{2} of two nonempty stacks are given. Move components from the first stack into the second one until the value of the top component of the first stack is equal to an even number (as a result, all components having been moved will be contained within the second stack in inverse order). If the first stack contains no components with even values then move all its components. Output a reference to a new top for each stack (if the first stack will be empty then output null for this stack). Do not create new instances of the Node class.
Dynamic10°. The top A_{1} of a nonempty stack is given. Create two new stacks by moving the given stack components whose values are even (odd) numbers into the first (second) new stack respectively. As a result, all components having been moved will be contained within each new stack in inverse order; one of the new stacks may be empty. Output a reference to the top for each new stack (if one of the new stacks will be empty then output null for this stack). Do not create new instances of the Node class.
Dynamic11°. The top A_{1} of a stack is given (if the stack is empty then A_{1} equals null). Also an integer N (> 0) and a sequence of N integers are given. Define a new class called IntStack that contains the following members: • a private field, top, of Node type (this field refers to the top of the stack); • a constructor with the parameter aTop of Node type (this parameter refers to the top of some existing stack); • a procedure Push(D) that pushes a new component with the value D onto the stack (an integer D is an input parameter); • a procedure Put that output a reference to the top field by means of the Put method of the PT class (this procedure has no parameters). Using the Push method, push all elements of the given sequence onto the given stack (the last number must be the value of the top component). Using the Put method of the IntStack class, output a reference to a new top of the stack.
Dynamic12°. The top A_{1} of a stack is given; the stack contains at least five components. Include an integer function Pop in the IntStack class (see Dynamic11); this function pops the top component off the stack, calls the Dispose method for this component, and returns the value of the popped component. The function has no parameters. Using this function, pop five components off the given stack and output their values. Also output a reference to a new top of the stack (if the stack will be empty then this reference must be equal to null).
Dynamic13. The top A_{1} of a stack is given. Include two functions in the IntStack class (see Dynamic11): a logical function IsEmpty returns true if the stack is empty, and false otherwise; an integer function Peek returns the value of the top component of the stack. The functions have no parameters. Using these functions and the Pop function from the task Dynamic12, pop five components (or all stack components if their amount is less than five) off the given stack and output their values. Also output the return value of the IsEmpty function for the resulting stack. At last, in the case of the nonempty resulting stack, output the value of its top component and a reference to this component.
Dynamic data structures: queue
Dynamic14. A sequence of 10 integers is given. Create a queue that contains components with the given values (a component with the first value must be the head of the queue, a component with the last value must be the tail of the queue) and output references A_{1} and A_{2} to the head and tail of the queue respectively.
Dynamic15. A sequence of 10 integers is given. Create two queues; the first one must contain the given integers with odd order numbers (1, 3, …, 9), the second one must contain the given integers with even order numbers (2, 4, …, 10). Output references to the head and tail of the first queue and then output references to the head and tail of the second one.
Dynamic16. A sequence of 10 integers is given. Create two queues; the first one must contain the given integers with odd values (in the same order), the second one must contain the given integers with even values (in the same order). Output references to the head and tail of the first queue and then output references to the head and tail of the second one (if one of the queues will be empty then output null twice for this queue).
Dynamic17. An integer D and references A_{1} and A_{2} to the head and tail of a queue are given (if the queue is empty then the references equal null). Add a component with the value D to the end of the queue and output references to the head and tail of the resulting queue.
Dynamic18. An integer D and references A_{1} and A_{2} to the head and tail of a queue are given; the queue contains at least two components. Add a component with the value D to the end of the queue and remove the first component from the front of the queue. Output the value of the component being removed and also output references to the head and tail of the resulting queue. After removing the component call its Dispose method.
Dynamic19. An integer N (> 0) and references A_{1} and A_{2} to the head and tail of a nonempty queue are given. Remove N initial components from the queue and output their values (if the queue contains less than N components then remove all its components). Also output references to the head and tail of the resulting queue (if the queue will be empty then output null twice). After removing components call the Dispose method for each of them.
Dynamic20. References A_{1} and A_{2} to the head and tail of a nonempty queue are given. Remove components from the front of the queue until the value of the head of the queue is equal to an even number; output values of all components being removed (if the queue contains no components with even values then remove all its components). Also output references to the head and tail of the resulting queue (if the queue will be empty then output null twice). After removing components call the Dispose method for each of them.
Dynamic21. Two queues are given; references A_{1} and A_{2} refer to the head and tail of the first one, references A_{3} and A_{4} refer to the head and tail of the second one (if some queue is empty then the corresponding references equal null). Move all components from the first queue (starting with its first component) to the end of the second one. Output references to the head and tail of the changed second queue. Do not create new instances of the Node class.
Dynamic22. An integer N (> 0) and two nonempty queues are given; references A_{1} and A_{2} refer to the head and tail of the first one, references A_{3} and A_{4} refer to the head and tail of the second one. Move N initial components of the first queue to the end of the second one (if the first queue contains less than N components then move all its components). Output references to the head and tail of the first queue and then output references to the head and tail of the second one (if the first queue will be empty then output null twice for this queue). Do not create new instances of the Node class.
Dynamic23. Two nonempty queues are given; references A_{1} and A_{2} refer to the head and tail of the first one, references A_{3} and A_{4} refer to the head and tail of the second one. Move initial components of the first queue to the end of the second one until the value of the head of the first queue is equal to an even number (if the first queue contains no components with even values then move all its components). Output references to the head and tail of the first queue and then output references to the head and tail of the second one (if the first queue will be empty then output null twice for this queue). Do not create new instances of the Node class.
Dynamic24. Two nonempty queues are given; references A_{1} and A_{2} refer to the head and tail of the first one, references A_{3} and A_{4} refer to the head and tail of the second one. The queues contain the equal amount of components. Combine the given queues into a new one; the resulting queue must contain alternating components of the given queues starting with the head of the first one. Output references to the head and tail of the resulting queue. Do not create new instances of the Node class.
Dynamic25°. Two nonempty queues are given; references A_{1} and A_{2} refer to the head and tail of the first one, references A_{3} and A_{4} refer to the head and tail of the second one. The values of components of each given queue are in ascending order. Combine the given queues into a new one; the values of components of the resulting queue must be in ascending order too. Output references to the head and tail of the resulting queue. Do not create new instances of the Node class; do not change the Data properties.
Dynamic26. References A_{1} and A_{2} to the head and tail of a queue are given (if the queue is empty then the references equal null). Also an integer N (> 0) and a sequence of N integers are given. Define a class called IntQueue that contains the following members: • two private fields, head and tail, of Node type (these fields refer to the head and tail of the queue respectively); • a constructor with the parameters aHead and aTail of Node type (these parameters refer to the head and tail of some existing queue); • a procedure Enqueue(D) that adds a new component with the value D to the end of the queue (an integer D is an input parameter); • a procedure Put that output references to the head and tail fields by means of the Put method of the PT class (this procedure has no parameters). Using the Enqueue method, add all elements of the given sequence to the end of the given queue. Using the Put method of the IntQueue class, output references to the head and tail of the resulting queue.
Dynamic27. References A_{1} and A_{2} to the head and tail of a queue are given; the queue contains at least five components. Include an integer function Dequeue in the IntQueue class (see Dynamic26); this function removes the first component from the front of the queue, calls the Dispose method for this component, and returns the value of the removed component. The function has no parameters. Using this function, remove five initial components from the front of the given queue and output their values. Also output references to the head and tail of the queue (if the queue will be empty then output null twice).
Dynamic28. References A_{1} and A_{2} to the head and tail of a queue are given. Include a logical function IsEmpty in the IntQueue class (see Dynamic26); this function returns true if the queue is empty, and false otherwise. The function has no parameters. Using this function and also the Dequeue function from the task Dynamic27, remove five initial components (or all queue components if their amount is less than five) from the front of the given queue and output their values. Also output the return value of the IsEmpty function for the resulting queue and references to the head and tail of this queue (if the queue will be empty then output null twice).
Dynamic data structures: doubly linked list
Dynamic29. An object A_{2} of the Node class is given. The class contains public properties Data (of integer type), Prev and Next (each of Node type). The given object is linked by its Prev and Next properties with the previous and next object of the same type respectively (that is, the Prev and Next properties of the given object contain references to the previous and next object). Output the values of the Data property for the previous and next object, and also output references A_{1} and A_{3} to the previous and next object.
Dynamic30°. A reference A_{1} to the beginning of a chain of objects is given; objects have the Node type and are linked by their Next property. Using the Prev property of the Node class, transform the given (singly linked) chain into the doubly linked chain whose components are linked not only with the next ones (by the Next property) but also with the previous ones (by the Prev property). The Prev property of the first chain component must be equal to null. Output a reference A_{2} to the last component of the resulting chain.
Dynamic31. A reference A_{0} to one of the components of a nonempty doubly linked list is given. Output the amount N of the list components and also references A_{1} and A_{2} to the first and last component respectively.
Dynamic32. Two integers D_{1}, D_{2} and a reference A_{0} to one of the components of a nonempty doubly linked list are given. Insert a new component with the value D_{1} at the beginning of the list; insert a new component with the value D_{2} at the end of the list. Output references to the first and last list component.
Dynamic33. An integer D and a reference A_{0} to one of the components of a nonempty doubly linked list are given. Insert a new component with the value D before the given list component. Output a reference to the component being inserted.
Dynamic34. An integer D and a reference A_{0} to one of the components of a nonempty doubly linked list are given. Insert a new component with the value D after the given list component. Output a reference to the component being inserted.
Dynamic35. References A_{1} and A_{2} to the first and last component of a doubly linked list are given. The list contains at least two components. Double occurrences of the first and last list components (new components must be inserted before the existing ones with the same value). Output a reference to the first component of the resulting list.
Dynamic36. References A_{1} and A_{2} to the first and last component of a doubly linked list are given. The list contains at least two components. Double occurrences of the first and last list components (new components must be inserted after the existing ones with the same value). Output a reference to the last component of the resulting list.
Dynamic37. A reference A_{1} to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd order numbers (new components must be inserted before the existing ones with the same value). Output a reference to the first component of the resulting list.
Dynamic38. A reference A_{1} to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd order numbers (new components must be inserted after the existing ones with the same value). Output a reference to the last component of the resulting list.
Dynamic39. A reference A_{1} to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd values (new components must be inserted before the existing ones with the same value). Output a reference to the first component of the resulting list.
Dynamic40. A reference A_{1} to the first component of a nonempty doubly linked list is given. Double occurrences of all list components with odd values (new components must be inserted after the existing ones with the same value). Output a reference to the last component of the resulting list.
Dynamic41. A reference A_{0} to one of the components of a nonempty doubly linked list is given. Remove this component from the list and output references to its previous and next component in the list (one or both these components may be absent; output null for each absent component). After removing the component call its Dispose method.
Dynamic42. A reference A_{1} to the first component of a doubly linked list is given. The list contains at least two components. Remove all components with odd order numbers from the list and output a reference to the first component of the resulting list. After removing components call the Dispose method for each of them.
Dynamic43. A reference A_{1} to the first component of a nonempty doubly linked list is given. Remove all components with odd values from the list and output a reference to the first component of the resulting list (if this list will be empty then output null). After removing components call the Dispose method for each of them.
Dynamic44. A reference A_{0} to one of the components of a nonempty doubly linked list is given. Move this component to the end of the list and output references to the first and last component of the resulting list. Do not create new instances of the Node class; do not change the Data properties.
Dynamic45. A reference A_{0} to one of the components of a nonempty doubly linked list is given. Move this component to the beginning of the list and output references to the first and last component of the resulting list. Do not create new instances of the Node class; do not change the Data properties.
Dynamic46. An integer K (> 0) and a reference A_{0} to one of the components of a nonempty doubly linked list are given. Move this component by K positions forward in the list (if the list contains less than K components after the given component then move it to the end of the list). Output references to the first and last component of the resulting list. Do not create new instances of the Node class; do not change the Data properties.
Dynamic47. An integer K (> 0) and a reference A_{0} to one of the components of a nonempty doubly linked list are given. Move this component by K positions backward in the list (if the list contains less than K components before the given component then move it to the beginning of the list). Output references to the first and last component of the resulting list. Do not create new instances of the Node class; do not change the Data properties.
Dynamic48. References A_{X} and A_{Y} to different components of a doubly linked list are given. The component A_{X} precedes the component A_{Y} in the list but need not be adjacent with it. Exchange the given components in the list and output a reference to the first component of the resulting list. Do not create new instances of the Node class; do not change the Data properties.
Dynamic49°. A reference A_{1} to the first component of a nonempty doubly linked list is given. Rearrange list components by moving all components with odd order numbers to the end of the list (in the same order). Output a reference to the first component of the resulting list. Do not create new instances of the Node class; do not change the Data properties.
Dynamic50. A reference A_{1} to the first component of a nonempty doubly linked list is given. Rearrange list components by moving all components with odd values to the end of the list (in the same order). Output a reference to the first component of the resulting list. Do not create new instances of the Node class; do not change the Data properties.
Dynamic51. Two nonempty doubly linked lists are given; references A_{1} and A_{2} refer to the first and last component of the first list, a reference A_{0} refers to one of the components of the second list. Combine the given lists by inserting all components of the first list (in the same order) before the given component of the second list. Output references to the first and last component of the combined list. Do not create new instances of the Node class.
Dynamic52. Two nonempty doubly linked lists are given; references A_{1} and A_{2} refer to the first and last component of the first list, a reference A_{0} refers to one of the components of the second list. Combine the given lists by inserting all components of the first list (in the same order) after the given component of the second list. Output references to the first and last component of the combined list. Do not create new instances of the Node class.
Dynamic53. References A_{X} and A_{Y} to different components of a doubly linked list are given. The component A_{X} precedes the component A_{Y} in the list but need not be adjacent with it. Move list components that are located between the given components (including these components) to a new list (in the same order). Output references to the first components of the changed and new list. If the changed list will be empty then output null for this list. Do not create new instances of the Node class.
Dynamic54. References A_{X} and A_{Y} to different components of a doubly linked list are given. The component A_{X} precedes the component A_{Y} in the list but need not be adjacent with it. Move list components that are located between the given components (not including these components) to a new list (in the same order). Output references to the first components of the changed and new list. If the new list will be empty then output null for this list. Do not create new instances of the Node class.
Dynamic55°. A reference A_{1} to the first component of a nonempty doubly linked list is given. Transform this list to the circular one by assigning the first component reference to the Next property of the last component and the last component reference to the Prev property of the first component. Output a reference to the component that has been the last component of the given list.
Dynamic56. References A_{1} and A_{2} to the first and last component of a doubly linked list are given. The amount of list components is an even number. Split the list into two circular lists (see Dynamic55); the first (second) resulting list must contain the first (second) half of components of the given list respectively. Output references A_{3} and A_{4} to two middle components of the given list; the object A_{3} must be contained in the first resulting circular list, the object A_{4} must be contained in the second one. Do not create new instances of the Node class.
Dynamic57. An integer K (> 0) and references A_{1} and A_{2} to the first and last component of a nonempty doubly linked list are given. Perform a cyclic shift of all list components by K positions forward (that is, from the beginning toward the end of the list). Output references to the first and last component of the resulting list. The required shift should be performed as follows: transform the given list to the circular one (see Dynamic55) and then break this circular list at the position that corresponds to the given value of K. Do not create new instances of the Node class.
Dynamic58. An integer K (> 0) and references A_{1} and A_{2} to the first and last component of a nonempty doubly linked list are given. Perform a cyclic shift of all list components by K positions backward (that is, from the end toward the beginning of the list). Output references to the first and last component of the resulting list. The required shift should be performed as follows: transform the given list to the circular one (see Dynamic55) and then break this circular list at the position that corresponds to the given value of K. Do not create new instances of the Node class.
Dynamic59°. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a doubly linked list are given (if the list is empty then the references equal null). Also an integer N (> 0) and a sequence of N integers are given. Define a new class called IntList that contains the following members: • three private fields—first, last, current—of Node type (these fields refer to the first, last, and current component of the list respectively); • a constructor with the parameters aFirst, aLast, aCurrent of Node type (these parameters refer to the first, last, and current component of some existing list); • a procedure InsertLast(D) that inserts a new component with the value D at the end of the list (an integer D is an input parameter; the component being inserted becomes the current component of the list); • a procedure Put that output references to the fields first, last, and current by means of the Put method of the PT class (this procedure has no parameters). Using the InsertLast method, insert all elements of the given sequence at the end of the given list (in the same order). Using the Put method of the IntList class, output references to the first, last, and current component of the resulting list.
Dynamic60. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a doubly linked list are given (if the list is empty then the references equal null). Also an integer N (> 0) and a sequence of N integers are given. Include a procedure InsertFirst(D) in the IntList class (see Dynamic59); this procedure inserts a new component with the value D at the beginning of the list (an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert all elements of the given sequence at the beginning of the given list (a component with the last value must be the first component of the resulting list). Output references to the first, last, and current component of the resulting list.
Dynamic61. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a nonempty doubly linked list and five integers are given. Include a procedure InsertBefore(D) in the IntList class (see Dynamic59); this procedure inserts a new component with the value D before the current component of the list (an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output references to the first, last, and current component of the resulting list.
Dynamic62. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a nonempty doubly linked list and five integers are given. Include a procedure InsertAfter(D) in the IntList class (see Dynamic59); this procedure inserts a new component with the value D after the current component of the list (an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output references to the first, last, and current component of the resulting list.
Dynamic63°. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a nonempty doubly linked list are given. Include four methods in the IntList class (see Dynamic59): a procedure ToFirst makes the first component of the list the current one; a procedure ToNext makes the component, which follows the current component of the list, the new current one (provided that such a component exists); a procedure SetData(D) assigns a new integer value D to the current component of the list (an integer D is an input parameter); a logical function IsLast returns true if the current component of the list is the last component, and false otherwise. The ToFirst, ToNext, IsLast methods have no parameters. Using these methods, assign zero value to the list components with odd order numbers. Output the amount of list components and also output references to the first, last, and current component of the resulting list (the current component should be the last one).
Dynamic64. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a nonempty doubly linked list are given. Include four methods in the IntList class (see Dynamic59): a procedure ToLast makes the last component of the list the current one; a procedure ToPrev makes the component, which precedes the current component of the list, the new current one (provided that such a component exists); an integer function GetData returns the value of the current component of the list; a logical function IsFirst returns true if the current component of the list is the first component, and false otherwise. All these methods have no parameters. Using these methods, browse all list components (from the end toward the beginning of the list) and output their values that are even numbers. Also output the amount of list components.
Dynamic65. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a doubly linked list are given. The list contains at least five components. Include an integer function DeleteCurrent in the IntList class (see Dynamic59); this function removes the current component of the list, calls the Dispose method for this component, and returns the value of the removed component. The function has no parameters. If the next component of the list exists then it becomes the new current component, otherwise the last component becomes the new current one. Using this function, remove five components from the given list and output their values. Also output references to the first, last, and current component of the resulting list (if the resulting list will be empty then output null three times).
Dynamic66. References A_{1}, A_{2}, and A_{3} to the first, last, and current component of a nonempty doubly linked list are given. Include a procedure Split(L_{1}, L_{2}) as a class method in the IntList class (see Dynamic59); this procedure moves some components of a list L_{1} into a new list L_{2}: components between the current and last component inclusively must be moved (as a result, the list L_{1} will be split into two parts; the first part may be empty). An object L_{1} of IntList type is an input parameter, an object L_{2} of the same type is an output parameter. The first component of each nonempty resulting list becomes the current component of this list. The procedure should not create new instances of the Node class. Using this procedure, split the given list into two lists and output references to the first, last, and current component of each resulting list.
Dynamic67. References to the first, last, and current component of two nonempty doubly linked lists are given. Include a procedure Add(L_{1}, L_{2}) as a class method in the IntList class (see Dynamic59); this procedure inserts all components of a list L_{1} (in the same order) at the end of a list L_{2}; as a result, the list L_{1} will be empty. The first component being inserted becomes the current component of the list L_{2}. Objects L_{1} and L_{2} of IntList type are input parameters. The procedure should not create new instances of the Node class. Using this procedure, insert the first given list at the end of the second one and output references to the first, last, and current component of the combined list.
Dynamic68. References to the first, last, and current component of two nonempty doubly linked lists are given. Include a procedure Insert(L_{1}, L_{2}) as a class method in the IntList class (see Dynamic59); this procedure inserts all components of a list L_{1} (in the same order) before the current component of a list L_{2}; as a result, the list L_{1} will be empty. The first component being inserted becomes the current component of the list L_{2}. Objects L_{1} and L_{2} of IntList type are input parameters. The procedure should not create new instances of the Node class. Using this procedure, insert the first given list before the current component of the second one and output references to the first, last, and current component of the combined list.
Dynamic69. References to the first, last, and current component of two doubly linked lists are given; the second list may be empty. Include a procedure MoveCurrent(L_{1}, L_{2}) as a class method in the IntList class (see Dynamic59); this procedure removes the current component from a list L_{1} and inserts this component after the current component of a list L_{2}. If the next component of the list L_{1} exists then it becomes the new current component of this list, otherwise the last component becomes the new current one; the component being inserted becomes the current component of the list L_{2}. Objects L_{1} and L_{2} of IntList type are input parameters. The procedure should not create new instances of the Node class. Using this procedure, move the current component of the first given list into the second one and output references to the first, last, and current component of each resulting list (if the first resulting list will be empty then output null three times for this list).
Dynamic data structures: list with the barrier component
Dynamic70°. References A_{1} and A_{2} to the first and last component of a doubly linked list are given (a doubly linked list is implemented by a chain of linked nodes of Node type, the Prev property of the first node and the Next property of the last node are equal to null); if the list is empty then the references equal null. Transform the given list into the circular list (see Dynamic55) with a barrier component. The barrier component has zero value and is linked with the first and last component of the given list by the Next and Prev property respectively (if the given list is empty then the Next and Prev properties of the barrier component must refer to the barrier component itself). Output a reference to the barrier component of the resulting list. Do not create new instances of the Node class except the barrier component.
Dynamic71. References A_{1} and A_{2} to the barrier and current component of a doubly linked list are given (see the barrier component definition in Dynamic70). Move the given list components that are between the current and last component (inclusively) to a new list with the barrier component. If the current component of the given list is its barrier component then the new list must be empty (that is, it must contain the barrier component only). Output a reference to the barrier component of the new list. Do not create new instances of the Node class except the barrier component of the new list.
Dynamic72. References A_{1} and A_{2} to the barrier components of two doubly linked lists are given (see the barrier component definition in Dynamic70). Combine the given lists by linking the last component of the first list with the first component of the second list. Use the barrier component of the first list as the barrier component of the combined list. Output references to the first and last component of the combined list (if the combined list will be empty then output a reference to its barrier component twice). After removing the superfluous barrier component (of the second list) call its Dispose method.
Dynamic73. References A_{1} and A_{2} to the barrier components of two doubly linked lists are given (see the barrier component definition in Dynamic70). Combine the given lists by linking the last component of the first list with the first component of the second list. Use the barrier component of the second list as the barrier component of the combined list. Output references to the first and last component of the combined list (if the combined list will be empty then output a reference to its barrier component twice). After removing the superfluous barrier component (of the first list) call its Dispose method.
Dynamic74°. References A_{1} and A_{2} to the barrier and current component of a doubly linked list are given (see the barrier component definition in Dynamic70). Also an integer N (> 0) and a sequence of N integers are given. Define a new class called IntListB that contains the following members: • two private fields, barrier and current, of Node type (these fields refer to the barrier and current component of the list respectively); • a constructor with the parameters aBarrier and aCurrent of Node type (these parameters refer to the barrier and current component of some existing list); • a procedure InsertLast(D) that inserts a new component with the value D at the end of the list (an integer D is an input parameter; the component being inserted becomes the current component of the list); • a procedure Put that output a reference to the current field by means of the Put method of the PT class (this procedure has no parameters). Using the InsertLast method, insert all elements of the given sequence at the end of the given list (in the same order). Using the Put method of the IntListB class, output a reference to the current component of the resulting list.
Dynamic75. References A_{1} and A_{2} to the barrier and current component of a doubly linked list are given. Also an integer N (> 0) and a sequence of N integers are given. Include a procedure InsertFirst(D) in the IntListB class (see Dynamic74); this procedure inserts a new component with the value D at the beginning of the list (an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert all elements of the given sequence at the beginning of the given list (a component with the last value must be the first component of the resulting list). Output a reference to the current component of the resulting list.
Dynamic76. References A_{1} and A_{2} to the barrier and current component of a doubly linked list and five integers are given. Include a procedure InsertBefore(D) in the IntListB class (see Dynamic74); this procedure inserts a new component with the value D before the current component of the list (an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output a reference to the current component of the resulting list.
Dynamic77. References A_{1} and A_{2} to the barrier and current component of a doubly linked list and five integers are given. Include a procedure InsertAfter(D) in the IntListB class (see Dynamic74); this procedure inserts a new component with the value D after the current component of the list (an integer D is an input parameter). The component being inserted becomes the current component of the list. Using this procedure, insert five given integers into the given list. Output a reference to the current component of the resulting list.
Dynamic78°. References A_{1} and A_{2} to the barrier and current component of a doubly linked list are given. Include four methods in the IntListB class (see Dynamic74): a procedure ToFirst makes the first component of the list the current one; a procedure ToNext makes the component, which follows the current component of the list, the current one; a procedure SetData(D) assigns a new integer value D to the current component of the list provided that the current component is not the barrier one (an integer D is an input parameter); a logical function IsBarrier returns true if the current component of the list is the barrier component, and false otherwise. The ToFirst, ToNext, IsBarrier methods have no parameters. Using these methods, assign zero value to the list components with odd order numbers. Output the amount of list components and a reference to the current component of the resulting list (the current component should be the barrier one). The components are numbered from the first component, which has the order number 1; the barrier component is not numbered and should not be counted.
Dynamic79. References A_{1} and A_{2} to the barrier and current component of a doubly linked list are given. Include three methods in the IntListB class (see Dynamic74): a procedure ToLast makes the last component of the list the current one; a procedure ToPrev makes the component, which precedes the current component of the list, the new current one; an integer function GetData returns the value of the current component of the list. All these methods have no parameters. Using these methods and also the IsBarrier function from the task Dynamic78, browse all list components from the end toward the beginning of the list and output their values that are even numbers. Also output the amount of list components. The barrier component should not be processed and counted.
Dynamic80. References A_{1} and A_{2} to the barrier and current component of a nonempty doubly linked list are given; the current component is not the barrier one. Include an integer function DeleteCurrent in the IntListB class (see Dynamic74); this function removes the current component of the list, calls the Dispose method for this component, and returns the value of the removed component. The function has no parameters. If the next component of the list is not the barrier one then it becomes the new current component, otherwise the previous component becomes the new current one. If the current component is the barrier one then the function performs no actions and returns 0. Using this function and also the IsBarrier function from the task Dynamic78, remove five components from the given list (or all components if their amount is less than five) and output their values. Also output a reference to the current
component of the resulting list.
