KeyedList

[pataphor]

The ordered dictionary discussion made me think of another data type
which seems to be somewhat related, a kind of ordered dictionary where
the order of the items is arbitrary. One can insert items in the middle
and still have O(1) access (I think). I have provided a very basic
implementation, it could be extended to also remove items with O(1)
access. I am wondering if the idea makes sense at all and what would be
the best name for the type itself and for its methods. 

Could it be that the ordered dictionary is a result of a way of
thinking which slowly extends what we currently have, while a
KeyedList or whatever we ultimately choose to name it is the kind of
data type we are really looking for? If accepted, I think this type
could be used for Knuth's dancing links style algorithms.

P.

#warning, embryonic, probably very buggy implementation

class Node:
    
    def __init__(self, left = None, right = None, key = None, item =
None): self.left = left
        self.right = right
        self.key = key
        self.item = item

class KeyedList:
    
    def __init__(self):
        self.first = Node()
        self.last = Node()
        self.last.left = self.first
        self.first.right = self.last
        self.D = {}
    
    def append(self, key, item):
        last = self.last
        prev = last.left
        x = Node(prev,last,key,item)
        prev.right = x
        last.left = x
        self.D[key] = x
    
    def insertafter(self,key1,key2,item):
        left = self.D[key1]
        right = left.right
        x = Node(left,right,key2,item)
        left.right =x
        right.left =x
        self.D[key2] = x
    
    def iteritems(self):
        x = self.first.right
        while x.right:
            key = x.key
            yield key, self.D[key].item
            x = x.right
        
def test():
    K = KeyedList()
    K.append('one','hello')
    K.append('two','hello')
    K.append('four','hello')
    K.insertafter('two','three','hello')
    for x in K.iteritems():
        print x
    
if __name__ == '__main__':
    test()