linkedListPython (おそらく 2.7) に組み込みのデータ構造があるかどうかは誰にもわかりませんか? キューはリストを使用して実装されており、スタックはありません (LIFO キューがあります)。
質問する
19069 次
5 に答える
6
特定の目的のために明示的な連結リスト構造が実際に必要でない限り、Python の組み込みリストには、連結リストから得られるすべての機能があります。たとえば、次のようにスタックとして使用できます。
>>> x = []
>>> x.append(1)
>>> x.append(2)
>>> x
[1, 2]
>>> x.pop()
2
>>> x
[1]
>>>
または、特定の要素の後に要素を挿入するには:
>>> x = [1,2,3,4,5,6,7]
>>> x.insert(3,"a")
>>> x
[1, 2, 3, 'a', 4, 5, 6, 7]
>>>
たとえば、データ構造に関する Python ドキュメントを参照してください。
ただし、これは「リスト」抽象データ型 ( ADT ) を使用しています。対照的に、「リンクされたリスト」は ADT ではなく、その ADT を実装する多くの可能な方法の 1 つです。
collections.deque前置の効率が問題である場合、Łukasz Rogalski の回答は、リンクされたリストを使用して実装されていることを指摘しています。リストをキューとして使用する際の注意事項:
リストをキューとして使用することもできます。この場合、最初に追加された要素が最初に取得された要素になります (「先入れ先出し」)。ただし、リストはこの目的には効率的ではありません。リストの末尾からの追加とポップは高速ですが、リストの先頭からの挿入またはポップは低速です (他のすべての要素を 1 つシフトする必要があるため)。
キューを実装するには、両端から高速に追加およびポップできるように設計された collections.deque を使用します。
を使用した場合と を使用した場合の効率の影響をテストするために、次のプログラムを使用しましたlist。deque
import timeit, sys
print ("append to list: %f" % (timeit.timeit ('x.append("x")', 'x = ["y"]')))
print ("insert to list element 0: %f" % (timeit.timeit ('x.insert(0,"x")', 'x = ["y"]')))
print ("append to deque: %f" % (timeit.timeit ('x.append("x")', 'import collections; x = collections.deque(["a","b","c"])')))
print ("append left to deque: %f" % (timeit.timeit ('x.appendleft("x")', 'import collections; x = collections.deque(["a","b","c"])')))
if (sys.version_info[0]+sys.version_info[1]/10) > 3.4999:
print ("insert in deque: %f" % (timeit.timeit ('x.insert(2,"x")', 'import collections; x = collections.deque(["a","b","c"])')))
...そして、Python 3.6 と Python 2.7 で次の結果が得られました。
$ python3 testList.py
append to list: 0.113031
insert to list element 0: 191.147079
append to deque: 0.058606
append left to deque: 0.064640
insert in deque: 0.160418
$ python testList.py
append to list: 0.102542
insert to list element 0: 191.128508
append to deque: 0.083397
append left to deque: 0.064534
したがって、list要素を追加するのに約 2 倍の時間がかかり、追加するよりも前に追加する (つまり、左に追加する) 時間がかかりませんdeque。deque
于 2013-02-03T02:12:43.667 に答える
5
collections パッケージの deque クラスは、ヘッドガードとテールガードを備えた二重リンクリストとして実装されていると思います。デフォルト リストのすべての通常の API をサポートします。先頭に追加するには、leftappend関数を使用します。
from collections import deque
于 2015-04-26T08:57:58.567 に答える
4
Pythonには組み込みのリンクリストはありませんが、デキューを使用できます。これにより、ヘッドとテールの両方にアクセスできますが、独自のリンクリストを実装したい場合は、使用できます
于 2013-02-03T02:09:43.643 に答える