자료구조_06.연결 리스트

이 글은 이해한 것을 적어놓은 글로, 'C언어로 쉽게 풀어쓴 자료구조'에서 가져왔다.

 

리스트 추상 데이터 타입

리스트의 소개

리스트에는 항목들이 차례대로 저장되어 있다. 리스트의 항목들은 순서 또는 위치를 가진다. 앞에서 살펴본 스택과 큐도 넓게 보면 리스트의 일종이다.

리스트는 집합하고는 다르다. 집합은 각 항목 간에 순서의 개념이 없다.

 

리스트 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) ::= 리스트의 모든 요소를 표시한다.

 

리스트의 구현

리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다.

• 배열 : 구현이 간단하고 속도가 빠르다는 장점이 있지만 ,리스트의 크기가 고정된다는 점과 리스트의 중간에 새로운 데이터를 삽입 및 삭제하기 위해서는 기존의 데이터들을 이동하여야 한다는 단점이 있다.
• 연결 리스트 : 포인터를 이용하여 연결 리스트를 만드는 방법으로, 크기가 제한되지 않고, 중간에서 쉽게 삽입 및 삭제할 수 있는 유연한 장점이 있지만, 구현이 복잡하고, 임의의 항목을 추출하려고 할 떄는 배열방식보다 시간이 많이 걸린다.

배열로 구현된 리스트

배열을 이용하여 리스트를 구현하면 순차적인 메모리 공간이 할당되므로, 리스트의 순차적 표현이라고도 한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_LIST_SIZE 100	//리스트의 최대크기

//리스트의 정의
typedef int element;	//항목의 정의
typedef struct {
	element array[MAX_LIST_SIZE];	//배열 정의(데이터 그릇)
	int size;	//현재 리스트에 저장된 항목들의 개수
}ArrayListType;

//기초연산

//오류 처리 함수
void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

//리스트 초기화 함수
void init(ArrayListType* L) {
	L->size = 0;
}

//공백 상태 검출 함수
int is_empty(ArrayListType* L) {
	return L->size == 0;	//리스트가 비어 있으면 True(1), 아니면 False(0) 반환
}

//포화 상태 검출 함수
int is_full(ArrayListType* L) {
	return L->size == MAX_LIST_SIZE;	//리스트가 가득 차 있으면 True(1), 아니면 False(0) 반환
}

//피크 함수
element get_entry(ArrayListType* L, int pos) {
	if (pos < 0 || pos >= L->size)	//pos가 0번째 이하거나 저장된 항목의 개수보다 이상이면 오류
		error("위치 오류");
	return L->array[pos];	//pos번째에 있는 데이터 반환
}

//리스트 출력
void print_list(ArrayListType* L) {
	for (int i = 0; i < L->size; i++)	//현재 저장된 항목수까지 출력
		printf("%d->", L->array[i]);
	printf("\n");
}

//맨끝에 항목 추가 함수
void insert_last(ArrayListType* L, element item) {
	if (L->size >= MAX_LIST_SIZE)	//리스트 최대크기까지 저장되어있으면 오류
		error("리스트 오버플로우");
	L->array[L->size++] = item;	//배열 맨끝(size)에 item값 저장 후 다음저장 준비
}

//중간에 항목 추가 함수
void insert(ArrayListType* L, int pos, element item) {
	if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
		for (int i = (L->size - 1); i >= pos; i--) {	//맨 끝부터 pos번째까지의 항목 오른쪽으로 한칸씩 이동
			L->array[i + 1] = L->array[i];
		}
		L->array[pos] = item;	//pos번째에 item값 삽입
		L->size++;
	}
}

element delete(ArrayListType* L, int pos) {
	element item;

	if (pos < 0 || pos >= L->size)
		error("위치 오류");
	item = L->array[pos];
	for (int i = pos; i < (L->size - 1); i++)	//pos번째부터 맨 끝까지 항목 왼쪽으로 한칸씩 이동
		L->array[i] = L->array[i + 1];
	L->size--;
	return item;
}

int main() {
	ArrayListType list;
	int sel;

	init(&list);
	while (1) {
		printf("삽입(1) 삭제(2) : ");
		scanf("%d", &sel);
		if (sel == 1) {
			int num, pos;
			printf("저장할 수, 저장할 포지션 : ");
			scanf("%d%d", &num, &pos);
			if (pos == list.size) {
				insert_last(&list, num);
				print_list(&list);
			}
			else {
				insert(&list, pos, num);
				print_list(&list);
			}
		}
		else if (sel == 2) {
			int pos;
			printf("삭제할 포지션 : ");
			scanf("%d", &pos);
			delete(&list, pos);
			print_list(&list);
		}
	}
	return 0;
}

 

연결 리스트

데이터들은 메인 메모리상의 어디에나 흩어져서 존재할 수 있다. 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법을 연결 리스트라고 한다.

 

장점

• 연결 리스트에서는 삽입 및 삭제가 앞뒤에 있는 데이터들을 이동할 필요가 없이 링크만 변경시켜주면 된다.
• 데이터를 저장할 공간이 필요할 떄마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다.

 단점

• 배열에 비하여 상대적으로 구현이 어렵고 오류가 나기 쉽다.
• 데이터뿐만 아니라 포인터도 저장하여야 하므로 메모리 공간을 많이 사용한다.
• i번째 데이터를 찾으려면 앞에서부터 순차적으로 접근하여야 한다.

연결 리스트의 구조

연결 리스트는 노드들의 집합이다.

노드들은 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서는 현재 노드가 가지고 있는 포인터를 이용하면 된다.

노드는 데이터필드(data field)와 링크 필드(link field)로 구성되어 있다. 데이터필드에는 저장할 값이, 링크 필드에는 다음 노드를 이어줄 포인터가 있다.

연결 리스트에서는 연결 리스트의 첫번째 노드를 알아야 만이 전체의 노드에 접근할 수 있어, 연결 리스트마다 첫 번째 노드를 가리키고 있는 변수가 필요한데 이것을 헤드 포인터(head pointer)라고 한다.

 

연결 리스트의 종류

• 단순 연결 리스트 : 체인(chain)이라고도 부르며, 일방향의 연결 리스트이다. 마지막 노드의 링크는 NULL값을 가진다.
• 원형 연결 리스트 : 단순 연결 리스트와 같으나 마지막 노드의 링크가 첫 번째 노드를 가리킨다.
• 이중 연결 리스트 : 각 노드마다 2개의 링크가 존재한다. 하나의 링크는 앞에 있는 노드를 가리키고 또 하나의 링크는 뒤에 있는 노드를 가리켜 쌍방향의 연결 리스트이다.

단순 연결 리스트

#include <stdio.h>
#include <stdlib.h>

typedef int element;

//노드의 정의
typedef struct ListNode{
	element data;
	struct ListNode* link;	//자기 참조 구조체 이용
}ListNode1;

//오류 처리 함수
void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

//첫부분 삽입 함수
ListNode1* insert_first(ListNode1* head, int value) {
	ListNode1* p = (ListNode1*)malloc(sizeof(ListNode1));	//동적 메모리 할당을 통하여 새로운 노드 p생성
	p->data = value;	//p->data에 value를 저장
	p->link = head;	//p->link를 현재의 head값으로 변경
	head = p;	//head를 p값으로 변경
	return head;	//변경된 헤드 포인터 반환
}

//노드 pre 뒤에 새로운 노드 삽입 함수
ListNode1* insert(ListNode1* head, ListNode1* pre, element value) {
	ListNode1* p = (ListNode1*)malloc(sizeof(ListNode1));	//동적 메모리 할당을 통하여 새로운 노드 p생성
	p->data = value;	//p->data에 value를 저장
	p->link = pre->link;	//p->link를 pre->link값으로 변경
	pre->link = p;	//pre->link를 p값으로 변경
	return head;	//변경된 헤드 포인터 반환
}

//첫 번째 노드를 삭제하는 함수
ListNode1* delete_first(ListNode1* head) {
	ListNode1* removed;
	if (head == NULL) return NULL;
	removed = head;	//head값을 removed에 복사
	head = removed->link;	//헤드 포인터에 removed->link값 저장
	free(removed);
	return head;
}

//pre가 가리키는 노드의 다음 노드를 삭제
ListNode1* delete(ListNode1* head, ListNode1* pre) {
	ListNode1* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

void print_list(ListNode1* head) {
	for (ListNode1* p = head; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}

int main() {
	ListNode1* head = NULL;

	for (int i = 0; i < 5; i++) {
		head = insert_first(head, i);
		print_list(head);
	}
	for (int i = 0; i < 5; i++) {
		head = delete_first(head);
		print_list(head);
	}
	return 0;
}