The code on this page accompanied the diagrams that were drawn on the blackboard on Wednesday's lecture.

This is the structure of our Node:

struct Node
{
  int data;
  Node* link;
};

Node* currPtr;
Node* prevPtr;
Node* newNodePtr;

newNodePtr = new Node;
newNodePtr->data = item;
  
prevPtr = NULL;
currPtr = head;

while (currPtr != NULL && item > currPtr->data)
{
  prevPtr = currPtr;
  currPtr = currPtr->link;
}

newNodePtr->link = currPtr;
if (prevPtr == NULL)
  head = newNodePtr;
else
  prevPtr->link = newNodePtr;

This code doesn't assume that the item is in the list. It may not be present, and this code will handle that case. Also, this code only removes the first occurrence of the item. If more than one exist, only the first one is removed.

head is assumed to be a pointer to the head of a non-empty list and the item to delete is 10.

Node* oldptr;
Node* ptr;

if (head->data == item)
{    
  oldptr = head;
  head = head->next;
  delete oldptr;
}
else
{  
  ptr = head;
  while (ptr->next)
  {
    if (ptr->next->data == item)
    {
      oldptr = ptr->next;
      ptr->next = ptr->next->next;
      delete oldptr;
      break;
    }
    ptr = ptr->next;
  }  
}