1. 연결 리스트란?
연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조입니다. 각 노드는 데이터를 저장하는 데이터 공간과 다음 노드의 주소를 가리키는 포인터 공간으로 구성됩니다.
2. 연결 리스트의 구성 요소
- 노드(Node): 데이터와 다음 노드의 주소를 가지는 구성요소로서, 연결 리스트의 기본 단위입니다.
- 데이터 공간: 실제 데이터가 저장되는 공간입니다.
- 포인터 공간: 다음 노드의 주소를 가리키는 포인터가 저장되는 공간입니다.
3. 연결 리스트의 특징
- 동적 할당: 연결 리스트는 동적으로 노드를 추가하거나 삭제할 수 있어 크기 조정이 가능합니다.
- 불연속 메모리 할당: 노드들은 메모리 어느 곳에나 할당될 수 있습니다.
- 삽입 및 삭제 용이: 노드 간의 포인터 조작만으로 삽입과 삭제가 가능합니다.
- 크기 제한 없음: 필요한 만큼 노드를 추가할 수 있으므로 크기에 제한이 없습니다.
4. 연결 리스트의 종류
- 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드의 주소만 가리키는 형태의 연결 리스트입니다.
- 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 노드와 다음 노드의 주소를 모두 가리키는 형태의 연결 리스트입니다.
- 순환 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 형태로 순환하는 연결 리스트입니다.
4-1. 단일 연결 리스트 (Singly Linked List)
- 각 노드는 다음 노드의 주소를 가리키는 포인터를 갖습니다.
- 접근 및 검색에는 시간이 더 걸리지만, 삽입과 삭제는 빠르게 수행할 수 있습니다.
- 시간 복잡도: 접근 및 검색 (O(n)), 삽입 및 삭제 (O(1))
4-2. 이중 연결 리스트 (Doubly Linked List)
- 각 노드는 이전 노드와 다음 노드의 주소를 가리키는 포인터를 갖습니다.
- 단일 연결 리스트보다 복잡하지만 양방향 접근이 가능합니다.
- 시간 복잡도: 접근 및 검색 (O(n)), 삽입 및 삭제 (O(1))
4-3. 순환 연결 리스트 (Circular Linked List)
- 마지막 노드가 첫 번째 노드를 가리키는 형태입니다.
- 순환적으로 요소에 접근할 수 있습니다.
5. 연결 리스트의 주의할 점
- 노드의 주소 유지: 노드 간의 주소가 정확하게 유지되어야 합니다. 잘못된 주소 설정으로 데이터 유실 문제가 발생할 수 있습니다.
- 메모리 누수: 노드를 삭제할 때 해당 메모리를 반환해야 합니다. 그렇지 않으면 메모리 누수가 발생할 수 있습니다.
6. 연결 리스트 vs 배열
- 배열: 고정된 크기, 빠른 접근, 메모리 효율적, 추가/삭제가 비효율적
- 연결 리스트: 동적 크기 조정 가능, 느린 접근, 메모리 불연속, 추가/삭제 용이
7. 연결 리스트 활용 문제 풀어보기
문제 1
아래 함수를 실행했을 때의 결과값을 구하시오.
// listNode: 1 -> 2 -> 3 -> 4 -> 5
void display(ListNode *h)
{
while (h != NULL) {
printf("%d ", h->data);
h = h->link;
}
printf("\n");
}문제 2
연결 리스트와 배열을 비교했을 때, 각각의 빠른 연산들을 작성하세요.
문제 3
이중 연결 리스트의 네 가지 연산(접근, 검색, 삽입, 삭제) 각각의 시간 복잡도를 서술하세요
문제 4
순환 연결 리스트를 구현하려면 어떤 점을 고려해야 할까요?
문제 5
이중 연결 리스트를 활용하여 스택을 구현하는 방법을 간략하게 설명해보세요.
웹솔루션과