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

Question

I have already seen Create an empty list in python with certain size - Stack Overflow; but I just wanted to confirm - consider this MWE:

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

outputA = []

for ix in data:
  print ix[0] # x1, x2
  for isnip in ix[1]:
    outputA.append(isnip)

print outputA
# [(3, 'a'), (1, 'b'), (5, 'c'), (2, 'a'), (4, 'b')]

outputB = []

for ix in data:
  print ix[0] # x1, x2
  for 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) #[]
for ix in data:
  print ix[0] # x1, x2
  for isnip in ix[1]:
    outputC[isnip[0]] = isnip

print outputC
# [None, (1, 'b'), (2, 'a'), (3, 'a'), (4, 'b'), (5, 'c')]

I have data where there are 2D tuples (actually, in my real case, dicts, but nevermind that), whose first element is an ordering index; they are unsorted, and I need them sorted. However, they are at all possible levels of nesting (I have simplified data above for an easier example; in my real situation they can be nested even further), so I cannot easily issue a "sorted" command.

So I thought about inserting elements - as you can see, I cannot get .insert() to preserve the order. So I thought then about explicit assignment - and that works, but only if the list is sized beforehand; and to find the size, I still would have to go through an extra recursion, just to discover what the maximum index is.

Thus, I would like to insert at exact location (not "before" like .insert() does) of a list, but without explicitly sizing the list beforehand - is there any way that this can be achieved?

---

EDIT: Here is something more like my actual data, showing (hopefully) why it would be difficult to sort it:

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

outputA = []

for ix in data:
  #print "[0]", ix[0], "[1]", ix[1] # x1, x2, x100
  try:
    for 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:
      for 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 = []

for ix in data:
  try:
    for isnip in ix[1]:
      if int(isnip[0]) == isnip[0]:
        outputB.insert(isnip[0]+1, isnip)
      else:
        raise Exception("not good")
  except:
    try:
      for 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')]

Answer 1

Think about your data as a tree:

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

I added a root node to bring it into a consistent format. What constitues a leaf in that tree?

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

Now you can just run a simple depth-first search to get the leaves in preorder:

def dfs(x):
    if isleaf(x):
        yield x
        return
    for y in x[1]: 
        yield from 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 be extended to any other tree-like data.

UPDATE: If you absolutely must avoid the sorting step for some reason, you can just collect the results in a dict and construct the array afterwards.

d = {}

def dfs(x):
    if isleaf(x):
        d[x[0]] = x
        return
    for y in x[1]: 
        dfs(y)
dfs(data)

res = [None] * (max(d) + 1)
for i, v in d.items():
    res[i] = v