| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
linked list추상적 자료형인 리스트를 구현한 자료 구조이다.
데이터(노드node)를 저장할 때 하나의 데이터와 그 다음 데이터로의 위치(보통 다음 노드의 주소나 참조)를 함께 저장하여 논리적으로 연결(link)하는 방식으로 자료를 저장한다. 데이터는 논리적으로 연결되어 있으므로 배열과 달리 데이터의 삽입 삭제가 자유로워지면서 자연스럽게 전체 크기를 늘리고 줄이는 것 또한 가능해진다.
논리적으로 연결되어있기 때문에 연결 리스트의 구조는 바로 아래 설명의 그림처럼 매우 난잡하지만 (분리 결합이 간단하다는 가정 하에) 사슬이나 기차라고 생각하면 적절하다.
2. 설명
배열이 철수 1번, 영희 2번, 민수 3번, 순이 4번...식으로 자료의 순번을 맞춘다면, 연결 리스트는 철수 다음 영희, 영희 다음 민수, 민수 다음 순이....식으로 자료를 연결해 놓는다. 따라서 배열과는 달리 새로운 데이터, 즉 노드를 뒤에 연결하거나 중간에 노드 몇 개를 껴놓는 것이 쉽다.[1] 그러나 배열에서는 자료마다 번호가 있어서 특정한 자료를 불러내기가 편리한 반면, 연결 리스트는 자료 번호가 없이 그저 연결 관계만 있기 때문에 특정한 노드를 불러내기 어려운 단점이 있다.[2][3]
연결 리스트는 배열에 비해 데이터의 추가/삽입 및 삭제가 용이하나 노드를 하나하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다. 즉 탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다. 단, 연결 리스트라고 해서 반드시 순차 탐색만 해야 한다는 법은 없다. B+tree 자료 구조는 연결 리스트에 힙을 더한 것 같은 모양새를 갖고 있는데 이 자료 구조는 데이터의 추가/삭제/정렬/조회 모두에 유리하다. 단점은 그 구현의 복잡도. 물론 여러분이 직접 구현할 필요는 전혀 없다. 데이터베이스와 파일 시스템이 이 B-tree의 구현체니까 그렇다.
또한 배열은 크기를 크게 키우기가 어려운 단점이 있다. 배열은 연속된 메모리 공간을 할당받아야 하는데 크기가 커지면 그만한 '연속된' 공간을 할당하기가 어려워진다. 요즘 컴퓨터는 페이징 개념을 도입해서 메모리를 관리하기 때문에 연속된 큰 공간을 할당하는 작업도 무리 없이 해내긴 하지만 그렇다 하더라도 배열은 자기가 당장 쓰지 않는 공간까지 전부 예약해 두고 있어야 하기 때문에 공간 낭비가 생긴다. 또한 배열은 처음에 정한 배열의 용량(크기)을 모두 사용했을 경우에 데이터를 배열에 추가하기 위해서는, 확장된 크기의 배열을 메모리에 추가로 확보한 후에 기존에 있던 배열의 내용을 새 배열에 복사하고 새 데이터를 새로운 배열에 추가한 후에 기존 배열을 없애야 한다. 따라서 배열은 크기의 조정이 쉽지 않다. 반면에 연결 리스트는 그저 새 노드를 기존 리스트에 연결하면 될 뿐이다. 한마디로 연결 리스트는 메모리 공간을 필요한 만큼은 사용할 수 있다는 장점이 있다.
3. 구현 방법
일반적으로 구조체와 그 포인터로 구성된다. 포인터가 없는 Java 언어의 경우에는 포인터 역할을 수행하는 레퍼런스로 구현한다.3.1. 단순 연결 리스트(singly linked list)
다음 노드에 대한 참조만을 가진 가장 단순한 형태의 연결 리스트이다. 가장 마지막 원소를 찾으려면 얄짤없이 리스트 끝까지 찾아가야 하기 때문에(O(n)), 마지막 원소를 가리키는 참조를 따로 가지는 형태의 변형도 있다. 보통 큐 (queue)를 구현할 때 이런 방법을 쓴다.
이 자료 구조는 head 노드(첫 번째 데이터 노드)를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점이 있다. 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 체인이 끊어진 양 거기부터 뒤쪽 자료들을 유실한다. 따라서 안정적인 자료 구조는 아니다.
파일 시스템 중 FAT 파일 시스템이 이 단순 연결 리스트로 파일 청크를 연결하는데 그래서 FAT 파일 시스템은 파일 내용 일부가 손상될 경우 파일의 상당 부분을 유실할 수 있고 랜덤 액세스 성능도 낮다.
3.2. 이중 연결 리스트(doubly linked list)
다음 노드의 참조뿐만 아니라 이전 노드의 참조도 같이 가리키게 하면 이중 연결 리스트가 된다. 뒤로 탐색하는 게 가능하다는 단순한 장점 이외에도 한 가지 장점이 더 있는데, 단순 연결 리스트는 현재 가리키고 있는 노드를 삭제하는 게 한 번에 안 되고 O(n)이 될 수밖에 없는 데 비해[4] 이중 연결 리스트에서 현재 노드를 삭제하는 것은 훨씬 간단하다. 대신 관리해야 할 참조가 두 개나 있기 때문에 삽입이나 정렬의 경우 작업량이 더 많고 이전 노드의 주소도 같이 저장해야 하는 만큼 데이터의 크기 또한 커진다.
단일 연결 리스트보다는 손상에 강한 편이다. head 노드(첫 번째 노드)와 tail 노드(마지막 노드)를 갖고 있다면 둘 중 하나를 가지고 전체 리스트를 순회할 수 있기 때문에 끊어진 체인을 복구하는 게 가능하다. 단일 연결 리스트는 tail 노드로는 리스트 순회가 불가능하고(이전 노드로의 연결이 없기 때문에) head 노드 유실 시 전체 자료를 다 잃어버린다. 단점은 이런 보정 알고리즘을 구현하지 않았을 경우에는 오히려 손상에 더 취약해진다는 것이다. 예를 들어 노드의 next 포인터(다음 노드의 메모리 주소를 갖는 포인터, 즉 다음 노드를 가르키는 포인터)는 갱신을 했는데 prev 포인터(이전 노드를 가르키는 포인터)는 갱신하지 않았을 경우 prev 포인터를 따라가는 순회에서 도달 불가능한 '잃어버린' 노드가 발생한다.
3.3. 순환 연결 리스트(circular linked list)
단순 연결 리스트(singly linked list)에서 마지막 원소(노드)가 널(null) 대신 처음 원소를 가리키게 하면 순환 연결 리스트가 된다. 이와 비슷하게, 이중 연결 리스트(doubly linked list)의 처음과 끝을 서로 이으면 이중 순환 연결 리스트를 만들 수 있다.
스트림 버퍼의 구현에 많이 사용한다. 이미 할당된 메모리 공간을 삭제하고 재할당하는 부담이 없기 때문에 큐를 구현하는 데에도 적합하다.
3.4. 청크 리스트(chunked List)
배열과 리스트의 장점을 합친 것. 리스트의 멤버가 배열이다. CPU에 캐시 기능이 있는 경우 지역성(locality)이 떨어지는 연결 리스트는 심각한 성능 저하를 불러온다. 이를 보완하기 위해 리스트의 멤버를 레코드의 배열로 하는 것이다. 이 청크 리스트의 발전형이 바로 B+tree다.4. 분석
배열과는 달리 첫 번째 데이터의 추가/삭제가 O(1)의 시간 안에 수행된다. 배열의 경우 데이터를 추가 또는 삭제할 때 해당 지점 뒤쪽의 데이터가 모두 추가 혹은 삭제되는 데이터 크기만큼 밀리거나 당겨져야 하나 연결 리스트는 그럴 필요가 없다. 하지만, 첫 번째가 아닌 중간에 있는 데이터들의 추가/삭제는 해당 데이터가 있는 노드까지 도달하는 데 시간이 걸리기 때문에(삭제하고자 하는 노드까지 가려면 head 노드, 즉 첫 번째 노드부터 출발해서 그다음 노드 또 그다음 노드...처럼 하나씩 이동해야 한다.) O(n)의 수행 시간을 갖게 된다.같은 이유로 데이터 탐색 시에는 문제가 되는데 각 데이터에 한 번에 접근할 수가 없어 항상 순차적으로 도달해야 한다. 이 때문에 데이터 검색에 쥐약이다. 정렬은 O(nlogn)시간에 가능하다. 이 단점을 해결한 것이 위에서 여러 번 언급한 그 B+tree.
5. C에서의 활용
구조체를 활용해서 정의한다.5.1. 선형(순차) 리스트
배열을 이용해서 구현한 리스트 자료 구조이다.LIST_LEN 100컴퓨터 구조를 배웠다면 좀 더 쉽게 이해할 수 있다.
- 처음에 num = 0; cur = -1로 세팅하고
- 삽입: num++
- 삭제: num--
- 조회: 처음 출력할 땐 cur = 0; 후 출력
- 다음에 출력할 땐 cur++; 후 출력을 해주면 된다.
코드를 짜는 입장에서는 간단하지만, 크기를 무조건 고정해야 해서, 공간 낭비 or 공간 부족으로 이어질 수 있다.
5.2. 단순 연결 리스트
struct Node{
int data1,data2,...;
struct Node * next;
5.3. 이중 연결 리스트
여기에서 Previous를 추가하면 이중 연결 리스트가 된다.struct Linked_List* Previous;
head->next->next->name 하는 식으로 사용한다. 노드 조회 메서드에 대해 설명하자면
List * get(int index)
{
List *head = HEAD;
List *cur = head;
for(int i=0; i<index; ++i)
{
cur = cur->next;
}
return cur;
}
특이할 점은 노드 자신의 위치를 표시하기 위한 자기 참조 구조체라는 개념이다. 자기 자신을 구조체 멤버로 가지지 못하는 대신 자기 자신 타입의 포인터를 멤버로 가짐으로써, 스스로의 주솟값을 표현하는 것이다. 그렇다면 왜 구조체가 자기 자신을 멤버로 못 가지는가? 구조체는 항상 고정 크기의 메모리 공간을 할당받아야 하는데 자기 자신을 멤버로 가진다면 그 '고정 크기'를 알 수 없기 때문이다. 그러나 자기 자신에 대한 포인터는 크기가 항상 4바이트(32비트 OS)나 8바이트(64비트 OS)로 같다. 그래서 구조체의 전체 크기를 계산 가능하다.
그럼 Java에서는 어떻게 자기 자신을 멤버로 포함시키는가 하면, 자바의 클래스는 레퍼런스 참조를 한다. 레퍼런스라 함은 상수 타입의 포인터와 같은 개념이다. 레퍼런스는 상수이면서 연산이 불가능한 포인터와 동일하다.
6. C++에서의 활용
C++은 STL의 list가 연결 리스트를 제공한다. 템플릿이므로 원하는 자료형으로 정의해 사용할 수 있다.직접 구현할 경우 C++에서 추가된 클래스 기능을 이용하여 정의하는 걸 빼면 C에서와 별반 다를 것은 없다. 다만 클래스는 스트럭트 타입의 변수와는 달리 안에 함수를 정의 가능하므로, 자주 쓰는 기능을 클래스 함수로 정의해 놓은 후 조금 더 쾌적하게 연결 리스트를 사용할 수 있다.
7. LISP와 연결 리스트
LISP에서 기본으로 제공하는 리스트는 기본적으로 리스트를 생성하는cons 연산에 의해 결합된 cell이 연결된 단순 연결형 리스트이다. 구현 상 리스트에 원소를 추가할 때에는 앞쪽에 붙인다. 예를 들어 (1 2 3)이라는 리스트는 아래 표현과 동일하다.(cons 1 (cons 2 (cons 3 nil)))
car, 첫 번째를 제외한 나머지 리스트를 구하는 cdr을 사용하여 루프를 돌면 매우 편리하게 리스트를 사용할 수 있다. 리스트가 비었는지 알아보려면 car을 수행하여 첫 번째 요소가 nil인지 검사하면 되고, 길이를 구하려면 nil이 나올때까지 루프를 돌면서 1씩 더한다든지 하는 식이다.(물론 이는 단순한 것을 예로 든 것으로, 이러한 기본적인 함수는 이미 다 구현되어 제공된다.)사투리 중에서는 필요성에 의해 양방향 리스트를 다른 자료형으로 구현하여 단순 연결형 리스트와 함께 기본 데이터 타입으로 지원하는 경우도 종종 있다. 이 경우는 리스트라고 안 부르고 벡터 등 다른 명칭으로 불린다.
8. 하스켈에서
하스켈 표준 라이브러리에서 제공하는 리스트가 연결 리스트이다. 아래와 같이 구현할 수 있다.data List a = [] | a : List a
[1] 배열: 영희 뒤에 지혜를 배치하려면 민수부터 하나씩 뒤로 밀고 지혜를 배치한 다음에 번호를 다시 매겨야겠다. / 연결 리스트: 지혜는 영희 뒤로 가.[2] 배열: 3번 나와봐. / 연결 리스트: 어디 보자. 철수가 1번이고, 그다음에 있는 영희가 2번이고, 그다음이 민수니까 민수가 3번이구나![3] 이 때문에 Java의 LinkedList의 경우처럼 배열처럼 인덱스 번호로 연산을 수행할 수 있도록 get(index)의 형태로 메서드를 제공하기도 한다. 물론 이것도 wrapping 수준이지 함수 자체를 까고 들어가 보면 역시 순서대로 찾는 것과 같다.[4] '현재' 노드를 삭제하기 위해서는 '이전' 노드가 가리키는 다음 공간이 '다음' 노드가 되도록 설정해야 한다. 즉, '현재' 노드를 삭제하면서 '현재' 노드의 위치에 '다음' 노드를 위치시켜야 된다는 의미이다.[5] https://www.manning.com/books/get-programming-with-haskell