Re: [Tutor] Make a linked list subscriptable?
On 7/11/19 10:55 AM, Mats Wichmann wrote: > On 7/10/19 6:30 PM, Sarah Hembree wrote: >> How might I best make a linked list subscriptable? Below is skeleton code >> for a linked list (my >> actual is much more). I've done __iter__ and __next__ but I would like to >> be able to do start:stop:stride I just can't figure out how. Suggestions or >> just hints please? > As a learning exercise this can be interesting, but as to practical > applications, one would like to ask "why"? If index into the list is > important, then choose a regular list; the "interesting" part of a > linked list, which is "next node" is then available as index + 1. > To expand on the question, the primary use of something like a linked list is that you want cheap insertions/deletions (of O(1)) and in exchange for that indexing becomes O(n), verse an array based list which has O(1) indexing but O(N) insertions/deletions (since you need to compact the array). Both can be iterated in O(1). You can add an index operator that takes O(N) time to a linked list. obj[n] will call obj.__getitem__ (and you will also want to implement __setitem__, __delitem__), and check if the argument is a slice to handle slices. -- Richard Damon ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Make a linked list subscriptable?
On 7/10/19 6:30 PM, Sarah Hembree wrote: > How might I best make a linked list subscriptable? Below is skeleton code > for a linked list (my > actual is much more). I've done __iter__ and __next__ but I would like to > be able to do start:stop:stride I just can't figure out how. Suggestions or > just hints please? As a learning exercise this can be interesting, but as to practical applications, one would like to ask "why"? If index into the list is important, then choose a regular list; the "interesting" part of a linked list, which is "next node" is then available as index + 1. ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Make a linked list subscriptable?
On 10Jul2019 20:30, Sarah Hembree wrote: How might I best make a linked list subscriptable? Below is skeleton code for a linked list (my actual is much more). I've done __iter__ and __next__ but I would like to be able to do start:stop:stride I just can't figure out how. Suggestions or just hints please? Well, you could write a method to find and return element `n`, counting from 0 (the root Node). For start stop stride you could do the extremely simple approach: iterate over a range() of the start stop stride and call the get-element-n method. This will be very slow though (a complete scan for every element). Instead, you could write a method accepting a start, stop and stride. Call the find-element-n method to get to start, lets call that `n`. While n < stop, step forward `stride` elements and also bump `n` by stride. That steps you along each element indicated by the start:stop:stride. You'll notice that this only works for a positive stride. For a negative stride you're probably better off handing it to range(), getting a list of values back from that as a list, and reversing the list (which then has ascending values). Collect the elements indicated by the list (because you can traverse the linkedlist forwards). Then reverse the collected elements and return them. Now, you _could_ accumulate each element in a list and return that at the end. _Or_ you could make the function a generator and just yield each element as found. To turn all this into a subscriptable list, define the __getitem__ method as a function accepting an index. If that index is an int, just return that element. If the index is a slice (start:stop:stride), call the more complicated function to return multiple elements. Cheers, Cameron Simpson ___ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
