片方向リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)
片方向リスト（singly-linked list）は、最も単純な連結リストであり、ノード毎に1つのリンクを持つ。このリンクはリスト上の次のノードを指し、リストの最後尾ならNull値を格納するか、空のリストを指す。 3つの整数値を格納した片方向リスト
※この「片方向リスト」の解説は、「連結リスト」の解説の一部です。
「片方向リスト」を含む「連結リスト」の記事については、「連結リスト」の概要を参照ください。
片方向リスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 20:30 UTC 版)
ここでのノードのデータ構造には2つのフィールドがある。また、List の "firstNode" というフィールドがリストの先頭ノード（空のリストの場合は "null"）を指すとする。 record Node { data // ノードに格納されるデータ next // 次のノードへの参照（最後尾の場合は null） } record List { Node firstNode // リストの先頭ノードを指す（空のリストの場合は null） } 片方向リストを辿るのは単純で、先頭ノードから各ノードの "next" リンクを最後まで辿っていく。 node := list.firstNode while node ≠ null { (node.data に何かをする) node := node.next } 次のコードは片方向リスト上のあるノードの次に新たにノードを挿入する。あるノードの前にノードを挿入することはできない。その場合は挿入位置の前のノードを見つける必要がある。 function insertAfter(Node node, Node newNode) { // newNode を node の次に挿入 newNode.next := node.next node.next := newNode } リストの先頭にノードを追加する場合、別の関数が必要である。この場合、firstNode を更新しなければならない。 function insertBeginning(List list, Node newNode) { // 現在の先頭ノードの前にノードを挿入 newNode.next := list.firstNode list.firstNode := newNode } 同様に、指定されたノードの次のノードを削除する関数と、リストの先頭のノードを削除する関数を示す。特定のノードを探して削除する場合、その前のノードを覚えておく必要がある。 function removeAfter(Node node) { // このノードの次のノードを削除 obsoleteNode := node.next node.next := node.next.next destroy obsoleteNode } function removeBeginning(List list) { // 先頭ノードを削除 obsoleteNode := list.firstNode list.firstNode := list.firstNode.next // 削除されるノードの次を指す destroy obsoleteNode } removeBeginning() は、削除するノードが最後のノードだった場合、"list.firstNode" を "null" にする。 逆方向に繰り返すことができないので、"insertBefore" や "removeBefore" といった操作を効率的に実装することはできない。 2つの片方向リストを連結したい場合、リストの最後尾を常に保持していないと効率的に処理できない。2つのリストがそれぞれ長さ n {\displaystyle n} である場合、連結にかかる時間は O ( n ) {\displaystyle O(n)} となる。LISP 系言語では、リストの連結には append を使う。 片方向リストの操作は先頭ノードの扱いが特殊であるが、先頭にダミー要素を追加することでこれを排除できる。これによって、"insertBeginning()" や "removeBeginning()" が不要となる。この場合、最初のデータを持ったノードは "list.firstNode.next" で参照可能である。
※この「片方向リスト」の解説は、「連結リスト」の解説の一部です。
「片方向リスト」を含む「連結リスト」の記事については、「連結リスト」の概要を参照ください。
- 片方向リストのページへのリンク
