データ構造内の単一リンクリスト
サラ・チェン
⚡ スマートサマリー
単方向連結リストは、線形かつ一方向のデータ構造であり、各ノードはデータと次のノードへの単一のポインタを格納します。そのため、走査は先頭から末尾にのみ進み、新しいノードが追加されるにつれてメモリが動的に割り当てられます。
単一リンクリストとは何ですか?
単方向連結リストは、データがノードに保存され、各ノードがリンクを介して次のノードに接続される線形かつ単方向のデータ構造です。各ノードにはデータフィールドと次のノードへのリンクが含まれています。単方向連結リストは一方向にしか走査できませんが、 二重リンクリスト 両方向への通行が可能です。
単方向連結リストのノード構造は以下のとおりです。
リンクリスト内のノードの構造
配列ではなくリンクリストを使う理由とは？
いくつかのシナリオでは、リンクリストが 配列:
- 不明な要素数: コンパイル時に必要な要素数が不明な場合、リンクリストは要素が追加されるにつれて動的にメモリを割り当てます。
- ランダムアクセス： ランダムなインデックスアクセスが必要ない場合は、リンクリストが適切な選択肢となります。
- 途中で挿入: 配列の途中に要素を挿入するには、要素を移動させる必要があります。一方、リンクリストでは、わずかなポインタを書き換えるだけで、任意の位置に要素を挿入できます。
Opera単一リンクリストのオプション
単方向連結リストは、メモリを動的に割り当てるのに適しています。また、挿入、削除、検索、更新、2つのリストのマージ、走査など、連結リストの標準的な操作をサポートしています。
この記事では、以下の操作について説明します。
- 頭から挿入
- 末尾に挿入
- ノードの後に挿入する
- ノードの前に挿入する
- ヘッドノードを削除する
- 末尾ノードを削除する
- ノードの検索と削除
- リンクされたリストの走査
以下は、4つのノードを持つ連結リストの例です。
単一リンクリストの例
単方向連結リストの先頭への挿入
これは簡単な操作です。一般的には、単方向連結リストへの要素追加として知られています。新しいノードが作成され、リストの先頭に配置されます。
この操作を実行するには、次の2つの重要な条件を満たす必要があります。
- リストが空の場合、新しく作成されたノードがヘッドノードになり、その 次の ポインタがNULLです。
- リストが空でない場合、新しいノードがヘッドノードになり、その 次の ポインタは前の先頭ノードを指しています。
以下は、連結リストの先頭にノードを挿入するための擬似コードです。
function insertAtHead(head, value): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
先頭に挿入
単方向連結リストの末尾への挿入
連結リストの末尾にノードを挿入するのは、先頭に挿入するのと似ています。末尾ノードまでたどり、次にそのノードを に向けます。 次の 新しいノードへのポインタ。headがNULLの場合、新しいノードがheadになります。
ステップ1） 横断して 次の 現在のノードのポインタがNULLになります。
ステップ2） 指定された値で新しいノードを作成します。
ステップ3） 新しいノードを末尾ノードの次のノードとして割り当てます。
単一リストの末尾に挿入するための擬似コード：
function insertAtEnd(head, value): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: head = head.next head.next = newNode newNode.next = NULL
尾部に挿入
単方向連結リストのノードの後に挿入する
ノードの後に挿入する処理は、2つの段階から成ります。まず、目的のノードを検索し、次にそのノードの後に新しいノードを追加します。リストを走査して一致するノードが見つかったら、新しいノードを挿入します。
ステップ1） 現在のノードの値が検索項目と一致するまで走査する。
ステップ2） 新しいノードを設定します 次の 現在のノードへのポインタ 次の ポインター。
ステップ3） 現在のノードを指す 次の 新しいノードへのポインタ。
疑似コード:
function insertAfter(head, value, searchItem): newNode = Node(value) while head.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
単一リンクリスト内のノードの後にノードを挿入する
単方向連結リストのノードの前に挿入する
これはノードの後に挿入するのと似ています。次のノードが検索値と一致するまで走査し、その後、新しいノードをその前に挿入します。
ステップ1） 次のノードの値が検索項目と等しくなるまでトラバースします。
ステップ2） 新しいノードを作成し、その設定を行います。 次の 現在のノードへのポインタ 次の.
ステップ3） 現在のノードを指す 次の 新しいノードへ。
function insertBefore(head, value, searchItem): newNode = Node(value) while head.next.value != searchItem: head = head.next newNode.next = head.next head.next = newNode
単一リンクリストのノードの前にノードを挿入する
単方向連結リストの先頭要素を削除する
パラメータとしてヘッドポインタが渡されます。ヘッドノードが削除され、次のノードが新しいヘッドになります。メモリリークを防ぐため、削除されたノードのメモリは解放する必要があります。
ステップ1） 先頭の次のノードを新しい先頭として割り当てます。
ステップ2） 前のヘッドノードに割り当てられていたメモリを解放します。
ステップ3） 新しいヘッド ノードを返します。
function deleteHead(head): temp = head head = head.next free(temp) return head
リンクリストの先頭を削除する
単方向連結リストの末尾を削除する
末尾ノードの削除は、先頭ノードの削除と似ています。違いは、リストの末尾まで走査する必要があることです。単方向連結リストでは、末尾ノードは、 次の ポインタがNULLの場合は、末尾ノードです。
ステップ1） 末尾ノードの直前まで走査する。現在のノードを保存する。
ステップ2） 次のノード（末尾）のメモリを解放します。
ステップ3） 現在のノードの次のノードをNULLに設定します。
function deleteTail(head): while head.next.next is not NULL: head = head.next free(head.next) head.next = NULL
単一リンクリストの末尾の削除
単方向連結リストからノードを検索して削除する
この関数は、検索と削除の 2 つのタスクを実行します。リストの末尾まで走査します。一致するノードが見つかった場合は、それを削除し、前のノードを再リンクします。 次の ポインター。
ステップ1） リストの最後まで走査します。現在のノードが検索ノードと一致するかどうかを確認します。
ステップ2） 一致するものが見つかった場合は、現在のノードへのポインタを保存します。
ステップ3） その 次の 前のノードの が、現在のノードの次のノードになります。
ステップ4） 現在のノードを削除し、そのメモリを解放します。
function searchAndDelete(head, searchItem): while head.next.next is not NULL and head.next.value != searchItem: head = head.next temp = head.next head.next = head.next.next free(temp)
単一リンクリストからノードを検索して削除する
単方向連結リストを走査する
単方向連結リストは、先頭から末尾への走査のみをサポートします。前のノードへのポインタがないため、逆方向の走査は不可能です。各ノードは順番に訪問され、NULLに到達するまでその値が出力されます。
ステップ1） NULLに到達するまで各ノードを走査する。
ステップ2） 現在のノードの値を出力します。
function traverse(head): while head is not NULL: print head.value head = head.next
単方向リンクリストの例 C++
#include<iostream> using namespace std; struct Node{ int data; struct Node *next; }; void insertAtHead(Node* &head, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; if(head != NULL){ newNode->next = head; } head = newNode; cout<<"Added "<<newNode->data<<" at the front"<<endl; } void insertEnd(Node* &head, int value){ if(head == NULL){ insertAtHead(head, value); return; } Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *temp = head; while(temp->next != NULL){ temp = temp->next; } temp->next = newNode; cout<<"Added "<<newNode->data<<" at the end"<<endl; } void searchAndDelete(Node **headPtr, int searchItem){ Node *temp = NULL; if((*headPtr)->data == searchItem){ temp = *headPtr; *headPtr = (*headPtr)->next; free(temp); } else { Node *currentNode = *headPtr; while(currentNode->next != NULL){ if(currentNode->next->data == searchItem){ temp = currentNode->next; currentNode->next = currentNode->next->next; free(temp); break; } else { currentNode = currentNode->next; } } } cout<<"Deleted Node\t"<<searchItem<<endl; } void insertAfter(Node* &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next != NULL && head->data != searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl; } void insertBefore(Node* &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next != NULL && head->next->data != searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl; } void traverse(Node *headPointer){ Node* tempNode = headPointer; cout<<"Traversal from head:\t"; while(tempNode != NULL){ cout<<tempNode->data; if(tempNode->next) cout<<" --> "; tempNode = tempNode->next; } cout<<endl; } int main(){ Node *head = NULL; insertAtHead(head, 5); insertAtHead(head, 6); insertAtHead(head, 7); insertEnd(head, 9); traverse(head); searchAndDelete(&head, 6); traverse(head); insertAfter(head, 7, 10); insertBefore(head, 9, 11); traverse(head); }
出力
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 --> 6 --> 5 --> 9 Deleted Node 6 Traversal from head: 7 --> 5 --> 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 --> 10 --> 5 --> 11 --> 9
単方向リンクリストの例 Python
class Node: def __init__(self, data=None, next=None): self.data = data self.next = next class SinglyLinkedList: def __init__(self): self.head = None def insertAtHead(self, value): newNode = Node(data=value) if self.head is not None: newNode.next = self.head self.head = newNode print(f'Added {newNode.data} at the front.') def insertAtEnd(self, value): if self.head is None: self.insertAtHead(value) return newNode = Node(value) temp = self.head while temp.next is not None: temp = temp.next temp.next = newNode print(f'Added {newNode.data} at the end.') def searchAndDelete(self, searchItem): if self.head is None: return if self.head.data == searchItem: self.head = self.head.next print(f'Deleted node\t{searchItem}') return currentNode = self.head while currentNode.next is not None: if currentNode.next.data == searchItem: currentNode.next = currentNode.next.next print(f'Deleted node\t{searchItem}') return currentNode = currentNode.next def insertAfter(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} after node\t{searchItem}') def insertBefore(self, searchItem, value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.next.data != searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} before node\t{searchItem}') def traverse(self): temp = self.head print("Traversing from head:\t", end="") while temp: print("{}\t".format(temp.data), end="") temp = temp.next print() singlyLinkedList = SinglyLinkedList() singlyLinkedList.insertAtHead(5) singlyLinkedList.insertAtHead(6) singlyLinkedList.insertAtHead(7) singlyLinkedList.insertAtEnd(9) singlyLinkedList.traverse() singlyLinkedList.searchAndDelete(6) singlyLinkedList.traverse() singlyLinkedList.insertAfter(7, 10) singlyLinkedList.insertBefore(9, 11) singlyLinkedList.traverse()
出力
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
単連結リストの複雑さ
複雑さには、時間計算量と空間計算量の2種類があります。単方向連結リストの場合、最悪の場合と平均的な場合の時間計算量は同じです。
最良の場合の時間計算量:
- 先頭への挿入はO(1)で実行できます。リスト内部の走査は不要です。
- 対象要素が先頭ノードにある場合、検索と削除はO(1)で実行できます。
平均的な時間計算量：
- 連結リスト内への挿入にはO(n)かかる。 n は要素の総数です。
- 検索と削除もO(n)の計算量になる可能性がある。なぜなら、対象となる要素は末尾ノードまでのどこにでも存在する可能性があるからだ。
単方向連結リストの空間計算量
単方向連結リストは動的にメモリを割り当てます。 n 要素を割り当てる n メモリユニット。したがって、空間計算量はO(n)です。
単方向連結リストの応用例
単方向連結リストは、前方のみの走査と動的メモリが有用な多くの場面で使用されます。
- スタックとキュー： ノードから構築されるLIFOスタックおよびFIFOキューの基盤となるストレージ。
- ハッシュテーブルの連鎖： 衝突は、バケットごとにエントリを単方向連結リストに連結することで解決されます。
- 隣接リスト: 疎グラフは、各頂点に対して隣接ノードの単方向連結リストを使用します。
- シンボルテーブル: コンパイラとインタプリタは、スコープごとに識別子を連結して単方向連結リストを作成します。
- メモリ割り当て関数: 無料リスト割り当てツール track個の空きブロックを単方向連結リストとして格納します。
