C언어로 쉽게 풀어쓴 자료구조 — 06. 연결 리스트 1
6.1 리스트 추상 데이터 타입
리스트
자료를 저장할 때 사용되는 자료구조 중 하나로 현실의 예에서는 버킷 리스트나 해야 할 일을 표시한 표를 들 수 있다. 큐도 일종의 리스트로 볼 수 있다.리스트에는 항목들이 차례대로 정리되어 있고 각각의 항목은 순서나 위치를 가진다.
*리스트와 집합은 같아보일 수 있으나 집합은 순서의 개념이 없기 때문에 둘을 다르다고 할 수 있다.
리스트를 기호로 나타내면 다음과 같이 나타낼 수 있다.
L = (A,B,C,….,(N-1))
리스트의 기본적인 연산
1. 리스트에 새로운 항목 추가(삽입 연산)
2. 리스트에서 항목 삭제(삭제 연산)
3. 리스트에서 항목 탐색(탐색 연산)
리스트 ADT
● 객체 : n개의 element로 구성된 순서 있는 모임
● 연산
1. insert(list, pos, item) ::= pos 위치에 요소를 추가
2. insert_last(list, item) ::= 맨 끝에 요소를 추가
3. insert_first(list, item) ::= 맨 처음에 요소를 추가
4. delete(list, pos) ::= pos 위치의 요소를 제거
5. clear(list) ::= 리스트 전체를 삭제
6. get_entry(list, pos) ::= pos 위치의 요소를 반환
7. get_length(list) ::= 리스트의 길이를 반환
8. is_empty(list) ::= 리스트가 비었는지 검사
9. is_full(list) ::= 리스트가 다 찼는지 검사
10. print_list(list) ::= 리스트의 모든 요소 표시
리스트의 구현
리스트는 주로 배열과 연결 리스트를 통해 구현된다.
● 배열 : 리스트 ADT를 가장 간단하고 빠르게 구현 가능하나 크기가 제한되어 동적으로 크기를 조절하는 것이 어렵다. 또한 큰 배열을 만들면 메모리 공간과 CPU 자원의 낭비가 발생하고 데이터 추가와 삭제 시 기존의 데이터를 이동시켜야 한다.
● 연결리스트 : 포인터를 이용하여 필요할 때마다 중간에 속지를 추가해서 사용할 수 있는 바인더 공책과 비슷한 구조이다. 크기가 제한되지 않고 중간에 데이터를 추가하거나 삭제하기 수월한 유연함이 장점이나 구현이 복잡하고 임의의 항목을 추출할 때 많은 시간이 걸린다.
6.2 배열로 구현된 리스트
배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당되므로 이것을 리스트의 순차적 표현(sequential representation)라고도 한다.
배열을 이용하면 리스트의 항목을 아주 자연스럽게 저장할 수 있다.
리스트의 정의
배열과 항목의 개수를 구조체로 묶어서 ‘ArrayListType’이라는 새로운 타입을 정의한다.
기초 연산
리스트의 연산들을 함수로 구현할 때, 모든 연산은 구조체 포인터를 받는다.
함수안에서 구조체를 변경할 필요도 있는데 포인터를 사용하지 않으면 구조체의 복사본이 전달되어서 원본 구조체를 변경할 없다.
항목 추가 연산
다음 함수는 리스트의 맨 끝에 항목을 추가하는 함수이다.
위 함수에서 리스트에 빈 공간이 없다면 오류를 발생시킨다.
특정 위치에 데이터를 삽입하고 싶을 때에는 n번째에서부터 마지막 항목까지 한 칸 씩 오른쪽으로 이동하여 빈자리를 만들고 새로운 항목을 n번째에 저장하면 된다.
항목 삭제 연산
항목을 삭제하는 연산도 insert 함수처럼 n+1번째에서부터 마지막 항목까지를 한칸씩 앞으로 이동시켜야 한다.
실행 시간 분석
배열로 구현한 리스트의 시간 복잡도를 알아보면 임의의 항목에 접근하는 연산인 get_entry 연산은 인덱스를 사용하여 항목에 바로 접근할 수 있으므로 명백히 O(1)이다. 삽입이나 사겢 연산은 다른 항목들을 이동하는 경우가 많으므로 최악의 경우(리스트가 거의 차 있고 새로운 항목을 맨 앞에 삽입하는 경우) O(n)이고 최적의 경우(맨 마지막에 추가하는 경우) O(1)이다.
6–3 연결리스트
연결 리스트는 동적으로 크기가 변할 수 있고 삭제나 삽입 시 데이터를 이동할 필요가 없으므로 연결된 표현(linked represention)이라고도 한다. 연결된 표현은 포인터를 사용하여 데이터를 연결하는데 리스트 뿐만 아니라 트리나 스택 등의 다른 자료구조도 구현할 수 있다.
연결된 표현은 줄로 연결된 상자로 표현할 수 있는데 한 군데에 데이터를 모아두는 것을 포기하는 대신 흩어진 데이터를 줄로 연결하여 하나로 연결한 구조이다. 이런 식으로 물리적으로 흩어진 데이터를 서로 연결하여 하나로 연결한 것을 연결 리스트라고 하고 데이터를 묶는 줄은 포인터로 구현한다.
연결리스트를 사용하면 배열과 달리 중간에 값을 삭제하거나 삽입할 때, 전체 데이터를 이동할 필요없이 포인터만 변경해 주면 간단히 구현할 수 있다.
하나의 프로그램 안에는 동시에 여러 연결 리스트가 존재할 수 있다. 이런 경우, 연결리스트를 구별하는 것은 첫 데이터이다. 첫 데이터만 안다면 나머지는 줄을 따라서 순차적으로 알 수 있다. 연결 리스트의 다른 장점은 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 할당할 수 있다는 것이다.
연결리스트 역시 단점이 존재하는데 배열에 비해 상대적으로 구현이 어렵고 오류가 나기 쉽다. 또한 포인터를 추가적으로 저장해야 하므로 메모리 공간을 많이 차지하고 I번째 데이터를 찾기 위해서는 순차적으로 접근해야 한다.
연결 리스트의 구조
연결 리스트에서 데이터를 담는 상자를 노드(node)라고 부른다. 연결 리스트는 노드들의 집합이라고 볼 수 있다. 노드는 데이터 필드와 링크 필드로 구성되어 있다.
● 데이터 필드 : 저장하고자 하는 데이터(정수나 구조체 등)가 들어간다.
● 링크 필드 : 다른 노드를 가리키는 포인터가 저장되고 이를 이용하여 다른 노드에 접근할 수 있다.
연결 리스트에서는 연결 리스트의 첫 노드를 알아야만 전체의 노드에 접근할 수 있다. 따라서 연결 리스트마다 첫 노드를 가리키는 변수가 필요한데 이를 헤드 포인터(head pointer)라고 한다.
노드의 링크 필드는 NULL로 설정되는데 이는 더 이상 연결된 노드가 없다는 것을 의미한다.
연결 리스트의 노드들은 필요할 때마다 malloc()을 이용하여 동적으로 생성된다.
연결리스트의 종류
연결리스트의 종류는 3가지로 볼 수 있다.
● 단순 연결 리스트(singly linked list) : 하나의 방향으로만 연결되어 있는 연결리스트로 체인이라고도 한다. 단순 연결 리스트에서 마지막 노드의 링크는 NULL값을 가진다.
● 원형 연결 리스트(circular linked list) : 단순 연결 리스트와 같으나 마지막 노드의 링크가 첫 번째 노드를 가리킨다.
● 이중 연결 리슽(double linked list) : 각 노드마다 2개의 링크가 존재하는데 하나는 앞의 노드를 가리키고 다른 하나는 뒤의 노드를 가리킨다.
6–4 단순 연결 리스트
단순 연결 리스트를 구현하기 위해서는 다음을 생각해야 한다.
● 노드를 어떻게 정의할 것인가
● 노드를 어떻게 생성할 것인가
● 노드를 어떻게 삭제할 것인가
c언어에서는 다음과 같이 정의한다.
● 노드를 어떻게 정의할 것인가 -> 자기 참조 구조체 이용
● 노드를 어떻게 생성할 것인가 -> malloc()으로 동적 메모리 생성
● 노드를 어떻게 삭제할 것인가 -> free()로 동적 메모리 해제
노드의 정의
노드는 자기 참조 구조체를 이용하여 정의한다.
자기 참조 구조체 : 자기 자신을 참조하는 포인터를 포함하는 구조체
위 코드는 노드의 구조는 정의하였지만 아직 노드는 생성하지 않았다. 실제 구조체를 생성하려면 구조체 변수를 선언해야 한다.
공백리스트의 생성
단순 연결 리스트는 헤드 포인터만 있으면 모든 노드를 찾을 수 있다. 따라서 head를 정의하면 하나의 단순 연결 리스트가 만들어졌다고 볼 수 있다. 현재는 노드가 없으므로 head의 값은 NULL이다.
->어떤 리스트가 공백인지를 검사하려면 헤드 포인터가 NULL인지를 검사하면 된다.
노드의 생성
일반적으로 연결 리스트에서는 필요할 때마다 동적 메모리 할당을 이용하여 노드를 동적으로 생성한다.
head = (ListNode *)malloc(sizeof(ListNode));
위의 코드를 실행하면 노드가 하나 생성된다. 이때 노드에는 아무것도 들어있지 않는다.
head->data = 10;
head->link = NULL;
다음 코드는 생성된 노드의 데이터필드에 10, 링크 필드에 NULL을 넣어주는 것이다.
노드의 연결
노드의 생성을 통해 P라는 노드를 하나 더 생성한다. head와 P를 연결하기 위해서는 head->link에 P를 저장하면 된다.
head->link = P;
이러한 방법을 반복하면 단순 연결 리스트를 만들 수 있다.
단순 연결 리스트의 연산 구현
리스트가 커지게 되면 추상 데이터 타입에 정의된 전용 함수들을 통하여 노드를 추가하는 것이 편리하다 .
● 삽입 연산(insert_first())
리스트의 첫 부분에 새로운 노드를 추가하는 함수
ListNode* insert_first(ListNode *head, element value);
*head는 헤드 포인터, value는 추가되는 데이터이며 변경된 헤드 포인터를 반환하는 함수이기 때문에 반환된 값은 헤드 포인터에 저장해야 한다.
● 삽입 연산(insert())
가장 일반적인 경우로 중간에 데이터를 삽입하는 것이다. 이때는 반드시 선행 노드를 알아야 삽입이 가능하다.
*pre는 선행노드라고 가정
여기서 중요한 사실은 새로운 데이터를 삽입한 후에 다른 노드들을 이동할 필요가 없다는 점이다.
● delete_first()함수
첫 번째 노드를 삭제하는 함수이다.
● 삭제 연산 delete()
리스트 중간의 노드를 삭제하는 함수이다.
● print_list() 함수
연결 리스트 안의 모든 노드의 데이터를 출력하는 함수이다.노드의 링크값이 NULL이 아니면 계속하여 노드를 방문하고 NULL이라면 방문을 중단한다.
