LIST

#define cstl_list(T) new_list(T)

LIST는 이중 연결 리스트(doubly-linked list) 컨테이너로, C++ STL의 std::list에 대응됩니다. 각 요소는 독립된 노드에 저장되며, 노드는 앞 노드와 뒤 노드를 가리키는 포인터를 함께 가집니다. 따라서 어느 위치에서든 삽입/삭제가 상수 시간에 수행되지만, 임의 접근(v[i])은 지원하지 않습니다.

LIST는 요소가 메모리에 연속적으로 놓이지 않기 때문에 캐시 지역성 면에서는 VECTOR보다 불리합니다. 대신 반복자가 컨테이너 구조 변경에도 무효화되지 않는다는 특성이 있어, 중간 위치에서의 삽입·삭제가 빈번하거나 외부에서 반복자를 장기 보관해야 하는 시나리오에 적합합니다.

복잡도: 끝(back)/앞(front)에서의 삽입·제거는 상수 시간 O(1), 임의 위치에서의 삽입·제거도 반복자를 이미 알고 있다면 O(1), 탐색(find)과 순회는 선형 시간 O(n)입니다.

Functions

생성/소멸

Function	설명
new_list(T)	T 타입의 새로운 리스트 생성
destroy	컨테이너 소멸자

Element access

Function	설명
front	첫 번째 요소에 접근
back	마지막 요소에 접근

Iterator

Function	설명
begin	시작 반복자를 반환
end	끝(past-the-end) 반복자를 반환
rbegin	역방향 시작 반복자를 반환
rend	역방향 끝 반복자를 반환
next	반복자를 한 칸 전진
prev	반복자를 한 칸 후퇴

Capacity

Function	설명
size	요소 개수를 반환
empty	비었는지 확인

Modifiers

Function	설명
clear	모든 요소를 제거
insert	지정 위치에 요소를 삽입
erase	지정 범위의 요소를 제거
push_back	끝에 요소를 추가
pop_back	마지막 요소를 제거
push_front	앞에 요소를 추가
pop_front	첫 번째 요소를 제거
resize	요소 개수를 n으로 변경

탐색

Function	설명
find	지정한 요소를 검색

Operations

Function	설명
sort	리스트를 정렬 (merge sort 기반)

Member function details

Note

LIST, new_list

LIST(int) list = new_list(int);

요소 타입이 TYPE인 빈 리스트를 생성합니다. 반환값은 TYPE*로, 내부적으로는 이중 연결 리스트의 헤드 노드를 가리키는 불투명 포인터입니다.

Parameters

Parameter	설명
T	저장할 요소의 타입 (예: int, double, 구조체 등)

Complexity

O(1)

Example

LIST(int) list = new_list(int);
LIST(double) dlist = new_list(double);

Note

destroy

void destroy(list);

리스트의 모든 노드를 순회하면서 각 노드의 메모리를 해제한 뒤, 컨테이너 본체까지 해제하고 포인터를 NULL로 설정합니다.

Warning

VECTOR와 달리 LIST는 각 요소마다 독립된 노드를 동적으로 할당하므로, destroy를 호출하지 않으면 다수의 메모리 누수가 발생합니다.

Complexity

O(n)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 10; i++) push_back(list, i);
// list 사용
destroy(list); // 모든 노드 해제

Note

front, back

<TYPE> front(list);
<TYPE> back(list);

front는 리스트의 첫 번째 요소의 값을, back은 마지막 요소의 값을 반환합니다.

Warning

빈 리스트에서 호출하면 정의되지 않은 동작(undefined behavior)이 발생합니다. 호출 전에 size(list) > 0 또는 !empty(list)를 확인하세요.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
push_back(list, 10);
push_back(list, 20);
push_back(list, 30);

printf("front: %d\n", front(list)); // 10
printf("back : %d\n", back(list));  // 30

Note

begin, end

iterator begin(list);
iterator end(list);

begin은 첫 번째 노드를 가리키는 반복자를, end는 past-the-end를 가리키는 반복자를 반환합니다. LIST의 end는 내부적으로 NULL입니다. 리스트가 비어 있으면 begin == end == NULL입니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 5; i++) push_back(list, i);

for (int* it = begin(list); it != end(list); it = next(it)) {
    printf("[%d] ", *it);
}
// 출력: [0] [1] [2] [3] [4]

Note

rbegin, rend

reverse_iterator rbegin(list);
reverse_iterator rend(list);

역방향 순회용 반복자를 반환합니다. rbegin은 마지막 노드를, rend는 첫 번째 노드의 이전 위치(내부적으로 NULL)를 가리킵니다.

Warning

역방향 순회 시에는 반드시 prev를 사용해 반복자를 이동시켜야 합니다. VECTOR처럼 it-- 같은 포인터 산술은 노드 포인터에서는 동작하지 않습니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 5; i++) push_back(list, i);

for (int* it = rbegin(list); it != rend(list); it = prev(it)) {
    printf("[%d] ", *it);
}
// 출력: [4] [3] [2] [1] [0]

Note

next, prev

iterator next(it);
iterator prev(it);

현재 반복자에서 다음 노드 또는 이전 노드로 이동합니다. LIST의 노드는 불연속적으로 할당되므로 포인터 산술로 이동할 수 없으며, 반드시 이 함수를 사용해야 합니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
push_back(list, 10);
push_back(list, 20);
push_back(list, 30);

int* it = begin(list);
it = next(it);
printf("%d\n", *it); // 20
it = prev(it);
printf("%d\n", *it); // 10

Note

size

size_type size(list);

리스트가 저장하고 있는 요소의 개수를 반환합니다. 내부적으로 카운터를 유지하므로 상수 시간에 수행됩니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
push_back(list, 1);
push_back(list, 2);
printf("%zu\n", size(list)); // 2

Note

empty

bool empty(list);

리스트가 비어 있는지 확인합니다. size(list) == 0과 동일하지만 의미가 더 명확합니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
if (empty(list)) {
    puts("list is empty");
}
push_back(list, 42);
// empty(list) == false

Note

clear

void clear(list);

리스트의 모든 요소를 제거하고 각 노드의 메모리를 해제합니다. 컨테이너 본체는 유지되므로 이후에도 계속 사용할 수 있습니다.

Complexity

O(n)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 100; i++) push_back(list, i);
clear(list);
printf("%zu\n", size(list)); // 0

Note

insert

void insert(list, iterator pos, <TYPE> value);
void insert(list, iterator pos, size_t n, <TYPE> value);

pos가 가리키는 노드의 앞 위치에 값을 삽입합니다. 두 번째 형식은 value를 n번 복사해서 삽입합니다.

Parameters

Parameter	설명
pos	삽입 위치를 가리키는 반복자
n	삽입할 요소의 개수 (생략 시 1)
value	삽입할 값

Note

VECTOR와 달리 LIST의 insert는 기존 반복자를 무효화하지 않습니다. 리스트에 이미 들고 있던 반복자는 계속 유효합니다.

Complexity

O(n) — 삽입할 요소 수에 비례

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 5; i++) push_back(list, i);
// [0] [1] [2] [3] [4]

insert(list, begin(list), 777);
// [777] [0] [1] [2] [3] [4]

insert(list, find(list, 3), 5, 999);
// [777] [0] [1] [2] [999] [999] [999] [999] [999] [3] [4]

Note

erase

void erase(list, iterator first, iterator last);

구간 [first, last)에 해당하는 노드들을 제거하고 메모리를 해제합니다.

Warning

삭제된 노드를 가리키는 반복자는 당연히 무효화됩니다. 다만 삭제 대상이 아닌 다른 노드의 반복자는 여전히 유효합니다.

Complexity

O(n) — 구간 길이에 비례

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 5; i++) push_back(list, i);
// [0] [1] [2] [3] [4]

erase(list, find(list, 1), find(list, 3));
// [0] [3] [4]

Note

push_back

void push_back(list, <TYPE> value);

리스트 끝에 값을 추가합니다. 새 노드를 할당해서 tail 뒤에 연결합니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 10; i++) {
    push_back(list, i);
}

Note

pop_back

void pop_back(list);

리스트의 마지막 노드를 제거하고 메모리를 해제합니다.

Warning

빈 리스트에서 호출하면 에러가 발생합니다 ("No elements in cstl_list").

Complexity

O(1)

Example

LIST(int) list = new_list(int);
push_back(list, 1);
push_back(list, 2);
pop_back(list);
printf("%zu\n", size(list)); // 1

Note

push_front

void push_front(list, <TYPE> value);

리스트 앞에 값을 추가합니다. LIST는 이중 연결이므로 VECTOR와 달리 선두 삽입이 O(1)에 수행됩니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
push_back(list, 2);
push_back(list, 3);
push_front(list, 1);
// [1] [2] [3]

Note

pop_front

void pop_front(list);

리스트의 첫 번째 노드를 제거하고 메모리를 해제합니다. 선두 제거도 O(1)입니다.

Warning

빈 리스트에서 호출하면 에러가 발생합니다.

Complexity

O(1)

Example

LIST(int) list = new_list(int);
push_back(list, 1);
push_back(list, 2);
push_back(list, 3);
pop_front(list);
// [2] [3]

Note

resize

void resize(list, size_t n);
void resize(list, size_t n, <TYPE> value);

리스트의 크기를 n으로 변경합니다.

현재 크기보다 작으면 뒤쪽 노드들이 제거됩니다.
현재 크기보다 크면 value로 초기화된 노드가 뒤에 추가됩니다. value를 생략하면 0으로 채워집니다.

Parameters

Parameter	설명
n	변경할 크기
value	증가분에 채울 값 (선택)

Complexity

O(|n - size|)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 3; i++) push_back(list, i); // [0] [1] [2]

resize(list, 5, 99);
// [0] [1] [2] [99] [99]

resize(list, 2);
// [0] [1]

Note

find

iterator find(list, <TYPE> value);

리스트를 처음부터 순회하며 value와 memcmp 기준으로 일치하는 첫 번째 노드의 반복자를 반환합니다. 찾지 못하면 NULL을 반환합니다.

Warning

비교는 바이트 단위(memcmp)로 수행됩니다. 구조체에 패딩이 있으면 예기치 않은 결과가 나올 수 있으니 memset으로 초기화하여 사용하세요.

Complexity

O(n)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 10; i++) push_back(list, i * i);

int* pos = find(list, 25);
if (pos != NULL) {
    printf("found: %d\n", *pos); // 25
}

Note

sort

void sort(list);

리스트를 오름차순으로 정렬합니다. 내부적으로 merge sort를 사용하므로 LIST의 노드 구조에 최적화되어 있으며, 노드 포인터만 재연결하고 값 자체는 이동하지 않습니다.

Note

연결 리스트에 quicksort를 적용하면 임의 접근이 없어 피벗 선택과 파티셔닝이 비효율적입니다. Merge sort는 연결 리스트에 대해 추가 메모리 없이 O(n log n)을 달성할 수 있는 자연스러운 선택입니다.

Complexity

O(n log n)

Example

LIST(int) list = new_list(int);
for (int i = 0; i < 50; i++) {
    push_back(list, rand32() % 1000);
}

sort(list);

for (int* it = begin(list); it != end(list); it = next(it)) {
    printf("[%d]->", *it);
}
puts("[NULL]");

Full Example

main.c의 cstl_list_test02에서 발췌한 종합 예시입니다.

LIST(int) list = new_list(int);

for (int i = 0; i < 10; i++) {
    push_back(list, i);
}
// [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

pop_back(list);
// [0] [1] [2] [3] [4] [5] [6] [7] [8]

insert(list, begin(list), 777);
// [777] [0] [1] [2] [3] [4] [5] [6] [7] [8]

insert(list, find(list, 4), 5, 999);
// [777] [0] [1] [2] [3] [999] [999] [999] [999] [999] [4] [5] [6] [7] [8]

erase(list, find(list, 2), find(list, 999));
// [777] [0] [1] [999] [999] [999] [999] [999] [4] [5] [6] [7] [8]

printf("front: %d\n", front(list)); // 777
printf("back : %d\n", back(list));  // 8

sort(list);

for (int* it = begin(list); it != end(list); it = next(it)) {
    printf("[%d]->", *it);
}
puts("[NULL]");

destroy(list);

VECTOR vs LIST

특성	VECTOR	LIST
메모리 배치	연속 (contiguous)	비연속 (노드 단위 할당)
임의 접근 `v[i]`	`O(1)`	미지원
끝에 삽입	amortized `O(1)`	`O(1)`
앞에 삽입	`O(n)`	`O(1)`
중간 삽입 (반복자 보유)	`O(n)`	`O(1)`
캐시 지역성	우수	불리
반복자 무효화	재할당/삽입 시 발생	삭제 대상 외에는 유지
정렬 알고리즘	pmsort (vector용 merge sort)	sort (list용 merge sort)

Note

일반적으로는 VECTOR가 기본 선택이 됩니다. LIST는 중간 위치에서 삽입/삭제가 매우 빈번하거나, 외부에서 반복자를 장기 보관해야 하는 경우에 선택하세요.

OpenCSTL Wiki

Home
- Container library
  - Sequential Containers
    - VECTOR
    - DEQUE
    - LIST
  - Associative Containers
    - SET
    - MAP
  - Unordered Containers
    - UNORDERED_SET
    - UNORDERED_MAP
- Sorting Algorithm
- Logging library

LIST

LIST

#define cstl_list(T) new_list(T)

Functions

생성/소멸

Element access

Iterator

Capacity

Modifiers

탐색

Operations

Member function details

Parameters

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Parameters

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Complexity

Example

Parameters

Complexity

Example

Complexity

Example

Complexity

Example

Full Example

VECTOR vs LIST

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

OpenCSTL Wiki

Clone this wiki locally