In more advanced computers with variable amounts of RAM, allocating

variables is not as simple as in the first question. A common approach for such

systems is keep a linked list of allocations in a memory pool, and upon de$-$allocation

to coalesce $($combine$)$ the freed space back into the free part of the pool.

See the following illustration:

In this example, we start with $1000$blocks$$ of RAM, and then perform a sequence

of allocations and free$$s; the resultant linked list is shown after each operation has

been performed.

$($a$)$ In this question, you will partially simulate the behaviour of such a memory

allocator. A partial Python class has already been provided, along with a

sample input text file for the illustration above. Your solution must implement

the following requirements:

$$ Allocations must happen in the smallest available block that can hold

that memory. So if you want to allocate $5$ blocks, and there are several

places to allocate that space, it must be from the smallest area. In the

event of a tie, it should be the first location in the linked list.

When an allocation happens and there is more space than needed, the

block splits into two $$ the memory being allocated and the remaining free

memory $($see Allocate $4$ e for smallest block and the split$).$

$$ De$-$allocations $($free$$s$)$ must coalesce adjacent blocks that are already free.

Note that there are two possibilities:

$$ An area is free to the left $($or the right$)$: In this case, the area to

remove as well as the adjacent area will coalesce into one area, with

the free space being a sum of the two.

$$ Areas are free both to the left and right: In this case, all three areas

should coalesce into one, with the free space being a sum of the three

$($see $$Free d$$ for an example of this$).$

Complete the Python class in the attached file MemoryAlloc.py$.$ Study the

given code, and read$/$understand the comments. Remember that the markers

will use different test files, so your code must be robust and consider all use

cases.

$($b$)$ Create a few test files. Note that the markers will be using several test files,

so your code must be general and work in all cases.

$($c$)$ Compare both the time and space complexity of this implementation with the

solution from Question $2.$