haas:fall2014:data:projects:dska0-solution
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| haas:fall2014:data:projects:dska0-solution [2014/10/31 22:24] – [Linked List Code Inversion] wedge | haas:fall2014:data:projects:dska0-solution [2014/10/31 22:38] (current) – [Linked List Code Inversion] wedge | ||
|---|---|---|---|
| Line 29: | Line 29: | ||
| {{ : | {{ : | ||
| - | 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 |
| - | 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" |
| =====Appending===== | =====Appending===== | ||
| Line 58: | Line 58: | ||
| * **insert()** in a next-oriented singly-linked list is functionally equivalent to **append()** in a previous-oriented singly-linked list | * **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 | * **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 perform | + | * 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()**: | More precisely, to convert the next-oriented linked-list **insert()** into a previous-oriented linked-list **append()**: | ||
| Line 65: | Line 65: | ||
| * all original references to **end** become **start** | * all original references to **end** become **start** | ||
| - | 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(), | + | ====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(), | ||
| The only difference here (if we were to implement **getpos()/ | The only difference here (if we were to implement **getpos()/ | ||
| Line 81: | Line 82: | ||
| </ | </ | ||
| - | Obviously, since **getpos()/ | + | Note the -1 and +1 difference. |
| + | ====navigating with while==== | ||
| + | Obviously, since **getpos()/ | ||
| Likely, something of the form: | Likely, something of the form: | ||
| Line 93: | Line 96: | ||
| </ | </ | ||
| + | ====average case connection==== | ||
| And then we could perform the necessary hook-ups (average case consideration): | And then we could perform the necessary hook-ups (average case consideration): | ||
| Line 100: | Line 104: | ||
| </ | </ | ||
| + | ====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(). | 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 | * next-insert() had special consideration for inserting before the start of the list | ||
| - | * prev-append() has special consideration for appending after the end of the list | + | * prev-append() |
| Similarly, as we just observed with the while loop logic: | 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) | * next-insert() had to locate the node one list position prior to place (coming from the direction of theList -> start) | ||
| - | * prev-append() has to locate the node one list position after place (coming from the direction of theList -> end) | + | * prev-append() |
| =====example append() implementation===== | =====example append() implementation===== | ||
| Line 116: | Line 121: | ||
| #include " | #include " | ||
| + | ////////////////////////////////////////////////////////////////////// | ||
| + | // | ||
| + | // append() - add newNode to the list after place | ||
| + | // | ||
| List *append(List *theList, Node *place, Node *newNode) | List *append(List *theList, Node *place, Node *newNode) | ||
| { | { | ||
| Line 150: | Line 159: | ||
| // | // | ||
| // edge case: if we have an empty list, newNode becomes the | // edge case: if we have an empty list, newNode becomes the | ||
| - | // list contents- theList -> start and end need to | + | // list contents. |
| - | // be updated | + | |
| // | // | ||
| if ((theList -> start == NULL) && | if ((theList -> start == NULL) && | ||
| Line 159: | Line 167: | ||
| // | // | ||
| // this is the simplest case- nothing exists so newNode IS | // this is the simplest case- nothing exists so newNode IS | ||
| - | // the list contents. Merely update the start and end pointers | + | // the list contents. Merely update the start and end |
| - | // and we're all set. | + | // pointers |
| // | // | ||
| theList -> start = newNode; | theList -> start = newNode; | ||
haas/fall2014/data/projects/dska0-solution.1414794259.txt.gz · Last modified: 2014/10/31 22:24 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
