Python 3 - Second Edition

14.4    Doubly Linked Lists

Let’s consider the following two variants of filling a list with the numbers from 0 to 9999. In the first version, the numbers are added one by one at the end of the list:

l = []for x in range(10000):    l.append(x)  

In the second variant, the numbers are inserted at the beginning of each list:

l = []for x in range(9999, -1, -1):    l.insert(0, x)  

Both examples generate the same list, but it turns out that the first variant runs much faster than the second one. This is due to the fact that the basic list data type has been optimized in terms of access via indexes and appending new elements to the end of the list. When inserting a value at the beginning of a list, all elements contained in the list must be recopied; that ...