How to add an element to the beginning of an OrderedDict?

I have this:

    d1 = OrderedDict([('a', '1'), ('b', '2')])

If I do this:


Then I get this:

    OrderedDict([('a', '1'), ('b', '2'), ('c', '3')])

but I want this:

    [('c', '3'), ('a', '1'), ('b', '2')]

without creating new dictionary.

There's no built-in method for doing this in Python 2. If you need this, you need to write a prepend() method/function that operates on the OrderedDict internals with O(1) complexity.

For Python 3.2 and later, you should use the move_to_end method. The method accepts a last argument which indicates whether the element will be moved to the bottom (last=True) or the top (last=False) of the OrderedDict.

Finally, if you want a quick, dirty and slow solution, you can just create a new OrderedDict from scratch.

Details for the four different solutions:

Extend OrderedDict and add a new instance method

    from collections import OrderedDict

    class MyOrderedDict(OrderedDict):

        def prepend(self, key, value, dict_setitem=dict.__setitem__):

            root = self._OrderedDict__root
            first = root[1]

            if key in self:
                link = self._OrderedDict__map[key]
                link_prev, link_next, _ = link
                link_prev[1] = link_next
                link_next[0] = link_prev
                link[0] = root
                link[1] = first
                root[1] = first[0] = link
                root[1] = first[0] = self._OrderedDict__map[key] = [root, first, key]
                dict_setitem(self, key, value)


    >>> d = MyOrderedDict([('a', '1'), ('b', '2')])
    >>> d
    MyOrderedDict([('a', '1'), ('b', '2')])
    >>> d.prepend('c', 100)
    >>> d
    MyOrderedDict([('c', 100), ('a', '1'), ('b', '2')])
    >>> d.prepend('a', d['a'])
    >>> d
    MyOrderedDict([('a', '1'), ('c', 100), ('b', '2')])
    >>> d.prepend('d', 200)
    >>> d
    MyOrderedDict([('d', 200), ('a', '1'), ('c', 100), ('b', '2')])

Standalone function that manipulates OrderedDict objects

This function does the same thing by accepting the dict object, key and value. I personally prefer the class:

    from collections import OrderedDict

    def ordered_dict_prepend(dct, key, value, dict_setitem=dict.__setitem__):
        root = dct._OrderedDict__root
        first = root[1]

        if key in dct:
            link = dct._OrderedDict__map[key]
            link_prev, link_next, _ = link
            link_prev[1] = link_next
            link_next[0] = link_prev
            link[0] = root
            link[1] = first
            root[1] = first[0] = link
            root[1] = first[0] = dct._OrderedDict__map[key] = [root, first, key]
            dict_setitem(dct, key, value)


    >>> d = OrderedDict([('a', '1'), ('b', '2')])
    >>> ordered_dict_prepend(d, 'c', 100)
    >>> d
    OrderedDict([('c', 100), ('a', '1'), ('b', '2')])
    >>> ordered_dict_prepend(d, 'a', d['a'])
    >>> d
    OrderedDict([('a', '1'), ('c', 100), ('b', '2')])
    >>> ordered_dict_prepend(d, 'd', 500)
    >>> d
    OrderedDict([('d', 500), ('a', '1'), ('c', 100), ('b', '2')])

Use OrderedDict.move_to_end() (Python >= 3.2)

Python 3.2 introduced the OrderedDict.move_to_end() method. Using it, we can move an existing key to either end of the dictionary in O(1) time.

    >>> d1 = OrderedDict([('a', '1'), ('b', '2')])
    >>> d1.update({'c':'3'})
    >>> d1.move_to_end('c', last=False)
    >>> d1
    OrderedDict([('c', '3'), ('a', '1'), ('b', '2')])

If we need to insert an element and move it to the top, all in one step, we can directly use it to create a prepend() wrapper (not presented here).

Create a new OrderedDict - slow!!!

If you don't want to do that and performance is not an issue then easiest way is to create a new dict:

    from itertools import chain, ifilterfalse
    from collections import OrderedDict

    def unique_everseen(iterable, key=None):
        "List unique elements, preserving order. Remember all elements ever seen."
        # unique_everseen('AAAABBBCCDAABBB') --> A B C D
        # unique_everseen('ABBCcAD', str.lower) --> A B C D
        seen = set()
        seen_add = seen.add
        if key is None:
            for element in ifilterfalse(seen.__contains__, iterable):
                yield element
            for element in iterable:
                k = key(element)
                if k not in seen:
                    yield element

    d1 = OrderedDict([('a', '1'), ('b', '2'),('c', 4)])
    d2 = OrderedDict([('c', 3), ('e', 5)])   #dict containing items to be added at the front
    new_dic = OrderedDict((k, d2.get(k, d1.get(k))) for k in \
                                               unique_everseen(chain(d2, d1)))
    print new_dic


    OrderedDict([('c', 3), ('e', 5), ('a', '1'), ('b', '2')])