Post-class 01/29

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 |