Lab46 Wiki

User Tools

Site Tools

You are here: start » haas » fall2014 » data » projects » dska0-solution
haas:fall2014:data:projects:dska0-solution

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
haas:fall2014:data:projects:dska0-solution [2014/10/31 20:09] – [Background] wedgehaas:fall2014:data:projects:dska0-solution [2014/10/31 22:38] (current) – [Linked List Code Inversion] wedge
Line 29: Line 29:
 {{ :haas:fall2014:data:projects:posll0.png |}} {{ :haas:fall2014:data:projects:posll0.png |}}
  
-Note that the NULL terminating the list is to the left of the list start... so again, an inversion or negation what we are used to seeing.+Note that the NULL terminating the list is to the left of the list start... so again, an inversion or negation of what we are used to seeing.
  
-The trick here is that we still view this list from left to right-- start is on the left (or beginning), and end is on the right (the contextual end). In this scenario, the connections work against the grain when using the list.+The trick here is that we still "view" this list from left to right-- start is on the left (or beginning), and end is on the right (the contextual end). In this scenario, the connections work against the grain when using the list.
  
 =====Appending===== =====Appending=====
 Our task is to implement the append() operation for this form of linked list. In pictures, our task is as follows: Our task is to implement the append() operation for this form of linked list. In pictures, our task is as follows:
  
 +{{ :haas:fall2014:data:projects:posll1.png |}}
  
 +The familiar "place" and "newNode" references are kept for continuity with our in-class and project examples, and we see that in order to perform the proper connections, we need to also set a pointer to the node "after" place.
  
 +The setting of **tmp** will require a loop and logic similar to our **getpos()**/**setpos()** functions, and to the astute, the procedure actually resembles that of **insert()** in our next-oriented singly-linked list. And such observations would be in no way incorrect.
 ====Inversion/Negation==== ====Inversion/Negation====
  
Line 51: Line 53:
 So, positive becomes negative, plus becomes minus. All inclusive becomes conditionally inclusive (and vice versa). So, positive becomes negative, plus becomes minus. All inclusive becomes conditionally inclusive (and vice versa).
  
-Here with the previous-oriented linked-list, we have the same concept at work. While we +=====Linked List Code Inversion===== 
 +Here with the previous-oriented linked-list, we have the same concept at work: 
 + 
 +  * **insert()** in a next-oriented singly-linked list is functionally equivalent to **append()** in a previous-oriented singly-linked list 
 +  * **append()** in a next-oriented singly-linked list is functionally equivalent to **insert()** in a previous-oriented singly-linked list 
 +  * To display the list from start to end in a previous-oriented singly-linked list, we effectively need to use the **displayb()** logic to assist us in our task. 
 + 
 +More precisely, to convert the next-oriented linked-list **insert()** into a previous-oriented linked-list **append()**: 
 +  * all **next** references become **prev** 
 +  * all references to **start** become **end** 
 +  * all original references to **end** become **start** 
 + 
 +====positioning tmp==== 
 +You'll see that, instead of seeking from the start of the list, we must seek from the end. And just as with next-insert(), which requires us to get to the node "before", prev-append() has the same need (it is the node that connects to place, and we get here from the end of the list). 
 + 
 +The only difference here (if we were to implement **getpos()/setpos()** functionality), is that when considering list position values, instead of doing: 
 + 
 +<code c> 
 +// next-oriented insert() tmp placement 
 +tmp = setpos(theList, getpos(theList, place)-1); 
 +</code> 
 + 
 +We instead need to: 
 + 
 +<code c> 
 +// prev-oriented append() tmp placement 
 +tmp = setpos(theList, getpos(theList, place)+1); 
 +</code> 
 + 
 +Note the -1 and +1 difference. 
 +====navigating with while==== 
 +Obviously, since **getpos()/setpos()** functions were not provided, some sort of repetition is in order (many seemed to go with a while loop, starting from the end of the list-- an excellent choice). 
 + 
 +Likely, something of the form: 
 + 
 +<code c> 
 +tmp = myList -> end; 
 +while (tmp -> prev != place) 
 +{ 
 +    tmp = tmp -> prev; 
 +} 
 +</code> 
 + 
 +====average case connection==== 
 +And then we could perform the necessary hook-ups (average case consideration): 
 + 
 +<code c> 
 +newNode -> prev = place; 
 +tmp -> prev = newNode; 
 +</code> 
 + 
 +====edge case connections==== 
 +As for edge cases, aside from dealing with similar NULL and empty list scenarios, the edge cases for prev-append() would be the same as those considered in next-insert(). 
 + 
 +  * next-insert() had special consideration for inserting before the start of the list 
 +  * prev-append() therefore has special consideration for appending after the end of the list 
 + 
 +Similarly, as we just observed with the while loop logic: 
 + 
 +  * next-insert() had to locate the node one list position prior to place (coming from the direction of theList -> start) 
 +  * prev-append() therefore has to locate the node one list position after place (coming from the direction of theList -> end) 
 + 
 +=====example append() implementation===== 
 +To aid in understanding, here is my reference implementation of append() for the previous-oriented singly-linked list: 
 + 
 +<code c 1> 
 +#include "list.h" 
 + 
 +////////////////////////////////////////////////////////////////////// 
 +// 
 +// append() - add newNode to the list after place 
 +// 
 +List *append(List *theList, Node *place, Node *newNode) 
 +{ 
 +    ////////////////////////////////////////////////////////////////// 
 +    // 
 +    // tmp will be our "after" pointer, allowing the side of the list 
 +    // to the right of place to connect in to newNode 
 +    // 
 +    Node *tmp                   = NULL; 
 + 
 +    ////////////////////////////////////////////////////////////////// 
 +    // 
 +    // edge case: should the list pointer be NULL, allocate a new List 
 +    //            and initialize theList -> start and end to sane 
 +    //            initial values. This is essentially what mklist() 
 +    //            does in the sll projects. 
 +    // 
 +    if (theList                == NULL) 
 +    { 
 +        theList                 = (List *) malloc(sizeof(List)); 
 +        theList -> start        = NULL; 
 +        theList -> end          = NULL; 
 +    } 
 + 
 +    ////////////////////////////////////////////////////////////////// 
 +    // 
 +    // edge case: the only thing that can gum up the works now is a 
 +    //            NULL newNode; so if one is encountered, do nothing 
 +    //            and return the list as-is. 
 +    // 
 +    if (newNode                != NULL) 
 +    { 
 +        ////////////////////////////////////////////////////////////// 
 +        // 
 +        // edge case: if we have an empty list, newNode becomes the 
 +        //            list contents. 
 +        // 
 +        if ((theList -> start  == NULL) && 
 +            (theList -> end    == NULL)) 
 +        { 
 +            ////////////////////////////////////////////////////////////// 
 +            // 
 +            // this is the simplest case- nothing exists so newNode IS 
 +            // the list contents. Merely update the start and end 
 +            // pointers and we're all set. 
 +            // 
 +            theList -> start    = newNode; 
 +            theList -> end      = newNode; 
 +        } 
 + 
 +        ////////////////////////////////////////////////////////////// 
 +        // 
 +        // edge case: if we're appending after end, we need to take 
 +        //            care to update theList -> end 
 +        // 
 +        else if (place         == theList -> end) 
 +        { 
 +            ////////////////////////////////////////////////////////////// 
 +            // 
 +            // this is the next simplest case to connect, as we only have 
 +            // to deal with one connection (hooking newNode into the list; 
 +            // then update theList -> end as appropriate). 
 +            // 
 +            newNode -> prev     = theList -> end; 
 +            theList -> end      = newNode; 
 +        } 
 + 
 +        ////////////////////////////////////////////////////////////// 
 +        // 
 +        // average case: if we're dealing with a typical append, we 
 +        //               do the following. We're also protecting  
 +        //               against a rogue edge case of the list being 
 +        //               non-empty yet place being NULL (trying to 
 +        //               process that condition would result in  
 +        //               certain disaster). 
 +        // 
 +        else if (place         != NULL) 
 +        { 
 +            ////////////////////////////////////////////////////////////// 
 +            // 
 +            // positioning tmp: we can only navigate from the end of the 
 +            //                  list, so we must start tmp there; then, 
 +            //                  keep seeking until we arrive at the node 
 +            //                  one prev away from place. 
 +            // 
 +            tmp                 = theList -> end; 
 +            while (tmp -> prev != place) 
 +            { 
 +                tmp             = tmp -> prev; 
 +            } 
 + 
 +            ////////////////////////////////////////////////////////////// 
 +            // 
 +            // connecting it: newNode connects to place, and the existing 
 +            //                list node connecting to place hooks to 
 +            //                newNode. 
 +            // 
 +            newNode -> prev     = place; 
 +            tmp     -> prev     = newNode; 
 +        } 
 +    } 
 + 
 +    ////////////////////////////////////////////////////////////////// 
 +    // 
 +    // whether we modify the list or bail out, we'll always return 
 +    // the right thing. 
 +    // 
 +    return(theList); 
 +} 
 +</code>
haas/fall2014/data/projects/dska0-solution.1414786158.txt.gz · Last modified: 2014/10/31 20:09 by wedge

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki