연결리스트

연결리스트는 데이터와 다음 데이터의 주소를 가지고 있는 노드들이 연결되어 있는 자료구조입니다. 연결리스트는 데이터를 추가하거나 삭제하기 쉽다는 장점이 있습니다. 연결리스트에는 단일 연결리스트, 이중 연결리스트, 환형 연결리스트 등이 있습니다.

연결리스트를 구현하려면 먼저 노드 구조체를 만들어야 합니다. 노드 구조체는 데이터와 다음 노드를 가리키는 포인터를 멤버로 가지고 있습니다.

 

예제)

노드를 이용하여 정수형 연결 리스트를 구현하는 예제입니다.

#include <iostream>
using namespace std;

// 정수형 연결 리스트 노드 클래스
class Node {
  public:
    int data;
    Node *next;
};

// 노드 추가 함수
void addNode(Node **head, int data) {
  Node *newNode = new Node();
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

// 노드 삭제 함수
void deleteNode(Node **head, int data) {
  Node *prev = nullptr;
  Node *curr = *head;

  // 삭제할 데이터를 찾아서 노드 삭제
  while (curr != nullptr && curr->data != data) {
    prev = curr;
    curr = curr->next;
  }

  if (curr == nullptr) {
    // 삭제할 데이터가 없는 경우
    return;
  } else if (prev == nullptr) {
    // 삭제할 데이터가 첫 번째 노드인 경우
    *head = curr->next;
  } else {
    // 삭제할 데이터가 중간 또는 마지막 노드인 경우
    prev->next = curr->next;
  }

  // 노드 메모리 반환
  delete curr;
}

// 연결 리스트 출력 함수
void printList(Node *head) {
  Node *curr = head;
  while (curr != nullptr) {
    cout << curr->data << " ";
    curr = curr->next;
  }
  cout << endl;
}

void main() {
  // 노드 추가
  Node *head = nullptr;
  addNode(&head, 3);
  addNode(&head, 2);
  addNode(&head, 1);

  // 리스트 출력
  cout << "List: ";
  printList(head);

  // 노드 삭제
  deleteNode(&head, 2);

  // 리스트 출력
  cout << "List: ";
  printList(head);
 }

 

<C++> 라이브러리 이용

C++ 표준 라이브러리에서는 연결 리스트를 구현하는 list 컨테이너를 제공합니다. list 컨테이너는 더블 링크드 리스트 구조를 기반으로 하며, push_back(), push_front(), pop_back(), pop_front() 등 다양한 기능을 제공합니다.

 

list 컨테이너는 동적 할당으로 구현되어 있기 때문에 선언할 때 크기를 지정하지 않아도 됩니다. 따라서, 리스트에 원소를 추가하면 자동으로 크기가 조정됩니다. 이것이 동적 할당의 장점 중 하나입니다. 리스트의 크기가 미리 결정되어 있지 않기 때문에, 원소의 삽입 및 삭제가 상수 시간에 이루어지는 것이 특징입니다.

 

예제)

리스트 라이브러리를 사용한 연결리스트 예제입니다.

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> linked_list;

    // 5, 4, 3, 2, 1의 값을 갖는 노드들을 리스트에 추가
    for (int i = 5; i >= 1; i--) {
        linked_list.push_front(i);
    }

    // 리스트 출력
    for (int node : linked_list) {
        cout << node << " ";
    }
    cout << endl;

    // 첫 번째 노드 삭제
    linked_list.pop_front();

    // 리스트 출력
    for (int node : linked_list) {
        cout << node << " ";
    }
    cout << endl;

    // 마지막 노드 삭제
    linked_list.pop_back();

    // 리스트 출력
    for (int node : linked_list) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

위 코드에서는 list 클래스의 객체 linked_list를 생성한 후, push_front() 메서드를 사용하여 값을 추가하고, pop_front()와 pop_back() 메서드를 사용하여 노드를 삭제하였습니다.