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:28] – [example append() implementation] 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===== | ||
haas/fall2014/data/projects/dska0-solution.1414794481.txt.gz · Last modified: 2014/10/31 22:28 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
