05 연결리스트 Linked List
출처
- C언어로 쉽게 풀어쓴 자료구조(천인국, 공용해, 하상호 저)
1. 연결리스트의 개념
1-1. 리스트란?
리스트는 자료를 정리하는 방법 중의 하나로, 할일 목록 등과 같은 것들을 관리할 때 쓰이는 자료구조이다. 리스트는 항목이 차례대로 저장되어 있으며, 각 항목들은 순서와 위치를 가지고 있다.
1-2. 연결리스트의 기능
리스트의 기능는 삽입, 삭제, 탐색 등의 연산을 수행할 수 있고, Node를 통해 연결된다. 리스트의 ADT는 아래와 같다.
- 객체: n개의 element 형으로 구성된 순서가 있는 모임
- 연산
insert(list, pos, item) ::= pos 위치에 요소를 추가한다.
insert_last(list, item) ::= 맨 끝에 요소를 추가한다.
insert_first(list, item) ::= 맨 처음에 요소를 추가한다.
delete(list, pos) ::= pos 위치의 요소를 제거한다.
clear(list) ::= 리스트의 모든 요소를 제거한다.
get_entry(list, pos) ::= pos 위치의 요소를 반환한다.
get_length(list) ::= 리스트의 길이를 구한다.
is_empty(list) ::= 리스트가 비었는지를 검사한다.
is_full(list) ::= 리스트가 꽉 찼는지를 검사한다.
print_list(list) ::= 리스트의 모든 요소를 표시한다2. 리스트 구현
리스트를 구현하려면 배열 또는 포인터 및 Node를 이용해야한다. 배열을 이용하면 간단하게 리스트를 만들 수 있으나, 배열은 정적 타입이라 크기가 고정된다는 단점이 있다. 반면 포인터를 이용하는 연결리스트 방식으로 구성하면 동적으로 메모리를 할당할 수 있기 때문에 좋지만, 구현이 복잡하고 배열보다 시간이 많이 걸린다.
2-1. 배열로 구현한 리스트
배열을 이용해 리스트를 구현하면 순차적인 메모리 공간이 할당되므로, 이를 리스트의 순차적 표현(Sequential representation)이라고 한다.
#define MAX_LIST_SIZE 100
typedef int element;
typedef struct {
element array[MAX_LIST_SIZE]; // 배열 정의
int size; // 리스트에 저장된 항목 개수
} ArrayListType;배열로 구현한 리스트의 시간복잡도를 표로 정리해봤다.
| 연산 | 시간복잡도 | 설명 |
|:--: |:--: |:--: |
| 인덱스로 접근 | O(1) | 인덱스를 통해 항목에 바로 접근 가능 |
| 삭제 연산 | O(n) | 삭제하고 뒤의 요소를 당겨와 빈 공간을 채워야함 |
| 맨 앞에 삽입 | O(n) | 삽입하기 전에 뒤에 있는 요소를 밀어야함 |
| 맨 뒤에 삽입 | O(1) | 그냥 끝자리에 삽입만 하면 됨 |
2-2. 단순 연결리스트
연결 리스트는 동적으로 크기가 변할 수 있고 삭제나 삽입 연산할 때 배열과 달리 이동이 필요가 없다. 이를 연결된 표현(linked representation)이라고 부른다.
연결된 표현은 줄로 연결된 상자들을 생각하면 된다. 연결된 표현은 데이터를 한 군데에 모아두는 것을 포기한다. 대신 메모리상에 흩어져있는 데이터들을 연결하여 묶는다. 여기서 상자를 엮는 줄의 역할을 포인터(pointer)가 한다.
연결리스트의 종류는 크게 3가지가 있다.
- 단순 연결 리스트
- 원형 연결 리스트
- 이중 연결 리스트
이 중 단순 연결 리스트를 살펴보자. 이 자료구조는 Head노드를 잃어버리면 데이터 전체를 못 쓰게되는 단점이 있다. 또한 참조하는 주소 중 하나가 잘못되면 체인이 끊어지기 때문에 뒤의 자료가 유실된다. 여러모로 안정적인 자료구조는 아니다.
typedef int element;
typedef struct {
element data;
struct ListNode *link;
} ListNode;
...
int main(void) {
ListNode *head = NULL; // 헤더 생성
...
}단순 연결리스트의 시간복잡도는 아래와 같다.
| 연산 | 시간복잡도 | 설명 |
|---|---|---|
| 해당 데이터로 접근 | O(n) | 인덱스가 없기 때문에 데이터를 찾는데 시간이 걸림 |
| 맨 앞 삭제 연산 | O(1) | 해당 요소는 삭제하고 앞뒤만 서로 연결해주면 됨 |
| 맨 뒤 삭제 연산 | O(n) | 맨 뒤의 노드를 탐색하는데 시간이 걸림 |
| 선택 삭제 연산 | O(n) | 해당 요소를 검색하는데 시간이 걸림 |
| 맨 앞에 삽입 | O(1) | 해당 요소를 헤더와 헤더의 링크부분의 사이에 연결하면 됨 |
| 맨 뒤에 삽입 | O(n) | 맨 뒤의 노드를 탐색하는데 시간이 걸림 |
| 선택 삽입 | O(n) | 해당 위치를 탐색하는데 시간이 걸림 |