"DoublyLinkedList" (データ構造)

"DoublyLinkedList"

要素が一般式である双方向連結リストを表す．

詳細

  • 双方向連結リストは，効率的に最初と最後の位置に要素を加えたり，最初と最後の位置から要素を削除したりするのに役立つ．
  • CreateDataStructure["DoublyLinkedList"]新しい空の "DoublyLinkedList"を作成する
    CreateDataStructure["DoublyLinkedList",elems]elems を含む新しい"DoublyLinkedList" を作成する
    Typed[x,"DoublyLinkedList"]x に"DoublyLinkedList"型を与える
  • "DoublyLinkedList"型のデータ構造には，以下の演算が使える．
  • ds["Append",x]x を ds に加えるtime: O(1)
    ds["Copy"]ds のコピーを返すtime: O(n)
    ds["DropAll"]ds からすべての要素を省くtime: O(n)
    ds["DropFirst"]ds の最初の要素を省くtime: O(1)
    ds["DropLast"]ds の最後の要素を省くtime: O(1)
    ds["Elements"]ds の要素のリストを返すtime: O(n)
    ds["EmptyQ"]ds が要素を持たない場合はTruetime: O(1)
    ds["Fold",fun,init]fun を ds の要素に適用する．init で始めて，結果を累積するtime: O(n)
    ds["JoinBack",elems]elems を ds の後ろに繋げるtime: O(nelems)
    ds["JoinFront",elems]elems を ds の前に繋げるtime: O(nelems)
    ds["Length"]ds に保存される要素の数time: O(1)
    ds["Part",i]ds の i 番目の部分を返すtime: O(n)
    ds["Prepend",x]x を ds の先頭に追加するtime: O(1)
    ds["SetPart",i,elem]ds の i 番目の部分を更新するtime: O(n)
    ds["SwapPart",i,j]ds の i 番目と j 番目の部分を交換するtime: O(n)
    ds["Visualization"]ds の可視化を返すtime: O(n)
  • 以下の関数もサポートする．
  • dsi===dsjdsi が dsj に等しい場合はTrue
    ds["Part",i]=valds の i 番目の要素を val に設定する
    FullForm[ds]ds の完全形
    Information[ds]ds についての情報
    InputForm[ds]ds の入力形
    Normal[ds]ds を通常の式に変換する

例題

すべて開くすべて閉じる

例  (2)

新しい"DoublyLinkedList"は，CreateDataStructureを使って作成できる：

要素は加えることができる：

要素は先頭に追加することができる：

長さを返す：

最初の要素を抽出する：

要素を変更する：

要素が更新された：

式バージョンの ds を返す：

最後の要素を省略する：

素早く加えることができる：

データ構造の可視化を生成することができる：

全要素を合計する：

スコープ  (1)

情報  (1)

新しい"DoublyLinkedList"は，CreateDataStructureを使って作成することができる：

データ構造 ds についての情報：