[PASCAL] Dynamic Array

[CouldnoT]

Dynamic Array

A dynamic array is an array with a big improvement: automatic resizing.

One limitation of arrays is that they're fixed size, meaning you need to specify the number of elements your array will hold ahead of time.

A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time.

 

 

Strengths:

• Fast lookups. Just like arrays, retrieving the element at a given index takes O(1)O(1) time.
• Variable size. You can add as many items as you want, and the dynamic array will expand to hold them.
• Cache-friendly. Just like arrays, dynamic arrays place items right next to each other in memory, making efficient use of caches.

Weaknesses:

• Slow worst-case appends. Usually, adding a new element at the end of the dynamic array takes O(1)O(1) time. But if the dynamic array doesn't have any room for the new item, it'll need to expand, which takes O(n)O(n) time.

• Costly inserts and deletes. Just like arrays, elements are stored adjacent to each other. So adding or removing an item in the middle of the array requires "scooting over" other elements, which takes O(n)O(n) time.

 

Script : 

 

program DynamicArray;
uses wincrt;

type
	tab = array of Integer;
var
	t : tab;
	LenghtCounter,i, input : Integer;

procedure AddToArray(const Num : Integer);
const
	AllocMem = 1024;		
begin
	if length(t) = LenghtCounter then 
		setlength(t, length(t) + AllocMem);
	t[LenghtCounter]:= Num;
	Inc(LenghtCounter);	
end;

begin
	LenghtCounter:= 0;
	repeat
		readln(input);
		AddToArray(input);
		setlength(t, LenghtCounter);		
	until input = -1;

	//writeln(LenghtCounter, ' ' ,high(t));
	for i:=0 to high(t) do 
		write(t[i], ' | ');	
	readkey();	
end.

Explanation : 

 

1) Procedure 

 

The following procedure consists of adding the input ( whatever type it is ) in the first step and increase the high of the Array by 1 in the second step.
Inc(LengthCounter) is the equivalent of LengthCounter += 1 or  LengthCounter:= LengthCounter + 1.

And it will Allocate more memory if the array is saturated. 

procedure AddToArray(const Num : Integer);
const
	AllocMem = 1024;		
begin
	if length(t) = LenghtCounter then 
		setlength(t, length(t) + AllocMem);
	t[LenghtCounter]:= Num;
	Inc(LenghtCounter);	
end;

2) Buddy 

 

In the buddy if the script I have included 4 Important parts : 

Reading a list of Integers until we reach the last one which is supposed to be -1.

Ranging the input in our dynamic array.

Setting the length of the array to the next step as it has increased by 1 from the procedure AddToArray.

Then output the array, I have to mention that the array counter starts from 0 which is the first case in the array until length - 1 or simply high which returns the same as Length -1, meaning that it reports -1 for empty arrays.

 

begin
	LenghtCounter:= 0;
	repeat
		readln(input);
		AddToArray(input);
		setlength(t, LenghtCounter);		
	until input = -1;

	//writeln(LenghtCounter, ' ' ,high(t));
	for i:=0 to high(t) do 
		write(t[i], ' | ');	
	readkey();	
end.

Learn more for advanced levels : Here

[CouldnoT]

Edited October 21, 2020 by CouldnoT