Inserting an element in list, at exact location, without array sizing in Python? -

i have seen create empty list in python size - stack overflow; wanted confirm - consider mwe:

data = ( ( "x1", ( (3, "a"), (1, "b"),  (5, "c") )  ), ( "x2", ( (2, "a"), (4, "b") )  ) )  outputa = []  ix in data:   print ix[0] # x1, x2   isnip in ix[1]:     outputa.append(isnip)  print outputa # [(3, 'a'), (1, 'b'), (5, 'c'), (2, 'a'), (4, 'b')]  outputb = []  ix in data:   print ix[0] # x1, x2   isnip in ix[1]:     outputb.insert(isnip[0], isnip)  print outputb # [(3, 'a'), (1, 'b'), (2, 'a'), (5, 'c'), (4, 'b')]  outputc = [none] * (5+1) #[] ix in data:   print ix[0] # x1, x2   isnip in ix[1]:     outputc[isnip[0]] = isnip  print outputc # [none, (1, 'b'), (2, 'a'), (3, 'a'), (4, 'b'), (5, 'c')] 

i have data there 2d tuples (actually, in real case, dicts, nevermind that), first element ordering index; unsorted, , need them sorted. however, @ possible levels of nesting (i have simplified data above easier example; in real situation can nested further), cannot issue "sorted" command.

so thought inserting elements - can see, cannot .insert() preserve order. thought explicit assignment - , works, if list sized beforehand; , find size, still have go through recursion, discover maximum index is.

thus, insert @ exact location (not "before" .insert() does) of list, without explicitly sizing list beforehand - there way can achieved?

---

edit: here more actual data, showing (hopefully) why difficult sort it:

data = ( ( "x1", ( (3, "a"), (1, "b"),  (5, "c") )  ), ( "x2", ( "x3", ( (2, "a"), (4, "b") ) )  ), ("x100", 1 ) )  outputa = []  ix in data:   #print "[0]", ix[0], "[1]", ix[1] # x1, x2, x100   try:     isnip in ix[1]:       #print "isnip", isnip[0], "-", isnip[1]       if int(isnip[0]) == isnip[0]:         outputa.append(isnip)       else:         raise exception("not good")   except:     try:       isnip in ix[1][1]:         #print "isnip", isnip[0], "-", isnip[1]         if int(isnip[0]) == isnip[0]:           outputa.append(isnip)     except:       #print "skipping this"       pass  print outputa # [(3, 'a'), (1, 'b'), (5, 'c'), (2, 'a'), (4, 'b')]  outputb = []  ix in data:   try:     isnip in ix[1]:       if int(isnip[0]) == isnip[0]:         outputb.insert(isnip[0]+1, isnip)       else:         raise exception("not good")   except:     try:       isnip in ix[1][1]:         #print "isnip", isnip[0], "-", isnip[1]         if int(isnip[0]) == isnip[0]:           outputb.insert(isnip[0]+1, isnip)     except:       #print "skipping this"       pass  print outputb # [(3, 'a'), (1, 'b'), (5, 'c'), (2, 'a'), (4, 'b')] 

think data tree:

data = ( "x", (           ( "x1", (              (3, "a"),              (1, "b"),                (5, "c"))),            ( "x2", (               (2, "a"),               (4, "b"))))) 

i added root node bring consistent format. constitues leaf in tree?

def isleaf(x):           return not isinstance(x[1], tuple) 

now can run simple depth-first search leaves in preorder:

def dfs(x):     if isleaf(x):         yield x         return     y in x[1]:          yield dfs(y) 

example:

>>> list(dfs(data)) [(3, 'a'), (1, 'b'), (5, 'c'), (2, 'a'), (4, 'b')] >>> sorted(dfs(data), key=lambda x: x[0]) [(1, 'b'), (2, 'a'), (3, 'a'), (4, 'b'), (5, 'c')] 

this can extended other tree-like data.

update: if absolutely must avoid sorting step reason, can collect results in dict , construct array afterwards.

d = {}  def dfs(x):     if isleaf(x):         d[x[0]] = x         return     y in x[1]:          dfs(y) dfs(data)  res = [none] * (max(d) + 1) i, v in d.items():     res[i] = v