set and dict iteration

[Aaron Brady]

On Thursday, August 23, 2012 1:11:14 PM UTC-5, Steven D'Aprano wrote:
> On Thu, 23 Aug 2012 09:49:41 -0700, Aaron Brady wrote:
> 
> 
> 
> [...]
> 
> > The patch for the above is only 40-60 lines.  However it introduces two
> 
> > new concepts.
> 
> > 
> 
> > The first is a "linked list", a classic dynamic data structure, first
> 
> > developed in 1955, cf. http://en.wikipedia.org/wiki/Linked_list . 
> 
> > Linked lists are absent in Python
> 
> 
> 
> They certainly are not. There's merely no named "linked list" class.
> 
> 
> 
> Linked lists are used by collections.ChainMap, tracebacks, xml.dom, 
> 
> Abstract Syntax Trees, and probably many other places. (Well, technically 
> 
> some of these are trees rather than lists.) You can trivially create a 
> 
> linked list:
> 
> 
> 
> x = [a, [b, [c, [d, [e, None]]]]]
> 
> 
> 
> is equivalent to a singly-linked list with five nodes. Only less 
> 
> efficient.
>
[snip.]
>
> -- 
> 
> Steven

That's not totally true.  Your formulation is equivalent to a single-linked list, but a double-linked list can't be represented as an expression because it contains reference cycles.

Single and double-linked lists have the same requirements for inserting a new node.  For instance:

[a, [b, [c, [d, [e, None]]]]]
[a, [a2, [b, [c, [d, [e, None]]]]]]

However, to remove a node, the single-linked list requires iterating over the entire list to find the predecessor of the target, whereas the double-linked list already contains that information.

[a, [b, [c, [d, [e, None]]]]]
[a, [b, [c, [e, None]]]]

The difference might be moot in some applications, such as if we only remove nodes when we're already iterating.

Memory constraints were more severe 50 years ago when the structure was developed.  The difference between one pointer and two in a structure could have a big impact in repetition.  The single-linked list admits more easily of recursive algorithms as well.