Static and Dynamic Allocation Linked Lists

Flashcards about Static and Dynamic Allocation of variables, Pointers and Linked Lists

Static data types

Allocate a fixed amount of memory at compile time, dictating the maximum number of elements it can hold.

Dynamic Data Structures

A solution to the limitations of static data types, allowing for more flexible memory allocation.

Linked Lists

An example of dynamic data structures

RAM

Random Access Memory, the memory all computers have

Variable

A contiguous area in memory whose size depends on its type.

Pointer

A variable that contains the address of another variable as its value.

Static Allocation

Memory for variables is allocated at compile time and remains fixed throughout the program's execution.

Dynamic Allocation

Memory for variables is allocated at runtime and can be resized or deallocated as needed.

Allocate()

A function used in dynamic memory allocation to obtain a new zone in the heap, returning its address.

Free()

A function used in dynamic memory allocation to return a memory location from the heap, destroying the link to the pointer.

Linked List

A sequence of dynamically allocated elements (nodes) linked together to represent a set of information.

Node

Represent each information and composed of 2 fields, an information field and an address field

Linked List Head

The address of the first element of a linked list.

Linked List Model

A set of operations defined to develop algorithms on linked lists.

Value(p)

Returns the content of the ”info” field of the node pointed to by p

Next(p)

Returns the content of the 'next' field (address) of the node pointed to by p

Ass Val(p, v)

Procedure which assigns the value v to the ”info” field of the node pointed to by ”p”

Ass Addr(p, q)

Procedure which assigns the address q to the ”next” field of the node pointed to by p

Circular Linked List

A list whose last node points to the first node.

Doubly Linked List

A list that can be traversed in either direction, with each node containing the address of the previous node.

Prev(p)

A function which returns the content of the ''prev'' field, it is used to access the left (previous) node.

Ass l addr(p, q)

In the ”prev” field (left address) of the node with address p, we store the address q.

Ass r addr(p, q)

In the ”next” field (right address) of the node with address p, we store the address q.