연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 주소(포인터)를 가지며, 이들이 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 선형 자료구조이다. 배열과 달리 메모리상에서 연속적으로 위치하지 않고 동적으로 할당된다.
연결 리스트 vs 배열(Array/Vector) 비교
| 비교 항목 | 배열 (Array / std::vector) | 연결 리스트 (Linked List / std::list) |
| 메모리 할당 | 정적/동적 연속된 메모리 공간 | 동적 비연속적인 메모리 공간 (필요할 때마다 할당) |
| 임의 접근 (Search by Index) | $O(1)$ (인덱스로 바로 접근 가능) | $O(N)$ (처음부터 차례대로 찾아가야 함) |
| 삽입/삭제 (Insertion/Deletion) | $O(N)$ (데이터를 뒤로 밀거나 당겨야 함) | $O(1)$ (포인터 주소만 변경하면 됨, 탐색 시간 제외) |
| 메모리 오버헤드 | 추가적인 오버헤드가 거의 없음 | 다음 노드를 가리키는 포인터 저장을 위한 추가 메모리 필요 |
연결 리스트의 종류
① 단일 연결 리스트 (Singly Linked List)
- 구조: 노드가 단방향(Next 포인터만 가짐)으로 연결되어 있다.
- 특징: 뒤로만 이동할 수 있으며, 이전 노드로 돌아갈 수 없다.
- C++ 지원: std::forward_list (C++11 이상)
② 이중 연결 리스트 (Doubly Linked List)
- 구조: 각 노드가 이전 노드(Prev)와 다음 노드(Next)를 가리키는 두 개의 포인터를 가진다.
- 특징: 양방향 탐색이 가능하여 노드 이동이 자유롭지만, 포인터를 하나 더 관리해야 하므로 메모리를 더 사용하고 구현이 조금 더 복잡하다.
- C++ 지원: std::list (기본 제공되는 연결 리스트 STL)
③ 원형 연결 리스트 (Circular Linked List)
- 구조: 마지막 노드의 Next 포인터가 NULL이 아닌 첫 번째 노드(Head)를 가리킨다. (이중 연결 리스트 구조에 적용하면 Head의 Prev가 Tail을, Tail의 Next가 Head를 가리킵니다.)
- 특징: 끝이 없이 순환하는 구조로, 시작 노드를 통해 모든 노드에 도달할 수 있다.
- C++ 지원: STL로 직접 제공되지 않으며, 필요 시 사용자 정의 구조체나 std::list를 변형하여 구현한다.
단일 연결 리스트 vs 이중 연결 리스트 STL 기능 비교
C++ STL에서 단일 연결 리스트는 std::forward_list, 이중 연결 리스트는 std::list로 구현되어 있다. 이 둘은 함수 인터페이스에서 매우 큰 차이를 보인다.
단일 연결 리스트는 뒤로 갈 수 없는 구조적 특징 때문에 다음과 같은 차이점이 생긴다.
- _after 계열 함수의 존재: 단일 연결 리스트에서 특정 노드 A 자리에 새 노드를 삽입하려면, A 앞 노드의 next 포인터를 수정해야 한다. 하지만 단일 연결 리스트는 뒤로 갈 수 없기 때문에 A 노드만 알아서는 이전 노드를 찾을 수 없다.
- 따라서 "특정 노드의 뒤에 삽입/삭제"하는 insert_after(), erase_after()를 사용한다.
- before_begin()의 존재:
- 맨 첫 번째 노드(Head)의 앞에 원소를 삽입할 수 있도록, 실제 첫 노드 이전의 가상 위치를 가리키는 반복자를 반환하는 함수이다.
- push_back() / pop_back() 미지원:
- 맨 뒤 노드에 접근하려면 처음부터 끝까지 다 가봐야 하므로($O(N)$), 이 비효율적인 연산들을 아예 지원하지 않는다. (오직 맨 앞에만 넣고 빼는 push_front, pop_front만 지원)
- size() 미지원 (중요):
- 크기(Size) 정보를 저장하려면 추가적인 메모리(4~8바이트)가 필요한데, std::forward_list는 크기 정보를 저장하지 않는다. 크기를 알려면 전체를 순회(std::distance)해야 하므로 $O(N)$이 걸린다.
주요 멤버 함수 비교표
기능단일 연결 리스트 (std::forward_list)이중 연결 리스트 (std::list)
| 맨 앞에 삽입 | push_front(val) | push_front(val) |
| 맨 뒤에 삽입 | 미지원 | push_back(val) |
| 맨 앞 원소 삭제 | pop_front() | pop_front() |
| 맨 뒤 원소 삭제 | 미지원 | pop_back() |
| 지정 위치 삽입 | insert_after(it, val) (지정 위치 뒤에) | insert(it, val) (지정 위치 앞에) |
| 지정 위치 삭제 | erase_after(it) (지정 위치 뒤를 삭제) | erase(it) (지정 위치를 삭제) |
| 첫 노드 이전 반복자 | before_begin() | 미지원 |
| 크기 조회 (size()) | 미지원 (직접 순회해서 계산해야 함) | size() ($O(1)$) |
std::forward_list 활용 예제 코드
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> fl = {10, 20, 30};
// 맨 앞에 원소 삽입
fl.push_front(5); // [5, 10, 20, 30]
// 특정 위치 뒤에 삽입 (insert_after)
auto it = fl.begin(); // 5를 가리킴
fl.insert_after(it, 7); // 5 뒤에 7 삽입 -> [5, 7, 10, 20, 30]
// 맨 첫 번째 원소 앞에 삽입하고 싶을 때 (before_begin 활용)
fl.insert_after(fl.before_begin(), 1); // 맨 앞에 1 삽입 -> [1, 5, 7, 10, 20, 30]
// 특정 위치 뒤의 원소 삭제 (erase_after)
it = fl.begin(); // 1을 가리킴
fl.erase_after(it); // 1 뒤에 있는 5를 삭제 -> [1, 7, 10, 20, 30]
// 출력 순회
std::cout << "단일 연결 리스트 출력: ";
for (int val : fl) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
이중 연결 리스트 (Doubly Linked List) 상세 및 예제
이중 연결 리스트는 임의의 위치에서 앞뒤 모두로 이동할 수 있기 때문에 데이터의 탐색과 삭제 속도를 대폭 개선할 수 있다.
C++ STL std::list 핵심 함수 정리
std::list는 양방향 반복자(Bidirectional Iterator)를 제공하며 모든 삽입/삭제가 $O(1)$로 수행된다.
| push_front(val) | 리스트의 맨 앞에 원소 val을 추가한다. | $O(1)$ |
| push_back(val) | 리스트의 맨 뒤에 원소 val을 추가한다. | $O(1)$ |
| pop_front() | 리스트의 맨 앞 원소를 제거한다. | $O(1)$ |
| pop_back() | 리스트의 맨 뒤 원소를 제거한다. | $O(1)$ |
| insert(it, val) | 반복자 it가 가리키는 위치 바로 앞에 val을 삽입하고, 삽입된 원소를 가리키는 반복자를 반환한다. | $O(1)$ |
| erase(it) | 반복자 it가 가리키는 위치의 원소를 제거하고, 그다음 원소를 가리키는 반복자를 반환한다. | $O(1)$ |
| remove(val) | 리스트 전체에서 값 val과 일치하는 모든 원소를 찾아서 삭제한다. | $O(N)$ |
| front() / back() | 각각 맨 앞과 맨 뒤 원소의 참조를 반환한다. | $O(1)$ |
| reverse() | 리스트 내 원소들의 순서를 뒤집는다. | $O(N)$ |
| sort() | 리스트의 원소들을 정렬한다. (내부 전용 정렬 알고리즘 사용) | $O(N \log N)$ |
std::list 활용 예제 코드
#include <iostream>
#include <list>
int main() {
std::list<int> myList;
// 맨 앞/뒤 원소 삽입
myList.push_back(20); // [20]
myList.push_front(10); // [10, 20]
myList.push_back(30); // [10, 20, 30]
// 반복자(Iterator)를 사용한 삽입 및 삭제
auto it = myList.begin();
it++; // 20을 가리킴
myList.insert(it, 15); // [10, 15, 20, 30] (it 직전에 삽입)
// 순회 출력
std::cout << "앞에서부터 출력: ";
for (int val : myList) {
std::cout << val << " ";
}
std::cout << "\n";
// 역방향 순회
std::cout << "뒤에서부터 출력: ";
for (auto rit = myList.rbegin(); rit != myList.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << "\n";
return 0;
}
원형 연결 리스트 (Circular Linked List) 상세 및 예제
원형 연결 리스트는 큐(Queue)를 순환 구조로 설계하거나 게임 내에서 순차적으로 턴(Turn)을 넘길 때, 멀티태스킹 환경에서 CPU 시간을 번갈아 할당하는 라운드 로빈(Round Robin) 스케줄링 등에 자주 사용된다.
사용자 정의 단일 원형 연결 리스트 예제 코드
#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class CircularLinkedList {
private:
Node* head;
public:
CircularLinkedList() : head(nullptr) {}
// 데이터 삽입 (가장 끝에 추가)
void insert(int val) {
Node* newNode = new Node(val);
if (!head) {
head = newNode;
newNode->next = head; // 스스로를 가리켜 원형 유지
} else {
Node* temp = head;
while (temp->next != head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = head; // 마지막 노드가 head를 가리킴
}
}
// 원형 리스트 특정 횟수만큼 순환하며 출력
void display(int limit) {
if (!head) return;
Node* temp = head;
int count = 0;
std::cout << "원형 리스트 순환 출력: ";
while (count < limit) {
std::cout << temp->data << " -> ";
temp = temp->next;
count++;
}
std::cout << "... (계속)" << std::endl;
}
// 소멸자 (메모리 해제 시 무한루프 방지 주의)
~CircularLinkedList() {
if (!head) return;
Node* curr = head;
Node* nextNode = nullptr;
// 원형 연결을 끊어서 일반 리스트처럼 만든 후 메모리 해제
Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
tail->next = nullptr; // 원형 연결 해제
while (curr != nullptr) {
nextNode = curr->next;
delete curr;
curr = nextNode;
}
}
};
int main() {
CircularLinkedList cll;
cll.insert(1);
cll.insert(2);
cll.insert(3);
// 원소는 3개지만 원형이므로 계속해서 순환 출력이 가능합니다.
cll.display(8); // 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 1 -> 2 -> ...
return 0;
}
'Language > C++' 카테고리의 다른 글
| [C++/STL] Queue 정리 (0) | 2026.05.27 |
|---|---|
| [C++/STL] Stack 정리 (0) | 2026.05.27 |