저번 글에 이어서 이번에는 선형 자료구조 중 하나인 연결 리스트에 대해 알아보자!
연결 리스트
정의와 성질
연결 리스트는 원소를 저장할 때 그 다음 원소가 있는 위치도 같이 저장하는 자료구조이다. 그리고 이러한 원소들은 메모리 상에서 이곳저곳에 흩어져 있다.
연결 리스트의 성질
- k번째 원소 확인/변경: O(k)
- 배열과 다르게 메모리 공간에 원소들이 연속해서 위치하지 않기 때문에 첫번째 원소부터 k번째 원소까지 순차적으로 방문해야 한다.
- 임의의 위치에 원소를 추가/삭제: O(1) ⭐
- 원소들이 메모리 상에 연속해 있지 않아 Cache hit rate가 낮지만, 메모리 할당은 다소 쉬움.
연결 리스트의 종류
- 단일 연결 리스트 (Singly Linked List): 각 원소가 자신의 다음 원소의 주소를 갖고 있는 리스트
- 이중 연결 리스트 (Doubly Linked List): 각 원소가 자신의 이전, 다음 원소의 주소를 모두 갖고 있는 리스트 (이전 원소의 주소도 알 수 있어서 좋지만, 그만큼 메모리 공간을 더 사용한다. STL list 컨테이너에 해당)
- 원형 연결 리스트 (Circular Linked List): 맨 마지막 원소가 첫번째 원소를 가리키고 있는 리스트 (각 원소는 다른 원소와 단일 또는 이중 연결되어 있다.)
⭐️ 배열 vs 연결 리스트
배열과 연결 리스트 모두 원소들 간의 순서가 정해져 있는 선형 자료구조이다. ('몇번째' 원소 라는 개념이 존재)
이 둘의 차이점을 잘 알아야 적재적소에서 적절한 자료구조를 선택하여 사용할 수 있다. (기술 면접 단골 질문이라고 한다!)
| 배열 | 리스트 | |
|---|---|---|
| k번째 원소 접근 | O(1) | O(k) |
| 임의의 위치에 원소 추가/삭제 | O(k) | O(1) |
| 메모리 상의 배치 | 연속 | 불연속 |
| 추가적으로 필요한 공간 (오버헤드) | - | O(k) |
cf) 34비트 체계의 컴퓨터인 경우 주소값이 32비트(4바이트) 단위이므로, 단일 연결 리스트에서 다음 원소의 주소를 저장하기 위해 4k 바이트가 추가적으로 필요하다. (k: 전체 원소 개수) 만약 64비트 체계의 컴퓨터라면 8k 바이트가 추가적으로 필요하다. 그리고 이중 연결 리스트의 경우, 이전 원소의 주소를 저장하기 위한 공간도 필요하다.
기능과 구현
연결 리스트의 기능
1. 임의의 위치에 있는 원소 확인/변경 - O(N)
첫번째 원소의 주소만 알고 있기 때문에 n번째 원소에 접근하거나 값을 변경하려면 O(N)의 시간복잡도가 걸린다.
2. 임의의 위치에 원소 추가 - O(1)
연결 리스트에서는 임의의 위치에 원소를 추가하더라도 그 뒤의 원소들을 전부 옮기는 작업을 하지 않아도 된다. 단지 다음 원소의 주소만 바꿔주면 되기 때문이다.
cf) 유의할 점이 있는데 원소를 추가하려는 번지 수를 알고 있을 때만 O(1)이라는 것이다. 그렇지 않고 그냥 새로운 원소를 세번째 원소 다음에 추가하라고 하면, 배열의 시작 주소에서 세번째 원소의 주소까지 찾아가야 하기 때문에 O(1)이라고 할 수 없다!!
3. 임의의 위치에서 원소 삭제 - O(1)
21을 삭제하려면, 65가 가리키는 위치를 17로 바꿔주기만 하면 되기 때문에 O(1)의 시간이 걸린다. (메모리 누수를 막기 위해 원소 21을 메모리에서 제거하는 과정이 필요하긴 하다.)
cf) 연결 리스트가 쓰이는 대표적인 상황이 바로 메모장과 같은 텍스트 에디터이다. 텍스트 에디터에서 우리는 보통 커서를 옮겨서 새로운 문자를 추가 및 삭제하는 일이 많다. 이런 경우에 배열은 임의의 위치에 원소를 추가/삭제하는 연산이 비효율적인 반면에, 연결 리스트는 O(1)에 처리할 수 있어서 더 효율적이다. 이처럼 임의의 위치에 원소를 추가/삭제하는 연산이 많을 때는 연결 리스트의 사용을 고려해보는 것이 좋다.
연결 리스트의 구현
struct NODE {
struct NODE *prev, *next;
int data;
};연결 리스트를 구현하는 가장 정석적인 방법은 위와 같이 NODE 구조체나 클래스를 만들어서 원소가 생성될 때 동적 할당하는 것이다.
그런데, 구현 시간이 부족한 코딩테스트에서는 STL에서 제공하는 list 컨테이너를 사용하는 게 좋다. STL list는 이중 연결 리스트로 구현되어 있기 때문에 가져다 쓰면 되기 때문이다.
드물긴 하지만 STL 사용을 금지하는 코딩테스트에서는 연결 리스트를 직접 구현해야 하는데, 정석적인 방법보다 조금 더 빠르게 구현할 수 있는 방법을 소개하려고 한다.
이 방법은 원소를 배열로 관리하며, prev, next에 이전/다음 원소의 포인터 대신 배열 상의 인덱스를 저장한다. 메모리 누수 문제 때문에 실무에서는 절대 사용할 수 없지만, 코딩테스트에서는 정석적인 연결 리스트 보다 구현 난이도가 낮고 시간복잡도도 동일하기 때문에 유용하게 사용할 수 있다.
const int MAX = 1000005;
int data[MAX], prev[MAX], next[MAX];
int unused = 1;
fill(prev, prev + MAX, -1);
fill(next, next + MAX, -1);data 배열에는 i번째 원소의 값, prev 배열에는 이전 원소의 인덱스, next 배열에는 다음 원소의 인덱스를 저장한다.
prev 또는 next 의 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 뜻이다.
unused는 현재 사용되지 않는 인덱스, 즉 새로운 원소가 들어갈 수 있는 인덱스이다. 따라서 원소가 추가될 때마다 이 값은 1씩 증가한다.
그리고 특별히 0번지 원소에는 값이 들어가 있지 않으며, 단지 시작점을 나타내기 위한 더미 노드라고 볼 수 있다. 이런 더미 노드를 구현하지 않으면 나중에 원소 삽입/삭제 기능 구현 시, 리스트가 비어 있는 경우에 대한 예외 처리가 까다롭기 때문에 더미 노드를 두는 것이 좋다.
원소의 길이를 알아야 하는 경우에는 코드 상에 len 변수를 추가하여, 원소 삽입/삭제에 따라 len 변수의 값을 증감 시키면 된다.
traverse 함수: O(N)
연결 리스트에서 모든 원소의 값을 출력하려면, 0번지에서 출발하여 next에 적힌 값을 보고 계속 넘어가면서 data를 출력하면 된다. (단순히 배열처럼 data[0], data[1], ... 이렇게 순차적으로 출력하면 안 된다.)
void traverse() {
int cur = next[0];
while(cur != -1){
cout << data[cur] << " ";
cur = next[cur];
}
cout << "\n\n";
}insert 함수: O(1)
// addr 바로 뒤에 새 원소를 삽입한다.
void insert(int addr, int num){
data[unused] = num;
prev[unused] = addr;
next[unused] = next[addr];
// 인덱스 주의
if(next[addr] != -1) prev[next[addr]] = unused;
next[addr] = unused;
unused++;
}erase 함수: O(1)
이 방법은 제거된 원소가 프로그램이 종료될 때까지 메모리를 점유하고 있기 때문에 실무에서는 사용할 수 없다.
그렇지만 코딩 테스트에서는 insert 횟수가 10만 번 혹은 100만 번과 같이 크기 제한이 있기 마련이므로, 배열의 크기를 해당 제한보다 넉넉하게 잡아버리고 위와 같은 방식으로 구현하면 편리하다.
// addr 위치의 원소를 제거한다.
void erase(int addr){
// 인덱스 주의
if(next[addr] != -1)
prev[next[addr]] = prev[addr];
next[prev[addr]] = next[addr];
}cf) 값을 갖고 있지 않은 더미 노드의 존재로 인해, 그 어떤 원소를 지우더라도 prev[addr]의 값은 -1이 될 수 없다. 반면에, next[addr] 는 맨 마지막 원소를 지울 때 -1이 될 수 있으므로 인덱스 체크를 해줘야 한다!
STL list
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> L = {1, 2}; // 1 2
// C++11 이상에서는 auto 키워드 사용 가능
list<int>::iterator t = L.begin(); // 첫번째 원소 가리킴.
L.push_front(10); // 10 1 2
cout << *t << "\n"; // t가 가리키고 있는 1을 출력
L.push_back(5); // 10 1 2 5
L.insert(t, 6); // t가 가리키는 곳 '앞'에 6을 삽입 (10 6 1 2 5)
t++; // t를 뒤로 한칸 전진 (현재 가리키는 값은 2)
t = L.erase(t); // t가 가리키는 값 제거, 그 다음 위치 반환 (10 6 1 5)
// t가 가리키는 값은 5
cout << *t << "\n";
for(auto e: L)
cout << e << " ";
cout << "\n";
// C++11 미만인 경우
for(list<int>::iterator it = L.begin(); it != L.end(); it++)
cout << *it << " ";
cout << "\n";
}