CSC161 2010F, Class 50: Alterative Linked Structures: Doubly-Linked Lists Overview: * Quiz! * Questions on the exam? * Problem with the current delete procedure? * Two more procedures: list_contains and list_insert_after * Making Life Easier: Doubly-Linked Lists. * Inserting in Doubly-Linked Lists. * Deletion in Doubly-Linked Lists. Admin: * EC for Steve Kurtz movie@4:30 and convo on Thursday. Quiz! * What's wrong with the delete procedure? [ ] A. 42 [ ] B. It crashes if you delete something not on the list (We fixed that yesterday.) [ ] C. It only deletes one copy of the element if it appears multiple times. (Documentation says it's only supposed to delete one copy.) Exam Questions (at end of class?) * What did you mean in problem 7? * See sample code Examples/LinkedLists/prob7.c list_contains /** Return the first node containing str or NULL if no such node. */ static struct node *list_find (struct list *lst, char *str) { struct node *um = lst->head; while ( (um != NULL) && (strcmp (um->data, str) != 0) ) um = um->next; return um; } int list_contains (struct list *lst, char *str) { return (list_find (lst, str) != NULL); } // list_contains int list_insert_after (struct list *lst, char *target, char *str) { struct node *um = list_find (lst, target); if (um == NULL) return 0; // Make a new node with str // Make the next element um->next struct node *newnode = cons (str, um->next); if (newnode == NULL) return 0; // Make um->next new node um->next = newnode; // Increment the list length ++lst->size; // Update the tail if necessary if (lst->tail == um) lst->tail = newnode; // And we're done return 1; } // list_insert_after DOUBLY LINKED LISTS * That helpful find procedure above let us simplify insert_after and contains, but won't help with delete or insert_before * Sometimes it's easier to manipulate lists if you have a poitner to both the previous and the next node.