[C언어로 쉽게 풀어쓴 자료구조] Chapter6. 연결 리스트 I (1)

6.1 리스트 추상 데이터 타입

 

● 리스트: 항목들이 순서 또는 위치를 가진 채로 차례대로 저장돼 있는 자료구조

- 기호로 L = (item0, item1, item2, ... , item n-1)과 같이 나타낸다.

- 리스트의 기본적인 연산으로는 새로운 항목 추가(삽입), 항목 삭제(삭제), 특정한 항목 찾기(탐색) 등이 있다.

 

● 리스트의 구현

최상단 그림처럼 리스트는 배열과 연결 리스트를 이용하여 구현할 수 있다.

배열 리스트는 구현이 쉽고 빠르지만 크기가 고정되고,

연결 리스트는 크기가 제한되지 않고 중간에 삽입이나 삭제를 유연하게 구현할 수 있지만 구현이 복잡하고,

i번째 항목을 추출하려고 할 때는 배열을 사용할 때보다 시간이 오래 걸린다.

 

6.2 배열로 구현된 리스트

● 리스트의 정의, 기초 연산, 항목 추가 연산, 항목 삭제 연산, 테스트 프로그램

#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_List(ArrayListType *L){
	L->size =0;
}


int is_empty(ArrayListType *L){
	return L->size ==0;
}


int is_full(ArrayListType *L){
	return L->size == MAX_LIST_SIZE;
}

element get_entry(ArrayListType *L,int pos){
	if(pos<0 || pos>L->size){
		error("위치 오류");
	}
	return L->array[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(is_full(L)){
		error("리스트 오버플로우");
	}
	L->array[L->size++] = item;
}

void insert(ArrayListType *L, int pos, element item){
	if(is_full(L)){
		error("리스트 오버플로우");
	}
	if(pos<0 || pos>L->size){
		error("위치 오류1");
	}
	for(int i=L->size-1;i>=pos;i--){
		L->array[i+1] = L->array[i];
	}
	L->array[pos] = item;
	L->size ++;
}

void insert_first(ArrayListType *L, element item){
	if(is_full(L)){
		error("리스트 오버플로우");
	}
	
	for(int i=L->size-1;i>=0;i--){
		L->array[i+1] = L->array[i];
	}
	L->array[0] = item;
	L->size ++;
}

element delete(ArrayListType *L, int pos){
	if(pos<0 || pos>L->size){
		error("위치 오류");
	}
	element item = L->array[pos];
	for(int i=pos; i<L->size-1;i++){
		L->array[i] = L->array[i+1];
	}
	L->size--;
	return item;
}



int main(){
	ArrayListType *list;
	list = (ArrayListType*)malloc(sizeof(ArrayListType));
	init_List(list);
	
	insert(list,0,10);
	print_List(list);
	insert(list,0,20);
	print_List(list);
	insert(list,0,30);
	print_List(list);
	insert_last(list,40);
	print_List(list);
	delete(list,0);
	print_List(list);
	insert_first(list,80);
	print_List(list);
	return 0;
}

183p 도전문제 1번, 2번을 반영한 코드이다.

 

● 실행 시간 분석

임의의 항목에 접근 : O(1)

삽입이나 삭제 : O(n), 최악의 경우 / O(1), 리스트의 맨 끝에 삽입하는 경우

 

6.3 연결 리스트

● 연결 리스트: 물리적으로 흩어져 있는 자료들을 서로 포인터를 통해 연결하여 하나로 묶는 방법

 

장점:

- 삽입과 삭제 연산 시에 앞뒤에 있던 데이터들을 모두 이동시킬 필요없이 포인터를 재지정하는 것만으로

연산을 수행할 수 있어 시간이 단축된다.

- 첫 번째 데이터만 알면 나머지 데이터들은 포인터를 따라가다 보면 얻을 수 있다.

- 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다.

 

단점:

- 배열에 비해 상대적으로 구현이 어렵고 오류가 나기 쉽다.

- 데이터와 포인터를 함께 저장하여야 하므로 메모리 공간을 많이 사용한다.

- i번째 데이터를 찾으려면 인덱스로 바로 접근하던 배열과 달리, 앞에서부터 순차적으로 접근하여야 한다.

 

 

● 연결 리스트의 구조

- 연결 리스트는 노드의 집합

- 노드는 메모리의 어떤 위치에나 있을 수 있으며 다른 노드로 가기 위해서는 현재 노드가 가진 포인터를 이용

- 데이터를 담는 데이터 필드와 포인터를 담는 링크 필드로 구성

- 연결 리스트의 첫 번째 노드를 알아야 전체 노드에 접근 가능, 첫 번째 노드를 가리키는 변수 = 헤드 포인터

- 마지막 노드의 링크 필드는 NULL

 

6.4 단순 연결 리스트

● 단순 연결 리스트:  하나의 방향으로만 연결되어 있는 연결 리스트, 속칭 체인(chain)

- 노드들이 하나의 링크 필드를 가지고 있고 마지막 노드의 링크 필드 값은 NULL

 

● 노드의 정의, 공백 리스트의 생성, 노드의 생성, 노드의 연결

- 노드는 자기 자신을 참조하는 포인터를 포함하는 구조체인 자기 참조 구조체

- 노드는 데이터 필드와 링크 필드를 포함한다.

 

- head 포인터 하나가 정의되면 새로운 하나의 단순 연결 리스트가 생성된 것이고,

리스트가 공백 상태라면  head 포인터는 NULL

 

- 각 노드는 malloc() 함수를 이용하여 노드의 크기만큼 동적 메모리를 동적으로 할당받아서 사용

- link 필드를 NULL로 하여 노드를 생성할 수 있고, 연결 리스트에 연결하려면 다른 노드의 포인터 p를

link 필드에 node->link = p로 연결할 수 있다.

 

♠ 190p Quiz

01 head

02 링크

03 삽입, 삭제 연산 시에 시간을 절약한다. 노드를 동적으로 생성하여 연결 리스트를 확장시킬 수 있다.

 

6.5 단순 연결 리스트의 연산 구현

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

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

void error(char *message){
	fprintf(stderr,"%s\n",message);
	exit(1);
}

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

ListNode* insert(ListNode *head, ListNode *pre, element value){
	ListNode *p = (ListNode*)malloc(sizeof(ListNode));
	p->data=value;
	p->link = pre->link;
	pre->link = p;
	return head;
}

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

ListNode* delete(ListNode* head, ListNode* pre){
	ListNode* removed;
	removed = pre->link;
	pre->link = removed ->link;
	free(removed);
	return head;
}

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

element get_entry(ListNode* head, int index){
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p= head;
	for(int i=0;i<index-1;i++){
		p = p->link;
	}
	return p->data;
}

int get_count(ListNode* head){
	int count=0;
	for(ListNode *p = head; p!=NULL;p= p->link){
		count++;
	}
	return count;
}

int main(void){
	ListNode *head = NULL;
	for(int i=0; i<5;i++){
		head= insert_first(head,i);
		print_list(head);
	}
	
	printf("3번째 인덱스는 %d\n",get_entry(head,3));
	printf("리스트에는 %d개의 노드가 있습니다\n",get_count(head));
	
	for(int i=0; i<5;i++){
		head= delete_first(head);
		print_list(head);
	}
	return 0;
}

199p 도전문제, Quiz02까지 구현한 코드    * get_entry와 get_count

 

♠ 199p Quiz

01 삭제하려는 노드를 가리키는 이전 노드 포인터 변수

02 상단 코드 참조