연결 리스트(Linked List)

 

리스트 : 데이터들을 순차적으로 저장할 때 사용되며, 각 항목은 순서를 가진다.

 

 

배열과 연결 리스트의 장단점

 

배열 : 구현이 간단하며 속도가 빠르지만, 크기가 정적이고 삽입 및 삭제가 까다로움.

연결 리스트 : 크기가 동적이며 삽입 및 삭제가 비교적 효율적이지만, 구현이 복잡하고 특정 위치의 데이터에 접근하려 할 때 배열보다 시간이 오래 걸림.

 

리스트의 추상 자료형 (Abstract Data Type)

 

• list_insert(list, pos, data) - 원하는 포지션에 데이터 삽입
• list_delete(list, pos) - 원하는 포지션의 데이터 제거
• list_clear(list) - 리스트의 모든 데이터 제거
• list_get_data(list, pos) - 원하는 포지션의 데이터 반환
• list_get_size(list) - 리스트의 길이 반환
• isEmpty(list) - 비어있는지 체크
• isFull(list) - 꽉 찼는지 체크
• list_all_print(list) - 리스트의 모든 데이터 출력

 

추상 자료형이 적용된 배열 리스트

 

typedef int element;
typedef struct {
	element array[MAX];
	int size; // 현재 리스트 원소의 개수 
}ArrayListType;

 

배열 리스트 타입이 구조체로 정의되었고, 상황에 따라 데이터에 대한 자료형이 다를 수 있기에 typedef를 이용 element를 정의하였다.

 

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

// 리스트가 비어있는지 체크
int is_empty(ArrayListType* L) {
	return L->size == 0;
}

// 리스트가 꽉 찼는지 체크
int is_full(ArrayListType* L) {
	return L->size == MAX;
}

 

리스트 포인터 타입으로 들어온 매개변수를 통해 구조체 내 size 변수를 0으로 초기화 해주는 함수가 있으며, 

size가 0이라면 비어있는 상태이기에 is_empty, size가 MAX라면 포화 상태이기에 is_full이라는 함수를 구현하였다.

 

// 원하는 인덱스의 데이터 반환
element list_get_data(ArrayListType* L, int pos) {
	if(pos < 0 || pos>= L->size)
		error("위치 에러");
	
	return L->array[pos]; 
}

 

배열 리스트 특정 위치에 해당하는 데이터를 반환 해주고 인덱스가 0보다 작거나 size를 넘어가는 경우 에러가 표시되며, 접근 속도는 O(1)의 시간복잡도를 가진다.

 

// 리스트의 모든 데이터 출력
void list_print(ArrayListType* L) {
	int i;
	for(i = 0; i<L->size; i++) {
		printf("%d -> ",L->array[i]);
	}
	printf("\n");
}

 

인덱스 0부터 size-1까지 모든 데이터를 순회하여 출력하는 함수이며, for문을 통해 간단하게 구현할 수 있다.

 

// 리스트의 맨 끝에 데이터를 삽입 
void list_insert_last(ArrayListType* L, element data) {
	if(L->size >= MAX) 
		error("리스트 오버플로우");
	
	L->array[L->size++] = data; 
}

// 리스트의 특정 위치에 데이터 삽입 
void list_insert(ArrayListType* L, int pos, element data) {
	int i;
	
	if(!is_full(L) && (pos >= 0) && (pos <= L->size)) {
		for(i = L->size-1; i>=pos; i--) {
			L->array[i+1] = L->array[i];
		}
		L->array[pos] = data;
		L->size++;
	}
}

 

배열 리스트의 끝에 데이터가 삽입되는 부분은 현재 size 인덱스에 접근하여 데이터를 삽입한 뒤 증감연산자를 활용해 size를 증가시켜준다. 만약, MAX보다 크거나 같은 경우 오버플로우로 error가 표시된다.

 

특정 위치에 데이터를 삽입하는 경우에는 위치에 해당하는 인덱스가 0과 size 사이여야 하고, 리스트가 포화 상태이면 안된다는 조건이 있어야한다. 이후 size-1 부터 pos까지 한 칸씩 뒤로 당기는 작업이 이뤄지며 pos에 해당하는 위치에 데이터가 삽입된다. 

 

// 리스트의 특정 위치 데이터 제거
element list_delete(ArrayListType* L, int pos) {
	int i;
	element data; 
	
	if(pos < 0 || pos >= L->size)
		error("위치 에러");
	
	data = L->array[pos];
	for(i = pos; i<(L->size-1); i++) {
		L->array[i] = L->array[i+1];
	}
	L->size--;
	
	return data;
}

 

특정 위치의 데이터가 제거되는 경우에도 중간에 삽입했을 때의 작업과 비슷한 작업이 이뤄지는데, 데이터가 없는 위치를 제거시키는 것을 방지하기 위해 예외처리를 해주고, 올바른 위치가 매개변수로 들어왔다면 특정 위치에 해당하는 데이터를 담아 놓는다. 이후, 반복문을 통해 pos 부터 size-1까지 한 칸씩 앞으로 당겨지며, 제거 된 데이터를 반환한다.

 

// 리스트의 특정 위치의 원소를 대체
void list_replace(ArrayListType* L, int pos, element data) {
	if(L->array[pos])
		L->array[pos] = data; 
} 

// 리스트의 사이즈를 반환 
int list_get_size(ArrayListType* L) {
	return L->size; 
}

// 리스트의 모든 데이터를 0으로 초기화 
void list_clear(ArrayListType* L) {
	int i;
	for(i = 0; i<L->size; i++) {
		L->array[i] = 0;
	}
}

 

이외 추가적인 ADT로는 특정 위치의 데이터를 대체하는 함수와, 현재의 배열 리스트 사이즈를 반환하는 함수,

모든 데이터를 0으로 초기화시키는 함수가 있다.

 

 

다음은 단순 연결 리스트에 관한 내용이다.

 

노드 정의

typedef struct ListNode {
	int data;
	struct ListNode* link;
}NODE;

노드는 자기 참조 구조체를 이용하여 정의가 되며, 데이터 필드와 링크 필드로 구성이 되어있다.

링크 필드에는 다음 노드의 주소값이 저장된다.

 

노드 생성 및 연결

NODE* head = NULL; // 리스트가 공백 리스트인지 체크하려면 head 포인터가 NULL인지 확인하면 된다. 

int main() {
	head = (NODE*)malloc(sizeof(NODE)); // 노드 생성
	head->data = 10;
	head->link = NULL;
	
	NODE* p = (NODE*)malloc(sizeof(NODE)); 
	p->data = 20;
	p->link = NULL;
	
	head->link = p; // 노드 연결 
}

동적 메모리 할당을 이용해 노드를 동적으로 생성하면 동적 메모리의 주소가 포인터 변수에 담긴다. 연결할 노드가 없는 경우 링크필드에는 NULL값으로 정의해주고, 노드와 노드를 연결시키려면 링크필드에 노드를 대입해준다.

 

단순 연결 리스트의 추상 자료형

사이즈가 작다면 위와 같이 하나의 함수 안에 노드를 생성하고 연결시켜도 되지만, 리스트의 크기가 커지면 추상 자료형에 정의된 함수들을 이용하여 노드를 추가하는 것이 편리하다.

 

• insert_first(): 리스트의 첫 부분에 노드 삽입
• insert(): 리스트의 중간 부분에 노드 삽입
• delete_first(): 리스트의 첫 번째 노드를 삭제
• delete(): 리스트의 중간 노드를 삭제
• print_list(): 리스트에 있는 모든 노드들을 출력

 

Insert_first()

NODE* insert_first(NODE* head, int data) {
	NODE* p = (NODE*)malloc(sizeof(NODE));
	p->data = data;
	p->link = head;
	head = p;
	
	return head;
}

 

1. 동적 메모리 할당을 통해 새로운 노드 p를 생성한다.
2. data를 저장하고, p→link에는 현재의 head값으로 변경한다.
3. head를 p값으로 변경하고, 변경된 헤드 포인터를 반환한다.

 

Insert()

NODE* insert(NODE* head, NODE* prev, int data) {
	NODE* p = (NODE*)malloc(sizeof(NODE));
	p->data = data;
	p->link = prev->link;
	prev->link = p;
	
	return head;
}

 

1. 동적 메모리 할당을 통해 새로운 노드 p를 생성한다.
2. data를 저장한 후, p→link에 선행 노드 prev의 link 값을 대입한다.
3. 선행 노드 prev 링크 필드는 새로운 노드인 p를 가르키게 된다.
4. 변경된 헤드 포인터를 반환한다.

 

delete_first()

NODE* delete_first(NODE* head) {
	NODE* removed;
	if(head == NULL) return NULL;
	removed = head;
	head = removed->link;
	free(removed);
    
	return head;
}

 

1. 공백 리스트가 아닌 경우, 헤드 포인터의 값을 removed에 복사한다.
2. 헤드 포인터의 값을 head(=removed)→link로 변경한다.
3. removed가 가르키는 동적 메모리를 해제한다.
4. 변경된 헤드 포인터를 반환한다.

 

delete()

NODE* delete_(NODE* head, NODE* prev) {
	NODE* removed = prev->link;
	prev->link = removed->link;
	free(removed);
	return head;
}

 

1. 삭제할 노드를 찾은 후, prev가 가르키고 있었던 구조체의 링크필드 값을 removed에 복사한다.
2. prev의 링크필드 값을 removed→link 값으로 변경시킨다.
3. removed가 가르키는 동적 메모리를 해제한다.
4. 변경된 헤드 포인터를 반환한다.

 

print_list()

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

 

각 리스트의 노드들을 방문하면서 링크필드 값이 NULL이 아닐때까지 노드의 데이터들을 출력하고, 링크필드의 값이 NULL이라면 연결 리스트의 끝에 도달한 것이다.