Dynamic Memory Structures and Linked Lists in Programming
7.1. Objectives
Static structures cannot be resized during program execution. Changing the arrangement of elements within a static structure is expensive. For example, the positions of elements within an array cannot be resized. At design time, we do not know exactly how much memory we need or how to organize it.
Solution: Define and organize this memory at runtime using dynamic memory structures.
Dynamic memory management is done through pointers.
Dynamic memory: Memory from which you can reserve space at runtime.
Dynamic memory structures: A collection of elements (called nodes of the structure) that are linked together.
Dynamic Variables: Positions of reserved memory at runtime.
Definition: A variable used to indicate the memory location of another variable.
Semantics: Declares a data type (ID) which is a pointer to another data type (Type).
7.2. Pointers
7.2.1. Pointer Operations
New: A procedure that reserves space for dynamic memory.
Syntax: new (Variable_puntero);
Semantics: Reserve memory space, and the pointer variable passed as a parameter is left pointing to that space.
Dispose: A procedure that frees dynamic memory.
Syntax: dispose (Variable_puntero);
Semantics: Releases the memory space pointed to by the pointer variable passed as a parameter.
Data access: Operator ^ (circumflex) (also called dereferencing operator)
^ From the reference operator is the type of data referenced by the pointer.
It is not always necessary to allocate memory required to use a pointer.
Getting the memory address of a variable: Operator @ (reference)
NIL (null pointer) is a constant pointer type.
A NIL pointer indicates that it does not point to any memory location.
Watch out for positions that are left to target; we may lose memory if not freed before.
It only allows assignment operations (:=) and comparison with the relational operators (= and <>).
The operands must be pointers to variables of the same type or NIL.
Procedures and Functions
Parameters may be passed by value and by reference to the subprogram.
A pointer may be returned as a result of a function.
Although f is a function that returns a pointer to a record, the following is not allowed:
f (actual parameters) ^. name; X
varPuntero: = f (actual parameters), V
7.2.2. Observations
Declaring a pointer type variable is not always enough to use it.
To create information dynamically, call the new procedure.
After calling new, the value pointed to by the pointer is undefined. To define it, it is necessary to assign a value.
Variable_puntero? Variable_puntero ^
It is very convenient to free the memory space when not using it. If you have more than one pointer, use dispose.
7.3. Linked Lists
A list consists of a collection of elements called nodes, such that each stores two values:
- The list element: All are of the same type of data (also called field of information).
- A pointer indicating the position of the node containing the next item in the list.
The connection is made through the pointer associated with each node.
We need the reference of the node that contains the first element of the list.
The linked list is a recursive structure.
7.3.1. Simple Linked Lists
Dynamic structure simpler: you only have a link.
A node is represented by a record with two fields: one for data and the other is a pointer to another node.
TYPE
TDate = String [25] (type of the elements of the list)
tlist = ^ tNodoLista;
tNodoLista = RECORD
Name: TDate;
sig: tlist) (Recursive Structure
END;
VAR
Paux, aux, first, previous list: TList;
Create an empty list:
list: = NIL;
Check if a list is empty:
IF (list = NIL) THEN
empty list ()
ELSE
(there are one or more elements) (Examples 10a, 10b)
End of a list:
IF (lista.sig = NIL) THEN
(last item in the list)
7.3.2. Doubly linked lists
Maintains links in both directions.
Need two pointers:
- Ant: Points to the previous node.
- Sig: Points to the next node.
Disadvantage: Operations such as insertion and deletion are more complex (need more auxiliary pointers).
Advantage: Measures such as ordering a list or getting a reverse list are easy to perform.
7.4. Other dynamic structures
Stacks: A list particularized to the case in which only elements are inserted and removed by one end: List LIFO (LastInFirstOut).
Queues: A list particularized to the case in which elements are inserted at one end and removed by the other: List FIFO (FirstInFirstOut).
7.5. Observations on dynamic structures
The concept of a list can be implemented in a static (array partially filled) structure.
The dynamic list has disadvantages compared to the array: access complexity O(n) vs. O(1).
Be especially careful not to lose the pointer pointing to the top of the list; we would lose the entire list if we have not pointed to it by a helper.
When deleting items from a list, we must not forget to free the node to delete (not just bypass it).