단일 연결 목록 C++에 노드 삽입

Jinku Hu 2023년10월12일
  1. 연결된 목록의 끝에 노드를 삽입하는 함수 구현
  2. 연결된 목록에서 주어진 노드 뒤에 노드를 삽입하는 함수 구현
  3. 연결된 목록의 시작 부분에 노드를 삽입하는 함수 구현
단일 연결 목록 C++에 노드 삽입

이 기사에서는 C++의 단일 연결 목록에 새 노드를 삽입하는 방법을 설명합니다.

연결된 목록의 끝에 노드를 삽입하는 함수 구현

연결된 목록은 순차적으로 서로를 가리키는 노드로 구성된 선형 데이터 구조입니다. 이 기사에서는 단일 연결 목록 구조에 더 초점을 맞추고 그에 따라 여러 삽입 작업을 구현합니다.

단일 연결 목록에는 데이터 개체와 목록의 다음 노드에 대한 포인터가 있습니다. 목록 삽입 작업을 더 잘 보여주기 위해ListNode라는 노드 구조와 두 개의 도우미 함수 (freeNodesprintNodes)를 정의했습니다. 삽입 작업 시간 복잡도는 노드를 삽입하는 위치에 따라 다릅니다. 예를 들어, 목록의 끝을 알 수없는 경우 목록 끝에 삽입하는 데 선형 시간이 걸립니다.

반면에 처음에 새 노드를 삽입하는 것은 항상 일정한 시간이 걸립니다. 다음 코드는 목록을 구성하는 핵심 함수로 취급 할 수있는insertNodeEnd함수를 보여줍니다. 목록의 헤드를 첫 번째 매개 변수로 사용하고 새 노드에 저장해야하는string데이터를 사용합니다. 이 함수는 목록의 첫 번째 요소를 만들고 그 끝에 새 요소를 추가 할 수 있습니다. 이 함수는 여유 저장 메모리에 새 노드를 할당합니다. 따라서freeNodes기능은 프로그램 종료 전에 모든 메모리를 해제하는 데 필요합니다.

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeEnd(head, "Utopic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

출력:

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic

연결된 목록에서 주어진 노드 뒤에 노드를 삽입하는 함수 구현

목록 중간에 노드를 삽입하려면 일반적으로 일정한 시간과 주어진 위치를 찾는 데 사용되는 검색 알고리즘의 시간 복잡성이 필요합니다. 그러나 검색 기능이 별도로 구현되었다고 가정하고insertNodeAfter함수를 구성하여 대상 노드의 위치를 ​​첫 번째 인수로 제공해야합니다.

insertNodeEnd함수는 새로 추가 된 노드에 대한 포인터를 반환하므로 반환 값을 사용하여insertNodeAfter의 작업을 보여줍니다. 임의의 위치 삽입을 위해 별도의 검색 기능이 필요하며 링크 된 목록에서 더 빠른 검색 작업을 구현하기 위해 외부 데이터 구조가 필요할 수도 있습니다.

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

struct ListNode *insertNodeAfter(struct ListNode *prev, string data) {
  if (!prev) return nullptr;

  auto new_node = new ListNode;
  new_node->next = nullptr;
  new_node->data = std::move(data);
  prev->next = new_node;
  return new_node;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  auto iter = insertNodeEnd(head, "Utopic");
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeAfter(iter, "Xenial");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

출력:

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
 -----------------------------------
node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
node 4 - data: Utopic
node 5 - data: Xenial

연결된 목록의 시작 부분에 노드를 삽입하는 함수 구현

단일 연결 목록에 대한 또 다른 유용한 삽입 작업은 처음에 새 노드를 추가하는 것입니다. 이 함수는 목록 자체에 액세스하기 위해 항상 목록의 헤드가 저장되므로 가장 좋은 실행 시간O(1)를 갖습니다. insertNodeFront함수는 루트 포인터와 노드에 저장해야하는string객체에 대한 참조를 가져옵니다. 이 프로세스는 새로운 연결 목록과 전면 삽입을 초기화하는 데 사용할 수 있도록 구현됩니다.

또는root인수가nullptr가 아닌 경우 새 노드를 할당하도록 함수를 다시 작성할 수 있습니다. 그렇지 않으면nullptr를 반환하여 함수가 실패했음을 나타냅니다. 이러한 함수의 인터페이스는 프로그래머의 요구와ListNode의 구조에 따라 다릅니다.

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next{};
  string data;
};

struct ListNode *insertNodeEnd(struct ListNode *root, string data) {
  auto new_node = new ListNode;
  if (root) {
    while (root->next) root = root->next;

    new_node->next = nullptr;
    new_node->data = std::move(data);
    root->next = new_node;

    return root->next;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

struct ListNode *insertNodeFront(struct ListNode *&root, string data) {
  auto new_node = new ListNode;
  if (root) {
    new_node->next = root;
    new_node->data = std::move(data);
    root = new_node;
    return root;
  }
  new_node->next = nullptr;
  new_node->data = std::move(data);
  return new_node;
}

void freeNodes(struct ListNode *root) {
  struct ListNode *tmp = nullptr;
  while (root) {
    tmp = root;
    root = root->next;
    delete tmp;
  }
}

void printNodes(struct ListNode *node) {
  auto count = 0;
  while (node) {
    cout << "node " << count << " - data: " << node->data << endl;
    node = node->next;
    count++;
  }
}

int main() {
  struct ListNode *head = nullptr;

  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  head = insertNodeEnd(head, data_set.at(0));
  for (auto it = data_set.begin() + 1; it != data_set.end(); ++it) {
    insertNodeEnd(head, *it);
  }
  printNodes(head);
  cout << " ----------------------------------- " << endl;

  insertNodeFront(head, "Bionic");
  printNodes(head);

  freeNodes(head);
  return EXIT_SUCCESS;
}

출력:

node 0 - data: Precise
node 1 - data: Quantal
node 2 - data: Saucy
node 3 - data: Raring
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
작가: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

관련 문장 - C++ Data Structure