diff options
Diffstat (limited to '01-31.md')
-rw-r--r-- | 01-31.md | 95 |
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 |