[\<- Notes 01/24](01-24.md)

---

# Dynamic Data Structures and Memory Allocation

- Dynamic data structures are dynamic (as opposed to static structures)
	- Can **grow** or **shrink**

- Dynamically allocated memory determined at runtime
	- flexible
	- finite
	- can also be freed during execution

- allocating memory:
	- `malloc` - memory allocation
	- `calloc` - cleared memory allocation
	- `free	 release memory
	- `realloc` change size of memory requested by `malloc` or `calloc`

- `malloc` and `calloc`
	- return pointers to newly allocated memory
	- declared as a pointer of **void-type**
		- therefore, these void-type pointers **must be cast to the proper pointer type**
	- if memory cannot be allocated, a null-pointer is returned

- Example:

```
int npts = 500;
double *x;
int *p;

// Allocate memory for 500 doubles //
x = (double *)malloc(npts * sizeof(double));

// Allocate memory for 500 integers //
p = (int *)calloc(npts * sizeof(int));
```

- Example: Allocating a 2D array dynamically:

```
int rows = 10;
int cols = 20;
double *x;

// Allocate a matrix for 200 doubles //
x = (double *)malloc(rows * cols * sizeof(double));
```

---

# Linked Lists

- Group of structures(**nodes**), connected by pointers
- A node consists of data(one or more variables) and a pointer to the next node
- Nodes can be ordered
- Head pointer points to the 1st node
	- Nodes are accessed through the head pointer
	- The last node's pointer is null
- Linked lists can be implemented
	- in an array (static)
	- with dynamically-obtained structures (dynamic)

- Example:

```
#define NODE struct node
...
struct node{
	int number;
	NODE *next;
};
...
```

- Creating an empty list:

```
NODE *head = NULL;
```

## Unordered Linked Lists

- Common Operations
	- Insert a node
		- insert before head
	- Search a node
		- search the entire linked list
	- Delete a node
		- search the entire linked list
	- Output the list

- **Insertion**
	- Nodes are inserted at the front of the list
	- Each node is obtained with a call to malloc

- Example:

```
NODE *p;
...
if((p = (NODE *)malloc(sizeof(NODE))) == (NODE *)NULL){
	printf("memory could not be allocated\n");
	return 0;
}

p->number = number;
p->next = head;
head = p;
```

Another Example (Unordered Linked List):

```
NODE *head = NULL;

void insert(int number){
	NODE *p;

	p = (NODE *)malloc(sizeof(NODE)); //create a new node
	if(p == NULL) return 0;
	if(head == NULL){
		p->number = number;
		p->next = NULL;
		head = p;
	}
	else{
		p->number = number;
		p->next = head;
		head = p;
	}
}
```

- **Order** of the above code **is important**

Example: This time, I want to insert a node after a pointer q (somewhere in the middle of the list):

```
p->next = q->next; //put the new node in the right place
q->next = p;       //the previous node now needs to point to the newly inserted node
```

Visual Representation of the previous example:

| Visual Representation | | | | | | | | | |
|   -         |  -   | -  | -  | -  |   -    |  - | -  | - | - |
| **Before:** | head | -> | n1 | -> | n2 (q) | -> | n3 |   |   |
| **After:**  | head | -> | n1 | -> | n2 (q) | -> | inserted n (p) | -> | n3 |