Dlaczego Python nie ma natywnej implementacji listy powiązanej?

Question

Próbowałem szybkiego eksperymentu porównującego wydajność natywnych list Pythona z połączonymi implementacjami list, takimi jak this.

Natywne listy pytonów są zawsze szybsze niż nieodłączna lista linków w przypadkach, w których nie powinny być (zgodnie z teorią).

from linkedlist import * 
import time 
a = LinkedList() 
b = [] 
for i in range(1000000): 
    b.append(i) 
    a.add_first(i) 
t0 = time.clock() 
a.remove(10) 
t1 = time.clock() 
b.remove(10) 
t2 = time.clock() 
print t1-t0 
print t2-t1 

Wyniki mam na teście powyżej są:

• rodzimy powiązany list = lista pyton 2.00000000001e-05

• = 0,005576

• non rodzimy powiązany listy = 3.90000000001e-05

Tak więc zastanawiałem się, dlaczego Python nie ma macierzystej struktury danych Linked List. W przypadku Pythona, wygląda na to, że użyteczna może być analiza algorytmiczna, aby mieć listę połączoną zamiast standardowych list, aby przyspieszyć niektóre aspekty standardowej biblioteki.

Rozumiem, że struktura danych Lista jest kluczowym elementem składowym języka, a to sprawia, że ​​kod jest łatwiejszy w utrzymaniu i łatwy do optymalizacji, aby skupić się na tej właśnie strukturze danych.

Czy jest jakikolwiek inny powód?

Answer 1

Python ma collections.deque, która jest natywną podwójnie linkowaną listą.

Answer 2

Dzieje się tak tylko dlatego, że lista budynków zajmuje większą część czasu niż metoda dołączania. Tak więc, jeśli nie jest to liniowa operacja czasu, jak pokazałeś, (metoda: n^2) metoda append będzie bardziej znacząca niż budowa, która doprowadzi do wyniku, który chcesz zobaczyć.