CSC161 2010F, Class 49: Deleting Elements from Lists

Overview:
* Exam 3 questions
* Review
* Deletion in Linked Lists.

Admin:
* No office hours today; Home with sick children.
* EC for Steve Kurtz movie on Tuesday and Convo on Thursday.
* No reading for Tuesday

Idea: Hide the underlying nodes from the client programmer.

struct node {
  struct char *data;
  struct node *next;
}

struct list {
  struct node *head;
  struct node *tail;
  int length;
}

Main list operations:
* Create a new empty list.  Return NULL if we failed.

struct list *new_list ()
{ 
  // Allocate memory
  struct list *newlst = malloc (sizeof (struct list));
  if (newlst == NULL)
    return NULL;
  newlst->head = NULL;
  newlst->tail = NULL;
  newlst->length = 0;
  return newlst;
} // new_list

* Add to the end

int add_to_end (struct list *lst, char *str)
{
  // Make a new node for the string
  struct node *newnode = malloc (sizeof (struct node));
  if (newnode == NULL)
    return 0;
  newnode->data = str;
  newnode->next = NULL;
 
  if (length == 0)
    lst->head = newnode;
  else
    // Make lst->tail->next point to this new node
    lst->tail->next = newnode;

  lst->tail = newnode;

  // Increment the length
  ++length;

  // Yay!
  return 1;
}

* Print
* Add to the front
* Add after
* Delete

Given the list (a b c d)
What steps do I need to do to remove the b?

  * Find b, assuming it's in the list
    node = lst->head;
    while (strcmp (node->data, "b") != 0)
      node = node->next;
  * Whoops, find the node before the node with b
    node = lst->head;
    while (strcmp (node->next->data, "b") != 0)
      node = node->next;
  * Store the thing we want to delete
    node *deleteme = node->next;
  * Update the next pointer in node to point to the nextnext thing
    node->next = deleteme->next;
  * And get rid of the thing we want to get rid of
    free (deleteme);

  * Special case: b is the last element
    Need to update tail (before deleting deleteme)
    if (deleteme->next == NULL)
      lst->tail = node;
    if (deleteme == lst->tail)
      lst->tail = node;

  * Special case: b is the first element
    "Ah, it will work"

* Get First
* Get Last
* Get Length

* Iterate
* Ith