[자료구조] 4. 리스트(List)1 - 리스트ADT / 순차 리스트와 연결 리스트 / 순차 리스트 구현
리스트에는 데이터들이 차례대로 나란히 저장되어 있다.
[리스트의 특징]
리스트의 항목들은 순서 또는 위치를 가진다.
중복된 데이터의 저장을 막지 않는다.
4.1 리스트의 ADT
[리스트의 ADT]
◾ 객체 : n개의 요소들로 구성된 순서 있는 모임.
◾ 연산 :
리스트를 초기화한다.
특정 위치에 요소를 추가한다.
맨 처음 위치에 요소를 추가한다.
맨 끝 위치에 요소를 추가한다.
특정 위치의 요소를 제거한다.
리스트의 모든 요소를 제거한다.
특정 위치의 요소를 반환한다.
리스트의 길이를 구한다.
리스트가 비어있는지 검사한다.
리스트가 꽉 차있는지 검사한다.
리스트의 모슨 요소를 출력한다.
4.2 리스트의 구현 방법
"리스트는 곧 연결 리스트를 의미하는가?" → 아니다. 리스트 ≠ 연결리스트
리스트라는 자료구조는 구현 방법에 따라 순차 리스트와 연결 리스트로 나뉜다.
순차 리스트 : 배열을 기반으로 구현된 리스트
연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트. 포인터를 이용한다.
1) 순차리스트의 장단점
[장점]
간단하게 구현이 가능하다.
속도가 빠르다.
[단점]
리스트의 크기가 고정된다. → 배열의 특성상 동적으로 크기를 늘리거나 줄이는 것이 힘들다. 메모리 사용이 비효율적.
리스트의 중간에 새로운 데이터를 삽입하거나 삭제하기 위해서는 기존의 데이터들을 이동해야 한다.
2) 연결리스트의 장단점
[장점]
크기가 제한되지 않는다.
리스트의 중간에 쉽게 데이터를 삽입하거나 삭제할 수 있는 유연한 리스트를 구현할 수 있다.
[단점]
구현이 복잡하다.
특정 항목을 추출(탐색)할 때 배열을 사용하는 방법보다 시간이 오래 걸린다.
메모리 공간을 많이 사용한다. (데이터뿐만 아니라 포인터도 저장해야 하기 때문)
4.3 순차 리스트 구현
배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당된다. 이것을 리스트의 순차적 표현(sequential representation)이라고도 한다.
1) 순차 리스트의 정의
배열로 리스트를 구현하기 위해 ArrList라는 새로운 타입을 정의한다.
#define MAX_LIST_SIZE 100 //리스트의 최대 크기
typedef int element; //항목(배열 내의 요소) 정의
typedef struct {
element arr[MAX_LIST_SIZE]; //배열 정의
int size; //현재 리스트에 저장된 항목들의 개수
} ArrList;2) 기초 연산
순차 리스트의 연산들을 함수로 구현한다. 이때 원본 ArrList 구조체를 변경하기 위해 구조체 포인터를 매개변수로 받는다.
// [순차 리스트 기초 연산]
// 1. 오류 처리 함수
void error(char* message) {
fprintf(stderr, "%s\n", message); //에러 메세지 출력
exit(1); //
}
// 2. 리스트 초기화 함수
void init(ArrList* L) {
L->size = 0;
}
// 3. 리스트가 공백 상태인지 검사 - 비어 있으면 1, 그렇지 않으면 0을 반환
int isEmpty(ArrList* L) {
return L->size == 0;
}
// 4. 리스트가 가득 차 있는 상태인지 검사 - 가득 차 있으면 1, 그렇지 않으면 0을 반환
int isFull(ArrList* L) {
return L->size == MAX_LIST_SIZE;
}
// 5. 특정 위치의 항목 추출하기
element getEntry(ArrList* L, int pos) {
if (pos < 0 || pos >= L->size) // 리스트의 범위를 벗어나는 경우 에러
error("위치 오류");
return L->arr[pos];
}
// 6. 리스트 출력
void printList(ArrList* L) {
int i = 0;
for (i = 0; i < L->size; i++) { //배열을 순회하며 맨 앞부터 맨 끝 항목까지 출력
printf("%d -> ", L->arr[i]);
printf("\n");
}
}
3) 항목 추가 연산
리스트의 맨 끝에 항목을 추가하는 연산은 리스트가 오버플로우 상태가 아니라면 맨 끝이 되는 위치에 추가할 항목을 넣어주면 된다.
리스트의 특정 위치를 지정하여 항목을 추가하는 연산은 기존 리스트의 특정 위치부터 마지막까지의 항목들을 한 칸씩 뒤로 이동시켜 빈자리를 만든 후에 새로운 항목을 특정 위치에 추가한다.
// 7. 항목 추가(삽입)
// 1) 리스트의 맨 끝에 항목 추가
void insertLast(ArrList* L, element item) {
if (L->size >= MAX_LIST_SIZE) { //리스트에 빈공간이 없으면 에러
error("리스트 오버플로우");
}
L->arr[L->size++] = item; //배열 맨 끝에 항목 추가하고 리스트 크기 증가
}
// 2) 리스트의 특정 위치에 항목 추가
void insert(ArrList* L, int pos, element item) {
if (!isFull(L) && pos >= 0 && pos <= L->size) { //빈공간이 있고 리스트 크기 내의 위치일 경우
for (int i = (L->size - 1); i >= pos; i--)
L->arr[i + 1] = L->arr[i]; //한 칸씩 뒤로 이동
L->arr[pos] = item; //새로운 항목 추가
L->size++; //리스트 크기 증가
}
}4) 항목 삭제 연산
특정 위치의 항목을 삭제하는 연산은 추가하는 연산과는 반대로 항목을 삭제한 후 해당 위치의 바로 다음부터 마지막까지의 항목들을 한 칸씩 앞으로 이동시켜야 한다.
// 8. 항목 삭제 연산 - 삭제한 항목을 반환
element delete(ArrList* L, int pos) {
element item;
if (pos < 0 || pos >= L->size) //리스트 크기 범위를 벗어난 경우 에러
error("위치 오류");
item = L->arr[pos]; //삭제할 항목
for (int i = pos; i < (L->size - 1); i++)
L->arr[i] = L->arr[i + 1]; //한 칸씩 앞으로 이동
L->size--; //리스트 크기 감소
return item;
}
4.4 연결 리스트
포인터를 사용하여 데이터들을 연결하는 리스트 구현 방식을 연결된 표현(linked representation)이라고 한다.
배열은 순차적인 메모리 공간을 할당 받아 데이터를 한군데 모아서 저장하는 반면, 리스트의 연결된 표현에서의 데이터들은 메인 메모리상의 어디에나 흩어져 존재할 수 있다. 이렇게 흩어져 있는 자료들을 포인터로 서로 연결하여 하나로 묶는 방법이 연결 리스트인 것이다.
연결 리스트는 순차 리스트와는 달리 동적으로 크기가 변할 수 있고, 항목 삽입이나 삭제 시에 데이터를 이동할 필요가 없다.
1) 연결 리스트의 구조
연결 리스트는 '노드'라는 객체들의 집합이다.
노드들은 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용한다.
그렇기 때문에 노드에는 데이터를 저장할 공간과 다음 노드 주소를 가리켜 연결하는 공간이 필요하다.
[노드의 구성]
- 데이터 필드 : 데이터를 저장하는 영역.
- 링크 필드 : 다른 노드를 가리키는 포인터를 저장하는 영역. 포인터를 이용하여 다음 노드로 건너갈 수 있다.
첫 번째 노드는 연결 리스트을 구별하는 지표이다. 노드들의 집합, 즉 연결 리스트에 접근하기 위해서는 해당 연결 리스트의 첫 번째 노드를 알아야 한다. 따라서 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터(head pointer)라고 한다.
마지막 노드는 더 이상 연결되는 노드가 없다는 것을 알리기 위해 노드의 링크 필드를 NULL로 설정한다.
연결 리스트의 노드들은 필요할 때마다 malloc()을 이용하여 동적으로 생성된다.
2) 연결 리스트의 종류
① 단순 연결 리스트(singly linked list) : 하나의 방향으로만 연결되어 있는 연결 리스트. 마지막 노드의 링크는 NULL 값을 가진다. 체인(chain)이라고도 부른다.
② 원형 연결 리스트(circular linked list) : 단순 연결 리스트와 같으나 마지막 노드의 링크가 첫 번째 노드를 가리킨다.
③ 양방향 연결 리스트 / 이중 연결 리스트(doubly linked list) : 각 노드마다 2개의 링크가 존재하여 앞뒤 노드를 가리킨다.
