Solutions of tasks connected with processing of dynamic data structures (including adding a node, removing a node, processing of doubly linked and circular dynamic structures) are described on this page.

Analyzing an existing dynamic structure: Dynamic2

In the "Dynamic" task group for .NET we should use two new kinds of data items: objects of Node type and dynamic structures implemented by linked chains of objects of Node type. The Node class is defined in the Programming Taskbook library, namely, in the pt4net.dll file.

Let's get acquainted with features of the new kinds of data items by solving the following task:

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.

Creating a template and acquaintance with the task

To create a template of the required task one should use PT4Load tool. The solution of the task should be entered in the Solve procedure, which is defined in the Dynamic2 file (this file is created by PT4Load tool, it has .cs extension for C# and .vb extension for VB.NET):

[C#]

public static void Solve()
{
    Task("Dynamic2");
}

[VB.NET]

Sub Solve()
    Task("Dynamic2")
End Sub

When the program is launched you will see the Programming Taskbook window. Here is the screenshot of the window for the C# language:

This window contains new kinds of input data: references to objects of the Node class and dynamic structures.

A dynamic structure is displayed in two screen lines: the first line contains names of Node variables that refer to components (nodes) of the structure, the second one contains values of nodes (that is, their Data properties). All data are displayed with light-cyan color to distinguish them from standard input-output data and comments. Here is a sample of the dynamic structure data for C# language:

 A₁
 97 - 94 - 10 - 14 - 25 >null

This structure consists of 5 nodes. The Data property of the first node equals 97; the first node is linked by the Next property with the second node whose Data property equals 94, and so on. The Next property of the fifth node equals null, so this node is the last chain node:

The dynamic structure for VB.NET language differs only by the name of the empty reference:

 A₁
 97 - 94 - 10 - 14 - 25 >Noth

The "Noth" text means the "Nothing" keyword that is used in VB.NET to denote empty reference (as the "null" keyword in C#).

All dynamic structures displayed in the input data panel were created when the task was initialized, and their nodes are stored in the dynamic memory (named the heap). To access the node we need to know its address. Therefore a Node object that refers the first node of the input dynamic structure is also given as an input data item.

This object has name A₁ and is displayed in the input data panel as follows:

A₁ = Node

The "P₁=" text is a comment and has light-grey color. The "Node" text means that this data item is a non-empty instance of the Node class that refers some node of input or output dynamic structure (an empty instance is denoted as "null" in C# and "Noth" in VB.NET). All instances of the Node class should be input by the GetNode function.

After creating some dynamic structure the student program must output one or more Node objects of this structure to Programming Taskbook (using the Put procedure). After receiving these objects Programming Taskbook can check correctness of the task solution.

Start of solving

Let's return to the Dynamic2 task. This task does not require to create a new data structure or to change the existing one; it is sufficient to analyse the given structure, that is, to output values of its nodes, to find its length, and output a reference to the last node of the structure.

The algorithm shown below outputs all required data except the reference to the last node:

[C#]

public static void Solve()
{
    Task("Dynamic2");
    int n = 0;
    Node a1 = GetNode();
    while (a1 != null)
    {
        Put(a1.Data);
        n++;
        a1 = a1.Next;
    }
    Put(n);
}

[VB.NET]

Sub Solve()
    Task("Dynamic2")
    Dim n As Integer = 0
    Dim a1 As Node = GetNode()
    Do While Not a1 Is Nothing
        Put(a1.Data)
        n += 1
        a1 = a1.Next
    Loop
    Put(n)
End Sub

When the program will be started we shall see that all numeric data are output correctly. But the reference to the last node is not output, therefore we shall see the following error message: "Some data are not output".

Change the last statement as follows:

[C#]

    Put(n, a1);

[VB.NET]

    Put(n, a1)

Now all required data will be output. But a resulting value of the reference will be equal to "null" ("Noth" in VB.NET) because the p1 variable contains empty reference when the "while" loop was finished. Therefore we shall see the error message "Wrong solution".

Correct solution

To get a correct result we should use an additional instance of the Node class. This variable named p2 will store a reference to node that precedes the node refered by the p1 variable. As a result the p2 variable will reference the last node when the loop will be finished:

[C#]

public static void Solve()
{
    Task("Dynamic2");
    int n = 0;
    Node a1 = GetNode(), a2 = null;
    while (a1 != null)
    {
        Put(a1.Data);
        n++;
        a2 = a1;
        a1 = a1.Next;
    }
    Put(n, a2);
}

[VB.NET]

Sub Solve()
    Task("Dynamic2")
    Dim n As Integer = 0
    Dim a1 As Node = GetNode(), a2 As Node = Nothing
    Do While Not a1 Is Nothing
        Put(a1.Data)
        n += 1
        a2 = a1
        a1 = a1.Next
    Loop
    Put(n, a2)
End Sub

After 3 test runnings we shall receive a message that the task is solved.

Adding a node to a dynamic structure: Dynamic3

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.

Acquaintance with the task

After launching the program we will see dots that mark the first node of resulting stack:

Such dots mark nodes that must be created by student's program (unlike the other nodes that are created by Programming Taskbook).

Start of solving

In the first version of solution we shall output a pointer to the top of the given stack without any changing of this stack:

[C#]

public static void Solve()
{
    Task("Dynamic3");
    int d = GetInt();
    Node a1 = GetNode();
    Put(a1);
}

[VB.NET]

Sub Solve()
    Task("Dynamic3")
    Dim d As Integer = GetInt()
    Dim a1 As Node = GetNode()
    Put(a1)
End Sub

Of course this solution is not correct, and after launching the program the resulting stack will be displayed as follows (provided that the input stack contains 4 nodes with values 12, 24, 74, and 49):

 A₂
(12)-(24)-(74)-(49)>null

The dynamic structure for VB.NET language will differ only by the name of the empty reference: "Noth" instead of"null".

The parentheses mark nodes that are created by Programming Taskbook but are located at wrong positions of the resulting dynamic structure. Indeed, in our case the node with value 12 must be the second node in the resulting stack, and so on.

Correct solution

To get a correct algorithm of the Dynamic3 task we should create a new instance of the Node class (named a2) and assign required values to the Data and Next properties of this instance. In particular, the Next property must link the a2 instance with the top a1 of the given stack:

[C#]

public static void Solve()
{
    Task("Dynamic3");
    int d = GetInt();
    Node a1 = GetNode(), a2 = new Node(d, a1);
    Put(a2);
}

[VB.NET]

Sub Solve()
    Task("Dynamic3")
    Dim d As Integer = GetInt()
    Dim a1 As Node = GetNode(), a2 As New Node(d, a1)
    Put(a2)
End Sub

After 5 test runnings we shall receive a message that the task is solved.

Remark. We can solve this task using no variables:

[C#]

    Put(new Node(GetInt(), GetNode()));

[VB.NET]

    Put(New Node(GetInt(), GetNode()))

Removing a node from a dynamic data structure: Dynamic5

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.

Acquaintance with the task

When solving tasks devoted to removing of nodes one should not only "disconnect" the required nodes from the given dynamic structure but also completely destroy them by the Dispose method of the Node class. All such nodes of given dynamic structure are marked by color that is more dark than an "usual" nodes (look at the node with the value 25 on the picture):

As is known that in the .NET CLS (.NET Commom Language Runtime) the garbage collector automatically releases the memory allocated to an object when that object is no longer used. But the garbage collector has no knowledge of unmanaged resources such as window handles, or open files and streams. The Node objects also use unmanaged resources, therefore the Node class contains the Dispose method that should be called explicitly for all Node objects that should be removed from the given dynamic structure. All such nodes are marked by color that is more dark than an "usual" nodes (see the node with the value 25 on the picture):

Start of solving

We begin with the wrong algorithm that does not release unmanaged resources allocated for the first node of the given stack:

[C#]

public static void Solve()
{
    Task("Dynamic5");
    Node a1 = GetNode();
    Put(a1.Data, a1.Next);
}

[VB.NET]

Sub Solve()
    Task("Dynamic5")
    Dim a1 As Node = GetNode()
    Put(a1.Data, a1.Next)
End Sub

Although all output results will coincide with the control ones (that is, the "Example of right solution" and "Results obtained" tabs will be contain identical data) the status bar will display the following error message "The Dispose method is not called for a Node object", and the component that must be removed will be marked by red color in the input data panel.

Correct solution

To get a correct solution it is enough to add the Dispose method call at the end of the program:

[C#]

    a1.Dispose();

[VB.NET]

    a1.Dispose()

After 5 test runnings we shall receive a message that the task is solved.

Doubly linked dynamic structures: Dynamic30

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.

Acquaintance with the task

After launching the program we will see that the input and output dynamic structures are displayed in different manner. The input chain of nodes will be displayed as all other dynamic structures in the previous tasks, for example:

 A₁
 35 - 11 - 36 - 39 - 56 >null

The output chain of nodes will be displayed as follows:

                          A₂
null< 35 = 11 = 36 = 39 = 56 >null

Note that the "null<" precedes the first node and all nodes are linked by the "=" character (instead of the "–" one). It means that the output dynamic structure is doubly linked one:

Task solution

To transform the initial single linked structure into the doubly linked one it is enough to assign a required value to the Prev property of each node:

[C#]

public static void Solve()
{
    Task("Dynamic30");
    Node a1 = GetNode(), a2 = null;
    while (a1 != null)
    {
        a1.Prev = a2;
        a2 = a1;
        a1 = a1.Next;
    }
    Put(a2);
}

[VB.NET]

Sub Solve()
    Task("Dynamic30")
    Dim a1 As Node = GetNode(), a2 As Node = Nothing
    Do While Not a1 Is Nothing
        a1.Prev = a2
        a2 = a1
        a1 = a1.Next
    Loop
    Put(a2)
End Sub

After 5 test runnings we shall receive a message that the task is solved.

Circular dynamic structures: Dynamic55

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.

Acquaintance with the task

After launching the program we will see that the input and output dynamic structures are displayed in a slightly different manner, for example:

      A₁
null< 19 = 94 = 51 = 41 = 55 >null

                          A₂
 << = 19 = 94 = 51 = 41 = 55 = >>

The "<<=" and "=>>" text means that the output chain of nodes is a circular double linked one:

Task solution

To solve the Dynamic55 task one should find the last node and link it with the first one:

[C#]

public static void Solve()
{
    Task("Dynamic55");
    Node a1 = GetNode(), a2 = a1;
    while (a2.Next != null)
        a2 = a2.Next;
    a2.Next = a1;
    Put(a2);
}

[VB.NET]

Sub Solve()
    Task("Dynamic55")
    Dim a1 As Node = GetNode(), a2 As Node = a1
    Do While Not a2.Next Is Nothing
        a2 = a2.Next
    Loop
    a2.Next = a1
    Put(a2)
End Sub

In this program we "forgot" to link the first node with the last one by the Prev property of the first node. Therefore when the program will be started we will see the "–" character after the last node of the output list, for example:

                A₂
null< 38 = 24 = 91 - >>

To get a correct algorithm it is enough to add the following statement before output of the p2 variable:

[C#]

    a1.Prev = a2;

[VB.NET]

    a1.Prev = a2

After 3 test runnings we shall receive a message that the task is solved.

Last revised:
04.06.2011