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.