logo

TechCodeview

循環単一リンクリストへの挿入

この記事では、循環リンク リストにノードを挿入する方法を学びます。挿入は、リストに新しいノードを追加するリンク リストの基本的な操作です。循環リンク リストでは、最後のノードが最初のノードに接続してループを作成します。

項目を追加するには主に 4 つの方法があります。

bash if ステートメント
  1. 空のリストへの挿入
  2. リストの先頭に挿入
  3. リストの最後に挿入
  4. リスト内の特定の位置に挿入

ヘッド ポインターの代わりにテール ポインターを使用する利点

リスト全体を走査して先頭にノードを挿入する必要があります。また、最後に挿入する場合は、リスト全体を走査する必要があります。の代わりに 始める pointer 最後のノードへのポインタを取得する場合、どちらの場合もリスト全体を走査する必要はありません。したがって、リストの長さに関係なく、先頭または末尾への挿入には一定の時間がかかります。



1. 循環リンクリスト内の空のリストへの挿入

空の循環リンク リストにノードを挿入すると、 新しいノード 指定されたデータを使用して、次のポインターがそれ自体を指すように設定し、 最後 これを参照するためのポインタ 新しいノード 。

循環リンクリスト内の空のリストへの挿入' title=空のリストへの挿入

段階的なアプローチ:

  • どうかを確認してください 最後 ではありません nullptr 。もし 真実 戻る 最後 (リストは空ではありません)。
  • それ以外の場合は、 新しいノード 提供されたデータを使用して。
    • を設定します。 新しいノードの それ自体を指す次のポインター (循環リンク)。
    • アップデート 最後 を指す 新しいノード そしてそれを返します。

空のリストへの挿入の詳細については、以下を参照してください。 循環リンク リスト内の空のリストへの挿入

2. 循環リンクリストの先頭に挿入

循環リンク リストの先頭に新しいノードを挿入するには

  • まず、 新しいノード そしてそれにメモリを割り当てます。
  • リストが空の場合 (最後のポインタが空であることによって示されます) NULL ) 私たちが作るのは、 新しいノード 自分自身を指します。
  • リストにすでにノードが含まれている場合は、 新しいノードの を指す次のポインタ 現在の頭 リストの（つまり 最後→次へ )
  • 次に、最後のノードの次のポインタを更新して、 新しいノード 。これにより、リストの循環構造が維持されます。
循環リンクリストの先頭への挿入' loading='lazy' title=循環リンクリストの先頭に挿入

先頭への挿入の詳細については、以下を参照してください。 循環リンクリストの先頭に挿入

3. 循環リンクリストの最後に挿入

循環リンク リストの最後に新しいノードを挿入するには、まず新しいノードを作成し、それにメモリを割り当てます。

JavaScript ドロップダウン
  • リストが空の場合 (つまり、 最後 または しっぽ ポインターであること NULL ) リストを次のように初期化します。 新しいノード そして、それ自体を指すようにして、円形の構造を形成します。
  • リストにすでにノードが含まれている場合は、 新しいノードの を指す次のポインタ 現在の頭 (つまり 末尾→次へ )
  • 次に、更新します 現在の尻尾 を指す次のポインタ 新しいノード 。
  • 最後に更新します テールポインタ に 新しいノード。
  • これにより、 新しいノード 今は 最後のノード 循環リンクを維持しながらリストに追加します。
循環リンクリストの末尾への挿入' loading='lazy' title=循環リンクリストの最後に挿入

最後に挿入について詳しくは、以下を参照してください。 循環リンクリストの最後に挿入

4. 循環リンクリストの特定位置への挿入

循環リンク リストの特定の位置に新しいノードを挿入するには、まずリストが空かどうかを確認します。

  • もしそうなら、そして 位置 ではありません 1 次に、その位置がリストに存在しないため、エラー メッセージを出力します。私
  • の 位置 は 1 次に、 新しいノード そしてそれ自体を指すようにします。
  • リストが空でない場合は、 新しいノード リストを走査して、正しい挿入ポイントを見つけます。
  • もし 位置 は 1 を挿入します 新しいノード 初めにポインタを適宜調整してください。
  • 他の位置については、目的の位置に到達するまでリストをたどって、 新しいノード ポインタを更新することによって。
  • 新しいノードが最後に挿入されると、 最後 リストの循環構造を維持する新しいノードを参照するためのポインタ。
循環リンクリストの特定位置への挿入' loading='lazy' title=循環リンクリストの特定の位置への挿入

段階的なアプローチ:

  • もし 最後 は nullptr そして 位置 ではありません 1 印刷' 無効な位置です! '。
  • それ以外の場合は、指定されたデータを使用して新しいノードを作成します。
  • 先頭に挿入: pos が 1 の場合、ポインターを更新して最後に戻ります。
  • トラバースリスト: ループして挿入ポイントを見つけます。 print '無効な位置です!'範囲外の場合。
  • ノードの挿入: ポインタを更新して新しいノードを挿入します。
  • 最後に更新: 更新の最後に挿入した場合 最後 。
C++ 
#include    using namespace std; struct Node{  int data;  Node *next;  Node(int value){  data = value;  next = nullptr;  } }; // Function to insert a node at a specific position in a circular linked list Node *insertAtPosition(Node *last int data int pos){  if (last == nullptr){  // If the list is empty  if (pos != 1){  cout << 'Invalid position!' << endl;  return last;  }  // Create a new node and make it point to itself  Node *newNode = new Node(data);  last = newNode;  last->next = last;  return last;  }  // Create a new node with the given data  Node *newNode = new Node(data);  // curr will point to head initially  Node *curr = last->next;  if (pos == 1){  // Insert at the beginning  newNode->next = curr;  last->next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr->next;    // If position is out of bounds  if (curr == last->next){  cout << 'Invalid position!' << endl;  return last;  }  }  // Insert the new node at the desired position  newNode->next = curr->next;  curr->next = newNode;  // Update last if the new node is inserted at the end  if (curr == last) last = newNode;  return last; } void printList(Node *last){  if (last == NULL) return;  Node *head = last->next;  while (true){  cout << head->data << ' ';  head = head->next;  if (head == last->next) break;  }  cout << endl; } int main(){  // Create circular linked list: 2 3 4  Node *first = new Node(2);  first->next = new Node(3);  first->next->next = new Node(4);  Node *last = first->next->next;  last->next = first;  cout << 'Original list: ';  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  cout << 'List after insertions: ';  printList(last);  return 0; }
C 
#include  #include  // Define the Node structure struct Node {  int data;  struct Node *next; }; struct Node* createNode(int value); // Function to insert a node at a specific position in a circular linked list struct Node* insertAtPosition(struct Node *last int data int pos) {  if (last == NULL) {  // If the list is empty  if (pos != 1) {  printf('Invalid position!n');  return last;  }  // Create a new node and make it point to itself  struct Node *newNode = createNode(data);  last = newNode;  last->next = last;  return last;  }  // Create a new node with the given data  struct Node *newNode = createNode(data);  // curr will point to head initially  struct Node *curr = last->next;  if (pos == 1) {  // Insert at the beginning  newNode->next = curr;  last->next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr->next;  // If position is out of bounds  if (curr == last->next) {  printf('Invalid position!n');  return last;  }  }  // Insert the new node at the desired position  newNode->next = curr->next;  curr->next = newNode;  // Update last if the new node is inserted at the end  if (curr == last) last = newNode;  return last; } // Function to print the circular linked list void printList(struct Node *last) {  if (last == NULL) return;  struct Node *head = last->next;  while (1) {  printf('%d ' head->data);  head = head->next;  if (head == last->next) break;  }  printf('n'); } // Function to create a new node struct Node* createNode(int value) {  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));  newNode->data = value;  newNode->next = NULL;  return newNode; } int main() {  // Create circular linked list: 2 3 4  struct Node *first = createNode(2);  first->next = createNode(3);  first->next->next = createNode(4);  struct Node *last = first->next->next;  last->next = first;  printf('Original list: ');  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  printf('List after insertions: ');  printList(last);  return 0; }
Java 
class Node {  int data;  Node next;  Node(int value){  data = value;  next = null;  } } public class GFG {  // Function to insert a node at a specific position in a  // circular linked list  static Node insertAtPosition(Node last int data  int pos){  if (last == null) {  // If the list is empty  if (pos != 1) {  System.out.println('Invalid position!');  return last;  }  // Create a new node and make it point to itself  Node newNode = new Node(data);  last = newNode;  last.next = last;  return last;  }  // Create a new node with the given data  Node newNode = new Node(data);  // curr will point to head initially  Node curr = last.next;  if (pos == 1) {  // Insert at the beginning  newNode.next = curr;  last.next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (int i = 1; i < pos - 1; ++i) {  curr = curr.next;  // If position is out of bounds  if (curr == last.next) {  System.out.println('Invalid position!');  return last;  }  }  // Insert the new node at the desired position  newNode.next = curr.next;  curr.next = newNode;  // Update last if the new node is inserted at the  // end  if (curr == last)  last = newNode;  return last;  }  static void printList(Node last){  if (last == null)  return;  Node head = last.next;  while (true) {  System.out.print(head.data + ' ');  head = head.next;  if (head == last.next)  break;  }  System.out.println();  }  public static void main(String[] args)  {  // Create circular linked list: 2 3 4  Node first = new Node(2);  first.next = new Node(3);  first.next.next = new Node(4);  Node last = first.next.next;  last.next = first;  System.out.print('Original list: ');  printList(last);  // Insert elements at specific positions  int data = 5 pos = 2;  last = insertAtPosition(last data pos);  System.out.print('List after insertions: ');  printList(last);  } }
Python 
class Node: def __init__(self value): self.data = value self.next = None # Function to insert a node at a specific position in a circular linked list def insertAtPosition(last data pos): if last is None: # If the list is empty if pos != 1: print('Invalid position!') return last # Create a new node and make it point to itself new_node = Node(data) last = new_node last.next = last return last # Create a new node with the given data new_node = Node(data) # curr will point to head initially curr = last.next if pos == 1: # Insert at the beginning new_node.next = curr last.next = new_node return last # Traverse the list to find the insertion point for i in range(1 pos - 1): curr = curr.next # If position is out of bounds if curr == last.next: print('Invalid position!') return last # Insert the new node at the desired position new_node.next = curr.next curr.next = new_node # Update last if the new node is inserted at the end if curr == last: last = new_node return last # Function to print the circular linked list def print_list(last): if last is None: return head = last.next while True: print(head.data end=' ') head = head.next if head == last.next: break print() if __name__ == '__main__': # Create circular linked list: 2 3 4 first = Node(2) first.next = Node(3) first.next.next = Node(4) last = first.next.next last.next = first print('Original list: ' end='') print_list(last) # Insert elements at specific positions data = 5 pos = 2 last = insertAtPosition(last data pos) print('List after insertions: ' end='') print_list(last)
JavaScript 
class Node {  constructor(value){  this.data = value;  this.next = null;  } } // Function to insert a node at a specific position in a // circular linked list function insertAtPosition(last data pos) {  if (last === null) {  // If the list is empty  if (pos !== 1) {  console.log('Invalid position!');  return last;  }  // Create a new node and make it point to itself  let newNode = new Node(data);  last = newNode;  last.next = last;  return last;  }  // Create a new node with the given data  let newNode = new Node(data);  // curr will point to head initially  let curr = last.next;  if (pos === 1) {  // Insert at the beginning  newNode.next = curr;  last.next = newNode;  return last;  }  // Traverse the list to find the insertion point  for (let i = 1; i < pos - 1; ++i) {  curr = curr.next;  // If position is out of bounds  if (curr === last.next) {  console.log('Invalid position!');  return last;  }  }  // Insert the new node at the desired position  newNode.next = curr.next;  curr.next = newNode;  // Update last if the new node is inserted at the end  if (curr === last)  last = newNode;  return last; } // Function to print the circular linked list function printList(last){  if (last === null)  return;  let head = last.next;  while (true) {  console.log(head.data + ' ');  head = head.next;  if (head === last.next)  break;  }  console.log(); } // Create circular linked list: 2 3 4 let first = new Node(2); first.next = new Node(3); first.next.next = new Node(4); let last = first.next.next; last.next = first; console.log('Original list: '); printList(last); // Insert elements at specific positions let data = 5; let pos = 2; last = insertAtPosition(last data pos); console.log('List after insertions: '); printList(last);

出力 
Original list: 2 3 4 List after insertions: 2 5 3 4

時間計算量: O(n) 特定の位置を見つけるにはリストを走査する必要があります。
補助スペース: ○(1)


クイズの作成