Lecture
Until now we have considered only static program objects. However, using only static objects in programming can cause certain difficulties, especially in terms of obtaining an efficient machine program. The fact is that sometimes we do not know in advance not only the size of the value of a given program object, but also whether this object will exist at all or not. Such program objects, which arise during the execution of the program itself or whose value size is determined during program execution, are called dynamic objects.
Dynamic data structures have 2 features:
To link the elements of dynamic structures together, in addition to information fields, the elements also include pointer fields (fig. 3.1) (links to other elements of the structure).
P1 and P2 are pointers containing the addresses of the elements they are linked to. The pointers contain the slot number.
The most common dynamic structures are linked lists. From the point of view of logical representation, a distinction is made between linear and non-linear lists.
In linear lists, the links are strictly ordered: the pointer of the previous element contains the address of the next element, or vice versa.
Linear lists include singly linked and doubly linked lists. Non-linear lists include multiply linked lists.
A list element generally consists of a record field and one or more pointers.
An element of a singly linked list contains two fields (fig. 3.2): an information field (INFO) and a pointer field (PTR).
The distinctive feature of the pointer is that it only gives the address of the next element of the list. The pointer field of the last element in the list is empty (NIL). LST is a pointer to the beginning of the list. The list can be empty, in which case LST will equal NIL.
Access to a list element is only possible from its beginning, that is, there is no backward link in this list.
A circular singly linked list is obtained from an ordinary singly linked list by assigning the pointer of the last element of the list the value of the pointer to the beginning of the list (fig. 3.3).
Basic operations performed on singly linked lists
We need to insert an element with information field D at the beginning of the singly linked list. To do this, we need to generate an empty element (P=GetNode). Assign the value D to the information field of this element (INFO(P)=D), assign the value of the pointer to the beginning of the list to the pointer value of this element (Ptr(P) = Lst), and assign the value of pointer P to the value of the pointer to the beginning of the list (Lst = P).
Implementation in Pascal:
type
PNode = ^TNode;
TNode = record
Info: Integer; {type of the list elements - can be any}
Next: PNode;
end;
var
Lst: PNode; {pointer to the beginning of the list}
P: PNode;
Insertion at the beginning
New(P); {create a new element}
P^.Info:=D;
P^.Next:=Lst; {P points to the beginning of the list, but Lst does not point to P - new beginning}
Lst:=P; {Lst points to the new beginning of the list}
We need to delete the first element of the list, but remember the information contained in the Info field of this element. To do this, we introduce a pointer P, which will point to the element being deleted (P = Lst). We store the value of the Info field of the deleted element in the variable X (X=Info(P)). We assign the value of the pointer to the element following the deleted one to the pointer to the beginning of the list (Lst = Ptr(P)). We delete the element (FreeNode(P)).
Implementation in Pascal:
Deletion from the beginning
P:=Lst;
X:=P^.Info;
Lst:=P^.Next;
Dispose(P); {Removes the element from dynamic memory}
Using unidirectional lists when solving a number of problems can cause certain difficulties. The fact is that a unidirectional list can only be traversed in one direction, from the head node to the last node of the list. Meanwhile, it is often necessary to perform some processing of the elements preceding an element with a given property. However, after finding the element with this property in a singly linked list, we have no way to get sufficiently convenient and fast access to the preceding elements - to achieve this goal, the algorithm would have to be made more complex, which is inconvenient and inefficient.
To eliminate this inconvenience, let us add one more field to each node of the list, whose value will be a reference to the previous node of the list. A dynamic structure consisting of elements of this type is called a bidirectional or doubly linked list.
A doubly linked list is characterized by the fact that any element has two pointers. One points to the previous element (backward), the other points to the next element (forward) (fig. 3.4).
In fact, a doubly linked list is two singly linked lists with the same elements, written in opposite order.
In programming, doubly linked lists are often generalized as follows: the value of the Rptr field of the last node is taken to be a reference to the head node, and the value of the Lptr field of the head node - a reference to the last node. The list closes into a kind of ring: moving along the references, one can go from the last node to the head node and vice versa.
O
perations on doubly linked lists:
- creation of a list element;
- searching for an element in the list;
- insertion of an element at a specified place in the list;
- deletion of a given element from the list.
Any singly linked list can be viewed as a stack. However, compared to a stack implemented as a one-dimensional array, a list has the advantage that its size is not fixed in advance.
Stack operations applicable to lists
1). To add an element to the stack, in the algorithm the pointer Lst must be replaced with the pointer Stack (operation Push(S, X)).
P = GetNode
Info(P) = X
Ptr(P) = Stack
Stack = P
If Stack = Nil then Print “Stack is empty”
Stop
P = Stack
X = Info(P)
Stack = Ptr(P)
FreeNode(P)
Implementation in Pascal:
Stack
Instead of the pointer Lst, the pointer Stack is used
Procedure Push (S, X)
procedure Push(var Stack: PNode; X: Integer);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=Stack;
Stack:=P;
end;
Checking for emptiness (Empty)
function Empty(Stack: PNode): Boolean;
begin
If Stack = nil then Empty:=True Else Empty:=False;
end;
Procedure Pop
procedure Pop(var X: Integer; var Stack: PNode);
var
P: PNode;
begin
P:=Stack;
X:=P^.Info;
Stack:=P^.Next;
Dispose(P);
end;
Queue operations applicable to lists.
We take the pointer to the beginning of the list as the pointer to the beginning of the queue F, and the pointer R, which points to the last element of the list, as the pointer to the end of the queue.
The dequeue operation must proceed from the beginning of the queue.
P = F
F = Ptr(P)
X = Info(P)
FreeNode(P)
If F = Nil then Print “Queue is empty”
Stop
The queue insertion operation must be performed at its end.
P = GetNode
Info(P) = X
Ptr(P) = Nil
Ptr(R)= P
R = P
Implementation in Pascal:
procedure Remove(var X: Integer; Fr: PNode);
var
P: PNode;
begin
New(P);
P:=Fr;
X:=P^.Info;
Fr:=P^.Next;
Dispose(P);
end;
function Empty(Fr: PNode): Boolean;
begin
If Fr = nil then Empty:=True Else Empty:=False;
end;
procedure Insert(X: Insert; var Re: PNode);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=nil;
Re^.Next:=P;
end;
For more efficient use of computer memory (to eliminate garbage, i.e. unused elements) when working with lists, a free list is created, having the same field format as the functional lists.
If the functional lists have different formats, then a free list must be created for each functional list.
The number of elements in the free list must be determined by the task the program is solving. As a rule, the free list is created in machine memory as a stack. In this case, creating (GetNode) a new element is equivalent to retrieving an element from the free stack, and the FreeNode operation - to adding a freed element to the free stack.
Suppose we need to create an empty list of the stack type (fig. 3.6) with a list-start pointer AVAIL. Let us develop procedures that will allow us to create an empty list element and free an element from the list.
Let us develop a procedure that will create an empty list element with the pointer P.
To implement the GetNode operation, the pointer of the generated element must be assigned the value of the pointer to the beginning of the free list, and the start pointer moved to the next element.
P = Avail
Avail = Ptr(Avail)
Before this, it is necessary to check whether there are elements in the list. Emptiness of the free list (Avail = Nil) is equivalent to overflow of the functional list.
If Avail = Nil then Print “Overflow” Stop
Else
P = Avail
Avail = Ptr(Avail)
Endif
When an element Nod(P) is freed from the functional list by the FreeNode(P) operation, it is placed into the free list.
Ptr(P) = Avail
Avail = P
The standard operations for returning a freed list element to the pool of free elements are not always effective when nonlinear multiply linked lists are used.
The first method of reuse is the counter method. A counter field is inserted into each element of the multiply linked list, which counts the number of references to that element. When the element's counter reaches zero, and the element's pointer fields are in the nil state, this element can be returned to the pool of free elements.
The second method is the garbage collection method (marker method). If a link is established with some element, the element’s single-bit field (marker) is set to “1”, otherwise - to “0”. On an overflow signal, elements whose marker is set to zero are searched for, i.e. a garbage collection program is started, which scans the entire allocated memory and returns to the list of free elements all elements not marked by the marker.
Traversal of a singly linked list can only be done sequentially, starting from the head (from the beginning) of the list. If it is necessary to view the previous element, one must return to the beginning of the list again. This is a drawback of singly linked lists compared to static structures such as arrays. The list structure shows its advantages when the number of elements in the list is large, and an insertion or deletion needs to be performed inside the list.
Example:
It is necessary to insert an element X into an existing array between the 5th and 6th elements.
To perform this operation in the array, all elements starting from X6 must be “shifted down” - their indices increased by one. As a result of the insertion, we get the following array (fig. 3.7, 3.8):
This procedure can take a very significant amount of time. In contrast, in a linked list the insertion operation consists of changing the value of 2 pointers and generating a free element. Moreover, the time spent performing this operation is constant and does not depend on the number of elements in the list.
We determine the element after which the element must be inserted into the list. Insertion is performed using the procedure InsAfter(Q, X), and deletion - DelAfter(Q, X).
In this case, the working pointer P will point to the element after which the insertion or deletion must be performed (fig. 29).
Example:
Suppose it is necessary to insert a new element with information field X after the element pointed to by the working pointer P.
For this:
1) A new element must be generated.
Q = GetNode
2) Assign the value X to the information field of this element.
Info(Q) = X
3) Insert the obtained element.
Ptr(Q) = Ptr(P)
Ptr(P) = Q
This is the InsAfter(Q, X) procedure.
Suppose it is necessary to delete the list element that follows the element pointed to by the working pointer P.
For this:
Q = Ptr(P)
2) We save the value of the information field of the element being deleted into the variable X.
X = Info(Q)
3) We change the value of the pointer to the element being deleted to the value of the pointer to the next element and perform the deletion.
Ptr(P) = Ptr(Q)
FreeNode(Q)
This is the DelAfter(P, X) procedure.
In the Pascal language, the above-described procedures will look as follows:
procedure InsAfter(var Q: PNode; X: Integer);
var
Q: PNode;
begin
New(Q);
Q^.Info:=X;
Q^.Next:=P^.Next;
P^.Next:=Q;
procedure DelAfter(var Q: PNode; var X: Integer);
var
Q: PNode;
begin
Q:=P^.Next;
P^.Next:=Q^.Next;
X:=Q^.Info;
Dispose(Q);
end;
Problem 1.
It is required to traverse the list and delete elements whose information field equals 4.
Let P denote the working pointer; at the beginning of the procedure P = Lst. We also introduce a pointer Q, which lags one element behind P. When the pointer P finds the element, it will be deleted relative to the pointer Q as the following element.
Q = Nil
P = Lst
While P <> Nil do
If Info(P) = 4 then
If Q = Nil then
Pop(Lst)
FreeNode(P)
P = Lst
Else
DelAfter(Q, X)
EndIf
Else
Q = P
P = Ptr(P)
EndIf
EndWhile
Problem 2.
A list ordered in ascending order of the Info field is given. It is necessary to insert into this list an element with the value X without violating the order of the list.
Let X = 16. Initial condition: Q = Nil, P = Lst. The insertion of the element must occur between the 3rd and 4th elements (fig. 3.10).
Q =Nil
P = Lst
while (P <> Nil) and (X > Info(P)) do
Q = P
P = Ptr(P)
EndWhile
if Q = Nil then
Push(Lst, X)
EndIf
InsAfter(Q, X)
Implementation of the examples in Pascal:
Problem 1:
Q:=nil;
P:=Lst;
While P <> nil do
If P^.Info = 4 then
begin
If Q = nil then
begin
Pop(Lst);
P:=Lst;
end
Else Delafter(Q,X);
End;
Else
begin
Q:=P;
P:=P^.Next;
end;
end;
Problem 2:
Q:=nil;
P:=Lst;
While (P <> nil) and (X > P^.Info) do
begin
Q:=P;
P:=P^.Next;
end;
{Insertion happens at this point}
If Q = nil then Push(Lst, X);
InsAfter(Q, X);
End;
To create a list with a header, an additional element is introduced at the beginning of the list, which can contain information about the list (fig. 3.11).
The list header often stores a dynamic variable containing the number of elements in the list (not counting the header itself).
If the list is empty, then only the list header remains (fig. 3.12).
It is also convenient to store the value of the pointer to the end of the list in the information field of the header. Then, if the list is used as a queue, Fr = Lst, and Re = Info(Lst).
The information field of the header can be used to store the working pointer when traversing the list, P = Info(Lst). That is, the header is a descriptor of the data structure.
A doubly linked list can be a nonlinear data structure if the second pointers set an arbitrary order of the elements (fig. 3.13).
LST1 - a pointer to the beginning of the 1st list (oriented by the pointer P1). It is linear and consists of 5 elements.
The 2nd list is formed from these same elements, but in an arbitrary sequence. The beginning of the 2nd list is the 3rd element, and the end is the 2nd element.
In the general case, an element of a list structure can contain any number of pointers, that is, it can point to any number of elements.
Three distinguishing features of a nonlinear structure can be identified:
1) Any element of the structure can reference any number of other elements of the structure, that is, it can have any number of pointer fields.
2) A given element of the structure can be referenced by any number of other elements of this structure.
3) References can have a weight, that is, a hierarchy of references is implied.
Suppose there is a discrete system whose state graph has nodes that are states, and edges that are transitions from state to state (fig. 3.14).
The input signal to the system is X. The response to the input signal is the generation of the output signal Y and the transition to the corresponding state.
The state graph of a discrete system can be represented as a doubly linked nonlinear list. In this case, information about the states of the system and the edges must be recorded in the information fields. The pointers of the elements must form the logical edges of the system (fig. 3.15).
To implement the above:
1) a list displaying the states of the system (1, 2, 3) must be created;
2) lists displaying the transitions along the edges from the corresponding states must be created.
In the general case, implementing a multiply linked structure results in a network.
Review questions
Comments