CS 201 - 10/14/14

Variations on linked lists

   Singly Linked Lists can only be traversed from
      start to end.

   Doubly Linked Lists allow movement from start to
     end and from end to start.

     struct doubleNode
       { 
         int elem;
         struct doubleNode *next;
         struct doubleNode *prev;
       }

  A Doubly Linked List may often have a head and a
     tail pointers


Insert-in-order code for the doubly linked list.

struct dListHead
   {
     struct doubleNode *front;
     struct doubleNode *tail;
   }


  main (...)
   {
      struct dListHead dlist1;
      dlist1.front = NULL;
      dlist1.tail = NULL;


      insertInOrder ( &dlist1, val );

-------------------------------

  void inserInOrder (struct dListHead* dl, int val)
    {
      /* create the new node for the list */
      struct doubleNode* temp;
      temp = (struct doubleNode*) malloc 
                   ( sizeof (struct doubleNode));
      
      temp->elem = val;
      temp->next = NULL;
      temp->prev = NULL;

      /* check if list is empty */
      if (dl->front == NULL)
        {
         dl->front = temp;
         dl->tail = temp;
         return;
        }

      /* traverse the list to find the position to insert */
      struct doubleNode* curr;
      curr = dl->front;

      while ( ( curr != null ) && (curr->elem <= val ) )
        {
          curr = curr->next;
        }

      /* check if insert occurs at the front */
      if (curr == dl->front)
        {
           curr->prev = temp;
           temp->next = curr;
           temp->prev = NULL;
           dl->front = temp;
           return;
         }

     /* check if insert occurs at the tail */
     if (curr == NULL)
       {
          temp->next = NULL;
          temp->prev = dl->tail;
          dl->tail->next = temp;
          /* alternative to the above line is:
          struct doubleNode* temp2;
          temp2 = dl->tail;
          temp2->next = temp;
          */
          dl->tail = temp;
          return;
      }

    /* insert in the middle of the list */
    temp->next = curr;
    temp->prev = curr->prev;
    curr->prev->next = temp;
    curr->prev = temp;
    return;
   }


One final variation:  Circularly Linked List