Programming Taskbook

1100 training tasks on programming

Main

Tasks

Examples

PT for MPI-2

Overview

Input-output operations

Task groups

Dynamic (obj)

Tasks | Task groups | Dynamic (obj)

Dynamic data structures (based on objects)

This group is named "ObjDyn" in the PascalABC.NET version of Programming Taskbook.

Starting from the 4.15 version, Programming Taskbook contains two variants of this group. The new one, named GCDyn, does not require to release resources used by the Node object because it is assumed that the Garbage Collector is used for this purpose. This difference occurs only for the tasks with the following numbers: 5–7, 12–13, 18–20, 27–28, 41–43, 65, 72–73, 80.

All numbers mentioned in tasks of this group are integers. All objects are of Node type; this class is defined in Programming Taskbook. In the tasks if this group the Data, Next, and Prev properties of the Node class are used. Therefore one can assume that the Node class contains the following public members:

[PascalABC.NET]

// Constructors:
constructor Create;
constructor Create(aData: integer);
constructor Create(aData: integer; aNext: Node);
constructor Create(aData: integer; aNext, aPrev: Node);
// Properties (available to read and write):
property Data: integer;
property Next: Node;
property Prev: Node;
// Method that releases resources used by the Node object:
procedure Dispose;

[C#]

// Constructors:
public Node();
public Node(int aData);
public Node(int aData, Node aNext);
public Node(int aData, Node aNext, Node aPrev);
// Properties (available to read and write):
public int Data;
public Node Next;
public Node Prev;
// Method that releases resources used by the Node object:
public void Dispose();

[VB.NET]

' Constructors:
Public Sub New()
Public Sub New(aData As Integer)
Public Sub New(aData As Integer, aNext As Node)
Public Sub New(aData As Integer, aNext As Node, _
aPrev As Node)
' Properties (available to read and write):
Public Property Data() As Integer
Public Property Next() As Node
Public Property Prev() As Node
' Method that releases resources used by the Node object:
Public Sub Dispose() Implements IDisposable.Dispose

[F#]

// Constructors:
public new()
public new(aData: int)
public new(aData: int, aNext: Node)
public new(aData: int, aNext: Node, aPrev: Node)
// Properties (available to read and write):
public Data: int
public Next: Node
public Prev: Node
// Method that releases resources used by the Node object:
public Dispose()

[Java]

// Constructors:
Node();
Node(int aData);
Node(int aData, Node aNext);
Node(int aData, Node aNext, Node aPrev);
// Accessors to properties:
int getData();
void setData(int value);
Node getNext();
void setNext(Node value);
Node getPrev();
void setPrev(Node value);
// Method that releases resources used by the Node object:
void dispose();

[Python]

# Constructor:
Node(data = 0, next = None, prev = None)
# Properties (available to read and write):
Data
Next
Prev
# Method that releases resources used by the Node object:
dispose()

[Ruby]

# Constructors:
Node.new()
Node.new(data)
Node.new(data, next)
Node.new(data, next, prev)
# Properties (available to read and write):
data
next
prev
# Method that releases resources used by the Node object:
dispose()

[Julia]

# Constructors:
node()
node(data::Integer)
node(data::Integer, next::Node)
node(data::Integer, next::Node, prev::Node)
# Accessors to properties (the ! symbol means changing the property):
data(node::Node)
data!(node::Node, value::Integer)
next(node::Node)
next!(node::Node, value::Node)
prev(node::Node)
prev!(node::Node, value::Node)
# Function that releases resources used by the Node object:
dispose!(node::Node)

In the introductory tasks and in the tasks devoted to stacks and queues the Prev property of the Node class is not used. In the tasks devoted to lists all properties (Data, Next, Prev) of the Node class are used.

All these languages use the reference object model; that is, any object variable is a reference to the object instance. Therefore, the expression "output the reference to a node" means that you should output the value of a corresponding variable of the Node type.

The order number of the first node of a list is assumed to be equal to 1.

Dynamic data structures: nodes and chains of nodes

Dynamic1. An object A₁ 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₂ that follows the given object.

Dynamic2°. An object A₁ 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

In these tasks a stack structure is implemented by a chain of linked components (nodes) that are instances of the Node class. The Next property of the last node equals null. The first node is said to be a top of the stack. The stack data can be accessed by means of the object variable (of the Node class) that refers to the top of the stack; if the stack is empty then this variable equals null. The value of the Data property of a stack component is considered as the value of this component.

Dynamic3°. An integer D and the top A₁ of a nonempty stack are given. Push a component with the value D onto the stack and output a reference A₂ 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₁ of a nonempty stack is given. Pop the top component off the stack and output its value D and a reference A₂ to a new top of the stack. If the stack will be empty after popping the component then A₂ 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₁ 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₂ 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₁ of a stack is given (if the stack is empty then A₁ 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₁ and A₂ 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₁ and A₂ 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₁ 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₁ of a stack is given (if the stack is empty then A₁ 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₁ 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₁ 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

In these tasks a queue structure is implemented by a chain of linked components (nodes) that are instances of the Node class. The Next property of the last node equals null. The first node is said to be a head of the queue; the head is located at the front of the queue. The last node is said to be a tail of the queue; the tail is located at the end of the queue. It is convenient to store not only a reference to the queue head but also a reference to the queue tail because it accelerates adding a new component to the end of a queue. If a queue is empty then these references equal null. The value of the Data property of a queue component is considered as the value of this component.

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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ refer to the head and tail of the first one, references A₃ and A₄ 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₁ and A₂ refer to the head and tail of the first one, references A₃ and A₄ 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₁ and A₂ refer to the head and tail of the first one, references A₃ and A₄ 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₁ and A₂ refer to the head and tail of the first one, references A₃ and A₄ 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₁ and A₂ refer to the head and tail of the first one, references A₃ and A₄ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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

In these tasks a doubly linked list structure is implemented by a chain of components (nodes) of the Node class; these nodes are linked with both the next node and the previous one. The Next property of the last node and the Prev property of the first node are equal to null. Though storing of a reference to some list node is sufficient to provide access to any list node, it is convenient to store three references (to the first, last, and current list node) because they accelerate list operations. If a list is empty then these references equal null. The value of the Data property of a list component is considered as the value of this component.

Dynamic29. An object A₂ 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₁ and A₃ to the previous and next object.

Dynamic30°. A reference A₁ 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₂ to the last component of the resulting chain.

Dynamic31. A reference A₀ 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₁ and A₂ to the first and last component respectively.

Dynamic32. Two integers D₁, D₂ and a reference A₀ to one of the components of a nonempty doubly linked list are given. Insert a new component with the value D₁ at the beginning of the list; insert a new component with the value D₂ at the end of the list. Output references to the first and last list component.

Dynamic33. An integer D and a reference A₀ 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₀ 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₁ and A₂ 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₁ and A₂ 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₁ 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₁ 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₁ 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₁ 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₀ 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₁ 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₁ 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₀ 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₀ 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₀ 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₀ 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₁ 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₁ 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₁ and A₂ refer to the first and last component of the first list, a reference A₀ 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₁ and A₂ refer to the first and last component of the first list, a reference A₀ 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₁ 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₁ and A₂ 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₃ and A₄ to two middle components of the given list; the object A₃ must be contained in the first resulting circular list, the object A₄ must be contained in the second one. Do not create new instances of the Node class.

Dynamic57. An integer K (> 0) and references A₁ and A₂ 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₁ and A₂ 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₁, A₂, and A₃ 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₁, A₂, and A₃ 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₁, A₂, and A₃ 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₁, A₂, and A₃ 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₁, A₂, and A₃ 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₁, A₂, and A₃ 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₁, A₂, and A₃ 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₁, A₂, and A₃ to the first, last, and current component of a nonempty doubly linked list are given. Include a procedure Split(L₁, L₂) as a class method in the IntList class (see Dynamic59); this procedure moves some components of a list L₁ into a new list L₂: components between the current and last component inclusively must be moved (as a result, the list L₁ will be split into two parts; the first part may be empty). An object L₁ of IntList type is an input parameter, an object L₂ 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₁, L₂) as a class method in the IntList class (see Dynamic59); this procedure inserts all components of a list L₁ (in the same order) at the end of a list L₂; as a result, the list L₁ will be empty. The first component being inserted becomes the current component of the list L₂. Objects L₁ and L₂ 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₁, L₂) as a class method in the IntList class (see Dynamic59); this procedure inserts all components of a list L₁ (in the same order) before the current component of a list L₂; as a result, the list L₁ will be empty. The first component being inserted becomes the current component of the list L₂. Objects L₁ and L₂ 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₁, L₂) as a class method in the IntList class (see Dynamic59); this procedure removes the current component from a list L₁ and inserts this component after the current component of a list L₂. If the next component of the list L₁ 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₂. Objects L₁ and L₂ 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

In these tasks a doubly linked list structure is implemented by a circular doubly linked chain of nodes with an additional barrier node (the barrier component of a list). This barrier node is linked with the first and last "true" list component by the Next and Prev property respectively; similarly, the first/last "true" list component is linked with the barrier node by the Prev/Next property respectively. Such a list implementation allows to store only two references (to the barrier and current list component) for list processing. The Data property of the barrier component may be of any value; for definiteness the value of this property is considered to equal zero. Both some "true" list component and the barrier component may be the current component. An empty list in this implementation is represented as a single barrier node linked with itself; the current component of an empty list is always the barrier component.

Dynamic70°. References A₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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₁ and A₂ 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.

Last revised:
01.01.2024