Linked Lists
--------------

  type Node:
  	record
  		info : string
  		next : ^Node
  	end record
  
  var top,temp : ^Node
  
Goal: Create the following
             ______    ______    ________    ______
       top ->|Jeff| -> |Tim | -> |Gunnar| -> |Fun |->nil
             ------    ------    --------    ------
  new top
  top->info := "Jeff"
  new top->next
  top->next->info := "Tim"
  new temp
  top->next->next := temp
  temp->info := "Gunnar"
  new temp->next
  temp := temp-> next
  temp->info := "Fun"
  temp->next := nil
  

Add/Delete to top/bottom/middle
--------------------------------

Steps in writing code
 - Specification
      % Adds a node containing info to the top of the list
      procedure AddToTop( top, bottom : ^Node, info : string )

 - first handle general case
     - draw picture
              ___    ___    ___    ___  <- bottom
       top ->|___|->|___|->|___|->|___|-> nil

     - what steps are needed to add a record in front?
     - write code
         new temp
         temp->info := info
         temp->next := top
         top := temp

- Check if this works for special cases
   - case empty list: top = bottom = nil
       Previous code works for top, but not bottom. 
       Add:
          if bottom=nil then 
             bottom := temp
          end if
       Change Specs  "var top, bottom"

  - case out of memory: Add
     if temp=nil then 
       put "Out of memory
       return
     end if
     
   % Adds a node containing info to the top of the list
   procedure AddToTop( var top, bottom : ^Node, info : string )
        var temp : ^Node
        new temp
        if temp=nil then 
            put "Out of memory
            return
        end if
        temp->info := info
        temp->next := top
        top := temp
        if bottom=nil then 
            bottom := temp
        end if
   end AddToTop
        
Similarly:
   
   % Deletes the node at the top of the list and returns its info
   procedure DelFromTop( var top, bottom : ^Node, var info : string )
        assert top~=nil   
        info := top->info
        var kill := top
        top := top->next
        free kill
        if top=nil then    % special case: one node
             bottom := nil
        end if
   end DelFromTop
   
   
   % Adds a node containing info to the bottom of the list
   procedure AddToTop( var top, bottom : ^Node, info : string )
        var temp : ^Node
        new temp
        if temp=nil then 
            put "Out of memory
            return
        end if
        temp->info := info
        temp->next := nil
        if bottom~=nil then 
             bottom->next := temp
        else
             assert top=nil
             top := temp  % special case: empty list
        end if 
        bottom := temp
   end AddToTop
        
   
   Delete from bottom
     PostCond: last node in list is removed 
        and bottom points at the second last node.
     Q: panic: how do you get to the second last element
     A: walk there
   
   
Finding an Element
--------------------
   
   % PreCond: top points at a linked list
   %          key is string to find
   % PostCond: returns a pointer to the record containing the key
   %        or if no such record returns nil
   function Find( top : ^Node, key : string ) : ^Node 
       var p : ^Node
       p := top
       loop % <Loop Inv>: The required node is not before node pointed to by p
         exit when p=nil or p->info=key
         p := p->next
       end loop
       % <postLoop>: if key is in list, p points at this node
       %             else p=nil
       result p
   end Find
   
   Note  "exit when p->info=key or p=nil" would crash
   
   
Inserting an Element
--------------------
          ___    ____    ___    ___ 
   top ->|___|->|_fun|->|___|->|___| <- bottom
   
   Goal insert record with wow after record with fun.
   p := Find( top, "fun" )
   if p~=nil then
        new temp
        temp->info := "wow"
        temp->next := p->next
        p->next := temp
   end if
   
   
Deleting an Element
-------------------
   
   Goal delete the record with fun
   p := Find( top, "fun" )
   Problem: Need the previous node to link to next node.
   
   % Deletes the node containing info
   procedure DelFromMid( var top, bottom : ^Node, info : string )
       var p,previous : ^Node
       previous := nil
       p := top
       loop % <Loop Inv>: The required node is not before node pointed to by p
         exit when p=nil or p->info=key
         previous := p
         p := p->next
       end loop
       % <postLoop>: if key is in list, p points at this node
       %               else p=nil
       %             previous points at previous node
       %               or nil if no previous node
       if p=nil then   % either Top=nil or fell off end of list
         put "Node not present "
           return
       end if
   
       % Connect previous and next nodes
       if previous=nil then   % special case: delete first node
           top := p->next  
       else
           previous->next := p->next
       end if
   
       % Check bottom
       if bottom=p then       % special case: deleting last
           bottom := previous
       end if
   
       free p
   end DelFromMid
  
Check
  - key in middle node
  - key in first node
  - key in last node
  - key in only node
  - key not in list
  - empty list


Finalize
-----------
   % Frees all the nodes
   procedure DelFromTop( var top, bottom : ^Node )
      var p, kill: ^Nodes
      p := top
      loop
         exit when p=nil
         kill := p
         p := p->next
         free kill
       end loop
       top := nil
       bottom := nil
   end Finalize