summaryrefslogtreecommitdiff
path: root/01-31.md
diff options
context:
space:
mode:
Diffstat (limited to '01-31.md')
-rw-r--r--01-31.md95
1 files changed, 95 insertions, 0 deletions
diff --git a/01-31.md b/01-31.md
new file mode 100644
index 0000000..4158e08
--- /dev/null
+++ b/01-31.md
@@ -0,0 +1,95 @@
+[\<- Notes 01/29](01-29.md)
+
+---
+
+# Linked Lists Continued
+
+Recall: Linked List Declaration:
+
+```
+#define NODE struct node
+
+struct node{
+ char name[20];
+ int number;
+ NODE *next;
+};
+
+NODE *head = NULL;
+```
+
+## Deleting a Node
+
+- if the Linked List only has one Node:
+
+```
+head->next = NULL;
+free(p); //where p is a pointer to the deleted node
+```
+
+- if the Linked List has more than one Node and you want to delete the first Node:
+
+| Visual Representation | | | | | | | | | |
+| - | - | - | - | - | - | - | - | - | - |
+| **Before:** | head | -> | n1 | -> | n2 | -> | n3 | | |
+| **After:** | head | -> | n2 | -> | n3 | | | | |
+
+```
+head = head->next;
+free(p); //where p is a pointer to the deleted node
+```
+
+the order of steps is important (freeing memory should always be the last step)
+
+- Find nodes with matching numbers 'n' (p and q are pointers pointing to the nodes they are in):
+
+| Visual Representation | | | | | | | | | |
+| - | - | - | - | - | - | - | - | - | - |
+| **Before:** | head | -> | n1 (p) (q)| -> | n2 | -> | n3 | | |
+
+```
+NODE *p, *q;
+p = q = head;
+
+while(p->number != n && p != NULL){
+ q = p;
+ p = p->next; //traverse in n1 until it finds 'n' or it gets to the end (NULL);
+}
+```
+
+| Visual Representation | | | | | | | | | |
+| - | - | - | - | - | - | - | - | - | - |
+| **After above While loop:** | head | -> | n1 | -> | n2 (q)| -> | n3 (p)| | |
+
+```
+//eventually...
+q->next = NULL;
+free(p);
+```
+
+Conditional Statements to determine info about the above Linked List (where we want to delete the Node 'p' is pointing to):
+
+```
+if(head->next == NULL){ //there is only one node (head)
+ head = head->next;
+ free(p);
+}
+
+else{
+ if(p == head){ //this is the First Node
+ head = head->next;
+ free(p);
+ }
+ else if(p->next == NULL){ //this is the last node
+ q->next = NULL;
+ free(p);
+ }
+ else{ //the node is somewhere in the middle of the list
+ q->next = p->next;
+ free(p);
+ }
+}
+```
+
+- It can be helpful to define a tail pointer in addition to the head pointer
+ - the tail pointer would point to the end of the list