blob: c77ac6e8f4ebb34d0c0afea6d76e268a124152f8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
[\<- 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 |
---
[-> Notes 01/31](01-31.md)
|
