summaryrefslogtreecommitdiff
path: root/01-29.md
diff options
context:
space:
mode:
Diffstat (limited to '01-29.md')
-rw-r--r--01-29.md151
1 files changed, 151 insertions, 0 deletions
diff --git a/01-29.md b/01-29.md
new file mode 100644
index 0000000..aa13f39
--- /dev/null
+++ b/01-29.md
@@ -0,0 +1,151 @@
+[\<- 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 |