Reading

None.

Pointers not values, search in linked lists

Recall that, earlier in the semester, we discussed that where arrays are concerned, it's "indices not values". With linked lists we have something similar: pointers not values. As with arrays, when this becomes really important is search. Suppose we want to write a "search" function for linked lists? What should we return if the search is successful? What should we return if a search is unsuccessful? In both cases, the best thing to do is to return a pointer. If the search is successful, we return a pointer to a node in the list whose data matches what we're searching for. If the search is unsuccessful, we return a NULL pointer. Thus, the search prototype will be (in this example for lists with data of type double): 
Node* search(dobule value, Node* L);
As we discussed with "search" in the case of arrays, it's best to have a function bool match(double a, double b); — where the types of the arguments a and b match the type of the data in the Node — that takes care of determining whether the data in an individual Node matches the value being searched for.

As an exercise, try downloading Ex0.cpp and see if you can provide a definition for the "search" function. If you've done it properly, the program should run like this: 

~/$ ./prog
34.2 , 54.98 , 92.0, 83.9;
search 54.98
Found!
search 54.88
Not Found!
search 12
Not Found!
quit
I'll provide you with two solutions, an iterative solution and a recursive solution.

Insert in order

One of the nice things about a linked list is that it's pretty easy to insert new nodes anywhere you'd like. If there's a new value you've read in, you might not necessarily want to add it to the front of the list or to the back. You might, for example, want to insert it in a list in a way that mantains sorted order. Let's consider a function insert_in_order(val,L) that will insert a new value val into L so that sorted order is maintained. Here's what we need to do in pictures:
Start: We want to add val to the list L.
Move p to point to the node after which val should be added.
Create the new node we want, with the proper data and next values. 
Node *T = new Node;
T->data = val;
T->next = p->next;
Splice our new node in after the node p points to. 
p->next = T;

	
Done!

      

      
      Now, how do we make that work in C++ code?
      First we need to "Move p to point to the node after which we
      want to insert our new node".
      

	

	  Attempt 1:
	  
  Node *p = L;
  while(p->next->data < val)
    p = p->next;
  add2front(val,p->next);

	  
	    Commentary: What makes p special
	    is that it's the first node in your list whose next
	    node has a bigger data value than val.
	    That's what we're looking for here.  The only problem
	    is that this'll crash if val is bigger
	    than everything currently in the list.  To deal with this,
	    we should also stop moving p if it's the
	    last node in the list - i.e. if p->next
	    is NULL.
	  
	

	

	  Attempt 2:
	  
  Node *p = L;
  while(p->next != NULL && p->next->data < val)
    p = p->next;
  add2front(val,p->next);

	  		
	  
	    Commentary: This works like a champ, but it
	    contains the hidden assumption that val
	    will never need to come before the first node.
	  
	

	

	  Attempt 3:
	  
if (L->data < val)
{
  Node *p = L;
  while(p->next != NULL && p->next->data < val)
    p = p->next;
  add2front(val,p->next);
}
else
  add2front(val,L);

	  
	    Commentary:
	    This is fine, except that it crashes if L
	    is the empty list, because the test L->data
	    implicitly assumes that L is really
	    pointing to something!
	  
	

	

	  Success!
	  
if (L != NULL && L->data < val)
{
  Node *p = L;
  while(p->next != NULL && p->next->data < val)
    p = p->next;
  add2front(val,p->next);
}
else
  add2front(val,L);

	  
	    Commentary:
	    This does exactly what we want, in all cases!
	  
	

      


      Now, let's compare the iterative versus the recursive version of
      the insert_in_order function:

      

	

	    
void insertinorder(double val, Node* &L)
{
 if (L != NULL && L->data < val)
   insertinorder(val,L->next);
 else
   add2front(val,L);
}

	  		
	    
void insertinorder(double val, Node* &L)
{
  if (L != NULL && L->data < val)
  {
    Node *p = L;
    while(p->next != NULL && p->next->data < val)
      p = p->next;
    add2front(val,p->next);
  }
  else
    add2front(val,L);
}


	

      

      You can do this stuff quite elegantly with recursion!
    

    
    

      
Sorting

      With our insertinorder we can sort stuff pretty
      easily with linked lists.  For example, if you want to read in a
      bunch of values and put them in sorted order, you can simply put
      them in a list as you read them using insertinorder,
      and when you're done, you'll have a sorted list of values.  Not
      bad, eh?  Of course, as we know from selection sort there are
      many, many different "orders" you can put things into when you
      sort.  If you recall, we used the before(a,b) function
      to determine whether element a must come before
      element b in sorted order.  We really ought to write
      insertinorder so it relies on a "before" function as
      well. This program uses linked lists and
      insertinorder with a "before" function to read in words
      from the user and write them back sorted by incresing length, with 
      ties broken by alphabetical order.  Here's an example of the
      program in action:
      
Enter words, terminated with a semi-colon :
the quick brown fox jumped over the lazy dog ;
dog fox the the lazy over brown quick jumped

    


    

      
Sorting existing lists

      Suppose that you already have a list and it's not in sorted
      order.  You could easily create a sorted copy of the list by
      moving through you list a node at a time and calling
      insertinorder for that node's data.
      
Node* sortedcopy(Node* L)
{
  Node* S = NULL;
  for(Node* p = L; p != NULL; p = p->next)
    insertinorder(p->data,S);
  return S;
}

      This function returns a copy of the original list in sorted order.
    

    
    

      
Problems

      
    

	
  1. 
	  Write a program that reads in commands from the user,
	  which are quit, add x, and
	  print.
	  Each time the add x command is given, the
	  actual number (as opposed to x) is stored.  Each time the
	  print command is given, all the numbers added thus
	  far are printed out in sorted order.  I'll leave it to you
	  to guess what the quit command does!
	
    2. 

	
  2. 
	  Modify the insertinorder function from above so
	  that duplicate values are not inserted, but rather simply 
	  ignored.  Thus, if used on the example code in which words
	  are entered, only unique words would appear — no
	  duplicates.
	
    3. 

	
  3. 
	  Write a program that reads in a collection of words
	  (comma-separated, semicolon-terminated) and then prints out
	  each word (order not important) along with the number of
	  times that word was entered.
	  Here's a sample run:
	  
    ~/$ ./prog
hi , bye , yo , ciao , hi , hallo , yo , sianara ;
sinara 1
hallo 1
ciao 1
yo 2
bye 1
hi 2
    
	
    4.