データ構造内の単一リンクリスト

単一リンクリストとは何ですか?

単一リンク リストは線形の一方向データ構造であり、データはノードに保存され、各ノードはリンクを介して次のノードに接続されます。 各ノードにはデータ フィールドと次のノードへのリンクが含まれています。 単一リンク リストは一方向にのみトラバースできますが、二重リンク リストは両方向にトラバースできます。

単一リンクリストのノード構造は次のとおりです。

リンクリスト内のノードの構造
リンクリスト内のノードの構造

なぜ配列ではなくリンクされたリストを使用するのでしょうか?

リンク リストではなくリンク リストを使用した方が良い場合がいくつかあります。 配列。 いくつかのシナリオを次に示します。

  • 不明な要素数: プログラムの実行中に保存する必要がある要素の数がわからない場合は、リンク リストを使用できます。 リンクされたリストに要素を追加すると、メモリが動的に割り当てられます。
  • ランダムアクセス: 要素からのランダム アクセスを使用する必要がないシナリオでは、リンク リストを使用できます。
  • 途中で挿入: 配列の途中に要素を挿入するのは複雑な作業です。他の要素を右に押し出す必要があるためです。ただし、リンク リストを使用すると、任意の位置に要素を追加できます。

Opera単一リンクリストのオプション

単一リンク リストは、メモリを動的に割り当てるのに適しています。挿入、削除、検索、更新、2 つのリンク リストのマージ、トラバースなど、リンク リストのすべての基本操作を提供します。

ここでは、リンク リストの次の操作について説明します。

  • 頭から挿入
  • 末尾に挿入
  • ノードの後に​​挿入する
  • ノードの前に挿入する
  • ヘッドノードを削除する
  • 末尾ノードを削除する
  • ノードの検索と削除
  • リンクされたリストの走査

以下は XNUMX つのノードを持つリンク リストの例です。

単一リンクリストの例
単一リンクリストの例

単一リンクリストの先頭への挿入

これは簡単な操作です。一般的には、単一リンク リストのプッシュとして知られています。新しいノードを作成し、それをリンク リストの先頭に配置する必要があります。

この操作を実行するには、2つの重要な条件に従う必要があります。

  1. リストが空の場合、新しく作成されたノードがヘッド ノードとなり、ヘッドの次のノードは「NULL」になります。
  2. リストが空でない場合、新しいノードがヘッド ノードとなり、次のノードは前のヘッド ノードを指します。

リンク リストの先頭にノードを挿入するための疑似コードは次のとおりです。

function insertAtHead( head, value ):
	newNode = Node(value)
	if head is NULL:
		head = newNode
		return head
	else: 
		newNode.next = head
		return newNode
先頭に挿入する
先頭に挿入

単一リンクリストの末尾への挿入

リンクされたリストの最後にノードを挿入することは、先頭にノードを挿入することといくつかの類似点があります。 必要なのは、終了ノードまたは末尾ノードまでトラバースすることだけです。 次に、終了ノードの「次の」ノードが新しく作成されたノードを指すようにします。 ヘッド ノードが null の場合、新しいノードがヘッド ノードになります。

手順は次のとおりです。

ステップ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:
		then head = head.next
	head.next = newNode
	newNode.next = NULL
尾部に挿入する
尾部に挿入

単一リンクリスト内のノードの後に​​挿入

ノードの後の挿入には XNUMX つの部分があります。ノードを検索し、検索されたノードの後に​​接続します。 すべてのノードを横断する必要があります。 各ノードについて、検索要素と一致する必要があります。 一致するものがあれば、検索されたノードの後に​​新しいノードを追加します。

手順は次のとおりです。

ステップ1) 現在のノードの値が検索項目と等しくなるまで、次のノードをトラバースします。

ステップ2) 新しいノードの次のポインタは、現在のノードの次のポインタになります。

ステップ3) 現在のノードの次のノードが新しいノードになります。

ノードの後に​​ノードを挿入するための疑似コードは次のとおりです。

function insertAfter( head, value, searchItem ):
	newNode = Node(value)
	while head.value equals searchItem:
		then head = head.next
	newNode.next = head.next.next
	head.next = newNode
単一リンクリスト内のノードの後に​​ノードを挿入する
単一リンクリスト内のノードの後に​​ノードを挿入する

単一リンクリストのノードの前に挿入

この機能は、ノードの後の挿入によく似ています。 新しいノードを作成し、現在のノードが検索ノードと一致するまでリンク リストをたどる必要があります。 その後、新しいノードを現在のノードの前のノードとして追加します。

手順は次のとおりです。

ステップ1) 次のノードの値が検索項目と等しくなるまでトラバースします。

ステップ2) 新しいノードを作成し、そのノードの「次」に next を現在のノードの次のノードに割り当てます。

ステップ3) 新しいノードを現在のノードの次のノードとして割り当てます。

疑似コードは次のとおりです。

function insertBefore( head, value, searchItem ):
	newNode = Node(value)
	while head.next.value equals searchItem:
		then head = head.next
	newNode.next = head.next.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
単一リンクリストの末尾の削除
単一リンクリストの末尾の削除

単一リンクリストからノードを検索して削除します

この機能には、検索と削除という XNUMX つのタスクがあります。 単一リンクされたリストの最後まで検索する必要があります。 同様のノードが見つかった場合は、そのノードを削除します。 その後、削除したノードの左右のノードをマージまたはリンクする必要があります。 これを行う手順は次のとおりです。

ステップ1) リンクされたリストの最後までたどります。 現在のノードが検索ノードと等しいかどうかを確認します。

ステップ2) 一致するノードがある場合は、現在のノードへのノード ポインターを保存します。

ステップ3) 前のノードの「次」は、現在のノードの次のノードになります。

ステップ4) 現在のノードのメモリを削除して解放します。

単一リンクリストからノードを検索および削除するための疑似コード:

function searchAndDelete( head, searchItem ):
	while head.next.next is not NULL  and head.next.value is not equals searchItem :
		head = head.next
	head.next = head.next.next
	delete(head.next)
単一リンクリストからノードを検索して削除する
単一リンクリストからノードを検索して削除する

単一リンクリストを走査する

単一リンクリストには、先頭から末尾までを移動する機能のみがあります。 前のノードを指すポインターはありません。 そのため、単一リンク リストを逆の順序でたどることはできません。 各ノードを走査し、null が得られるまで現在のノードの値を出力します。

手順は次のとおりです。

ステップ1) 次のノードとして null が得られるまで、各ノードをトラバースします。

ステップ2) 現在のノードの値を出力します。

単一リンクリストを走査するための疑似コード:

function traverse( head ):
		while head.next is not NULL:
			print the value of the head
			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);
  }
  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 = new Node();
  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);
      }else{
        currentNode = currentNode->next;
      }
    }
  }
  cout<<"Deleted Node\t"<<searchItem<<endl;
  return;
}
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 = new 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 (AFCプログラム)

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.')
    return  
  def insertAtEnd(self,value):
    if self.head is None:
      self.insertAtHead(value)
    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):
    temp = Node()
    if self.head is searchItem:
      temp = self.head
      self.head = self.head.next
    else:
      currentNode = self.head
      while currentNode.next is not None:
        if currentNode.next.data is searchItem:
          temp = currentNode.next
          currentNode.next = currentNode.next.next
        else:
          currentNode = currentNode.next
    print(f'Deleted node\t{searchItem}')
    return
  def insertAfter(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} after node\t{searchItem}')
    return 
  def insertbefore(self,searchItem,value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data is not searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    print(f'Inserted {value} before node\t{searchItem}')
    return
  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) で実行できます。

平均的なケースの時間計算量:

  • 単一リンク リストに「n」個の要素が存在する場合、リンク リスト内への挿入には O(n) がかかります。
  • 検索要素が末尾ノードに存在する可能性があるため、検索と削除にも O(n) がかかります。 その場合は、リスト全体を調べる必要があります。

単一リンクリストの空間計算量

単一リンクリストは動的にメモリを割り当てます。n 個の要素を保存する場合、n 個のメモリ ユニットが割り当てられます。したがって、空間計算量は O(n) です。