Dynamic data structures are essential for creating flexible and efficient programs that can handle varying amounts of data. In this section, we will explore the concept of dynamic data structures in ALGOL, including their definition, types, and practical implementation.
What are Dynamic Data Structures?
Dynamic data structures are data structures that can grow and shrink at runtime, allowing for efficient memory usage and flexibility in handling data. Unlike static data structures, which have a fixed size, dynamic data structures can adapt to the needs of the program.
Key Concepts:
- Dynamic Allocation: Memory is allocated at runtime.
- Flexibility: Can grow and shrink as needed.
- Efficiency: Optimizes memory usage.
Types of Dynamic Data Structures
In ALGOL, the most common dynamic data structures include:
- Linked Lists
- Stacks
- Queues
- Trees
Linked Lists
A linked list is a sequence of elements, where each element points to the next one. It allows for efficient insertion and deletion of elements.
Example:
begin
integer node;
record nodeType (integer value; ref nodeType next);
ref nodeType head, temp;
head := new nodeType;
head.value := 10;
head.next := new nodeType;
head.next.value := 20;
head.next.next := nil;
temp := head;
while temp != nil do
begin
print(temp.value);
temp := temp.next;
end;
end;Stacks
A stack is a LIFO (Last In, First Out) data structure. Elements are added and removed from the top.
Example:
begin
integer stackSize, top;
stackSize := 10;
top := 0;
array stack[1:stackSize] of integer;
procedure push(integer value);
begin
if top < stackSize then
begin
top := top + 1;
stack[top] := value;
end
else
print("Stack Overflow");
end;
procedure pop();
begin
if top > 0 then
begin
print(stack[top]);
top := top - 1;
end
else
print("Stack Underflow");
end;
push(10);
push(20);
pop();
pop();
pop();
end;Queues
A queue is a FIFO (First In, First Out) data structure. Elements are added at the rear and removed from the front.
Example:
begin
integer queueSize, front, rear;
queueSize := 10;
front := 1;
rear := 0;
array queue[1:queueSize] of integer;
procedure enqueue(integer value);
begin
if rear < queueSize then
begin
rear := rear + 1;
queue[rear] := value;
end
else
print("Queue Full");
end;
procedure dequeue();
begin
if front <= rear then
begin
print(queue[front]);
front := front + 1;
end
else
print("Queue Empty");
end;
enqueue(10);
enqueue(20);
dequeue();
dequeue();
dequeue();
end;Trees
A tree is a hierarchical data structure with a root node and child nodes. Each node can have multiple children.
Example:
begin
integer node;
record treeNode (integer value; ref treeNode left, right);
ref treeNode root;
root := new treeNode;
root.value := 10;
root.left := new treeNode;
root.left.value := 5;
root.right := new treeNode;
root.right.value := 15;
procedure inOrderTraversal(ref treeNode node);
begin
if node != nil then
begin
inOrderTraversal(node.left);
print(node.value);
inOrderTraversal(node.right);
end;
end;
inOrderTraversal(root);
end;Practical Exercises
Exercise 1: Implement a Doubly Linked List
Create a doubly linked list where each node points to both the next and the previous node.
Solution:
begin
integer node;
record nodeType (integer value; ref nodeType next, prev);
ref nodeType head, tail, temp;
head := new nodeType;
head.value := 10;
head.prev := nil;
head.next := new nodeType;
head.next.value := 20;
head.next.prev := head;
head.next.next := nil;
tail := head.next;
temp := head;
while temp != nil do
begin
print(temp.value);
temp := temp.next;
end;
end;Exercise 2: Implement a Circular Queue
Create a circular queue where the last position is connected back to the first position.
Solution:
begin
integer queueSize, front, rear;
queueSize := 5;
front := 1;
rear := 0;
array queue[1:queueSize] of integer;
procedure enqueue(integer value);
begin
if (rear + 1) mod queueSize != front then
begin
rear := (rear + 1) mod queueSize;
queue[rear] := value;
end
else
print("Queue Full");
end;
procedure dequeue();
begin
if front != (rear + 1) mod queueSize then
begin
print(queue[front]);
front := (front + 1) mod queueSize;
end
else
print("Queue Empty");
end;
enqueue(10);
enqueue(20);
dequeue();
dequeue();
dequeue();
end;Summary
In this section, we covered the basics of dynamic data structures in ALGOL, including linked lists, stacks, queues, and trees. We also provided practical examples and exercises to help reinforce the concepts. Understanding dynamic data structures is crucial for writing efficient and flexible programs that can handle varying amounts of data. In the next module, we will delve into advanced topics such as file handling and memory management.