[Do it 알고리즘] 09. 리스트(1)

란지·2021년 9월 25일
c언어do it 알고리즘알고리즘자료구조
0

Do it 알고리즘

목록 보기
4/7

09. 리스트

09-1. 선형 리스트

선형 리스트란?

리스트 : 데이터를 순서대로 나열해 놓은 자료구조
선형 리스트 / 연결 리스트 : 가장 단순한 구조를 가진 리스트


데이터가 사슬 모양으로 연결한 형태. 하나 이상의 칸을 건너 뛸 수 없음

  • 노드/요소 : 리스트의 데이터. 데이터와, 다음 노드를 가리키는 포인터 존재
  • 머리 노드(head node) : 처음에 있는 노드
  • 꼬리 노드(tail node) : 끝에 있는 노드
  • 앞쪽 노드(predecessor node) : 하나의 노드에 대해 바로 앞에 있는 노드
  • 다음 노드(successor node) : 하나의 노드에 대해 바로 뒤에 있는 노드

배열로 선형 리스트 만들기

다음 노드 꺼내기

배열의 각 요소에 데이터가 순서대로 저장되어 있으므로
'1만큼 큰 인덱스를 갖는 요소'에 접근

노드의 삽입과 삭제

데이터의 삽입 시 삽입 요소 다음의 모든 요소를 하나씩 뒤로 밀어야 하고,
데이터의 삭제 시 모든 요소를 뒤로 밀거나 앞으로 당겨야 함

선형리스트의 문제
1. 쌓이는 데이터의 크기를 미리 알아야 함
2. 데이터의 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않음

09-2. 포인터로 연결 리스트 만들기

포인터로 연결 리스트 만들기

연결 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면 앞에서 제시한 데이터를 밀고 당기는 문제를 해결할 수 있음

typedef struct __node {
	Member data;		/* 데이터 */
    struct __node *next;	/* 다음 노드를 가리키는 포인터 */
} Node;


* 자기 참조(self-referential)형 자료 구조 : 자기 자신과 같은 자료형의 객체를 가리키는 데이터를 가지고 있는 자료구조

  • data : 데이터를 저장하는 멤버
  • next : 자기 자신과 같은 구조체를 가리키는 포인터. 꼬리 노드의 next 값은 NULL

연결 리스트를 관리하는 구조체 List

연결 리스트를 관리하며 두 멤버로 구성되어 있고 모두 Node에 대한 포인터 자료형을 가지고 있음

/* 포인터를 사용한 선형 리스트(헤더) */
#ifndef ___LinkedList
#define ___LinkedList

#include "Member.h"

/*--- 노드 ---*/
typedef struct __node {
	Member data;		/* 데이터 */
	struct __node *next;	/* 뒤쪽 포인터(뒤쪽 노드에 대한 포인터) */
} Node;

/*--- 선형 리스트 ---*/
typedef struct {
	Node *head;		/* 머리 노드에 대한 포인터 */
	Node *crnt;		/* 선택한 노드에 대한 포인터 */
} List;

/*--- 선형 리스트를 초기화 ---*/
void Initialize(List *list);

/*--- 함수 compare로 x와 같은 노드를 검색 ---*/
Node *search(List *list, const Member *x, int compare(const Member *x, const Member *y));

/*--- 머리에 노드를 삽입 ---*/
void InsertFront(List *list, const Member *x);

/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(List *list, const Member *x);

/*--- 머리 노드를 삭제 ---*/
void RemoveFront(List *list);

/*--- 꼬리 노드를 삭제 ---*/
void RemoveRear(List *list);

/*--- 선택한 노드를 삭제 ---*/
void RemoveCurrent(List *list);

/*--- 모든 노드를 삭제 ---*/
void Clear(List *list);

/*--- 선택한 노드의 데이터를 출력 ---*/
void PrintCurrent(const List *list);

/*--- 선택한 노드의 데이터를 출력(줄바꿈 문자 포함) ---*/
void PrintLnCurrent(const List *list);

/*--- 모든 노드의 데이터를 리스트 순서대로 출력 ---*/
void Print(const List *list);

/*--- 선형 리스트 종료 ---*/
void Terminate(List *list);
#endif

head : 연결 리스트의 머리 노드를 가리키는 포인터
crnt : 현재 선택한 노드를 가리키는 포인터. '검색'한 노드를 선택하고 '삭제'하는 용도

노드를 만드는 AllocNode 함수

Node형 객체를 만들고 만든 객체의 포인터를 반환

static Node *AllocNode(void)
{
	return calloc(1, sizeof(Node));
}

노드의 멤버 값을 설정하는 함수 SetNode 함수

Node형 객체의 두 멤버(data, next)의 값을 설정하는 함수

첫 번째 매개변수 n으로 전달받은 포인터가 가리키는 Node형 객체에 x가 가리키는 값을 대입하고 n의 next에 세 번째 매개변수로 전달받은 next를 대입함

static void SetNode(Node *n, const Member *x, const Node *next)
{
	n->data = *x;		/* 데이터 */
	n->next = next;		/* 뒤쪽 포인터 */
}

연결 리스트를 초기화하는 Initialize 함수

연결 리스트를 사용하기 전에 초기화하는 함수

void Initialize(List *list)
{
	list->head = NULL;	/* 머리 노드 */
	list->crnt = NULL;	/* 선택한 노드 */
}

머리 노드를 가리키는 list->head에 NULL 값을 대입하여 노드가 하나도 없는 텅 빈 연결 리스트 생성. 빈 연결 리스트는 노드가 하나도 없는 상태이므로 head가 가리키는 노드도 존재하지 않음
* list->crnt에도 NULL 값을 대입하여 노드를 선택하지 않은 상태로 초기화

연결리스트가 비어 있는지 판단하는 방법 [a]
[a]는 노드가 하나도 없는 빈 연결 리스트

list->head == NULL		/* 연결 리스트가 비어 있는지 확인합니다. */

노드가 1개인 연결 리스트를 파난하는 방법 [b]
[b]는 연결 리스트에 노드가 1개만 있는 상태

list->head->next == NULL	/* 노드가 1개인지 확인합니다. */

변수 list->head가 가리키는 노드는 머리 노드 A
연결 리스트에는 1개의 노드만 있기 때문에 머리 노드 A는 리스트의 꼬리 노드이기도 함
따라서 next의 값은 NULL

노드가 2개인 연결 리스트를 판단하는 방법[c]
[c]는 노드가 2개 있는 상태 - 머리 노드는 A, 꼬리 노드는 B

list->head->next->next == NULL	/* 노드가 2개인지 확인합니다. */

list->head가 가리키는 노드 A의 next는 노드 B를 가리킴
꼬리 노드 B의 next는 NULL 값을 가지고 있음

머리 노드인지 판단하는 방법
자료평이 Node *형인 변수 p는 리스트의 노드 중 하나를 가리킴

p == list->head			/* p가 가리키는 노드가 머리 노드인지 확인합니다. */

꼬리 노드인지 판단하는 방법
자료평이 Node *형인 변수 p는 리스트의 노드 중 하나를 가리킴

p->next == NULL			/* p가 가리키는 노드가 꼬리 노드인지 확인합니다. */

검색을 수행하는 Search 함수

어떤 조건을 만족하는 노드를 검색

  • 찾은 노드에 대한 포인터 반환
  • 검색에 실패할 경우 NULL 반환

    선형 검색 - 머리 노드부터 스캔
    아래 조건 중 하나만 성립하면 노드 스캔 종료
  1. 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우
  2. 검색 조건을 만족하는 노드를 찾은 경우
  • list : 검색 대상인 연결리스트를 가리키는 포인터
  • x : 검색하는 키 값을 저장한 데이터를 가리키는 포인터
  • compare : 두 번째 매개변수 x가 가리키는 객체와 연결 리스트의 노드와 데이터를 비교하는 함수를 가리키는 포인터. 검색에 성공하면 0을 반환
Node *search(List *list, const Member *x, int compare(const Member *x, const Member *y))
{
/*l3*/	Node *ptr = list->head;
	while (ptr != NULL) {
			if (compare(&ptr->data, x) == 0) {	/* 키값이 같은 경우 */
					list->crnt = ptr;
				return ptr;			/* 검색 성공 */
			}
/*l9*/		ptr = ptr->next;				/* 다음 노드를 선택 */
	}
/*l11*/	return NULL;						/* 검색 실패 */
}

l3 : 스캔하고 있는 노드를 가리키는 변수 ptr을 list->head로 초기화
while문 : ptr 값이 NULL이면 스캔할 노드가 없음을 의미
while문 내 if문 : 스캔하고 있는 노드의 데이터(ptr->data_와 x가 가리키는 데이터 비교. 검색 성공 시 list->crnt에 ptr 대입 후 찾은 노드에 대한 포인터인 ptr 반환
l9 : ptr에 ptr->next를 대입하여 ptr이 다음 노드를 가리키도록 함. 이후 계속 스캔
l11 : 검색 실패 시 NULL값 반환

머리에 노드를 삽입하는 InsertFront 함수

연결 리스트의 머리에 노드를 삽입하는 함수

void InsertFront(List *list, const Member *x)
{
	Node *ptr = list->head;
	list->head = list->crnt = AllocNode();
	SetNode(list->head, x, ptr);
}


처리 과정
1. 삽입 전의 머리 노드 A에 대한 포인터를 ptr에 대입
2. 삽입할 노드 G를 AllocNode 함수로 만들고, 만든 노드 G를 가리키도록 list->head를 업데이트. list->crnt도 새로 만든 노드를 가리키도록 업데이트
3. SetNode 함수를 호출하여 값을 설정. 삽입한 다음 머리 노드의 다음을 가리키는 포인터의 값을 ptr로 업데이트

꼬리에 노드를 삽입하는 InsertRear 함수

연결 리스트 꼬리에 노드를 삽입하는 함수

  • 리스트가 비어 있는 경우, 머리에 노드를 삽입하는 처리와 같음.
    InsertFront 함수로 처리
  • 리스트가 비어 있지 않은 경우, 리스트 꼬리에 노드 G를 삽입
void InsertRear(List *list, const Member *x)
{
	if (list->head == NULL)			/* 비어있는 경우 */
		InsertFront(list, x);		/* 머리에 삽입 */
	else {
    		/*[4]*/
		Node *ptr = list->head;
		while (ptr->next != NULL)
			ptr = ptr->next;
          
         	 /*[5]*/
		ptr->next = list->crnt = AllocNode();
		SetNode(ptr->next, x, NULL);
	}
}


[4] 꼬리 노드 찾기. 머리 노드를 가리키도록 초기화한 ptr이 가리키는 노드를 계속해서 다음 노드를 가리키도록 업데이트하는 과정을 반복함으로써 노드를 처음부터 차례로 스캔.
ptr->next가 가리키는 노드가 NULL이 되면 while문 종료, 이때 ptr이 가리키는 노드는 꼬리 노드 F
[5] 삽입할 노드 G를 AllocNode 함수로 만들고, 삽입하기 전의 꼬리 노드 F의 다음 포인터 ptr->next가 가리키는 노드에 삽입한 다음의 꼬리 노드 G 대입. SetNode 함수를 호출해 앞에서 만든 노드 G의 값을 설정, 이때 노드 G의 다음 노드에 NULL 대입

머리 노드를 삭제하는 RemoveFront 함수

머리 노드를 삭제하는 함수

void RemoveFront(List *list)
{
	if (list->head != NULL) {
		Node *ptr = list->head->next;	/* 두 번째 노드에 대한 포인터 */
		free(list->head);		/* 머리 노드를 해제 */
		list->head = list->crnt = ptr;	/* 새로운 머리 노드 */
	}
}

리스트가 비어 있지 않은 경우(list->head != NULL)에만 머리 노드 삭제

머리 노드에 대한 포인터 list->head에 두 번째 노드 B에 대한 포인터 list->head->next를 대입하여 list->head가 가리키는 노드를 B로 업데이트, 삭제하기 전의 머리 노드 A의 메모리 영역 해제. 이때 선택한 노드 crnt가 가리키는 노드도 B로 업데이트

리스트에 노드가 1개만 있는 경우, 삭제하기 전의 머리 노드는 꼬리 노드이므로 다음 노드를 가리키는 list->head->next의 값은 NULL

꼬리 노드를 삭제하는 RemoveRear 함수

꼬리 노드를 삭제하는 함수

void RemoveRear(List *list)
{
	if (list->head != NULL) {
		if ((list->head)->next == NULL)	/* 노드가 하나만 있는 경우 */
			RemoveFront(list);	/* 머리 노드를 삭제 */
		else {
        		/*[1]*/
			Node *ptr = list->head;
			Node *pre = NULL;
			while (ptr->next != NULL) {
				pre = ptr;
				ptr = ptr->next;
			}
			/*[2]*/
			pre->next = NULL;	/* pre는 꼬리 노드부터 두 번째 노드 */
			free(ptr);		/* ptr은 꼬리 노드 */
			list->crnt = pre;
		}
	}
}

리스트에 있는 노드 개수에 따라 해당하는 작업을 수행

  • 리스트에 노드가 1개만 있는 경우 : 머리 노드를 삭제하는 것과 같음
    RemoveFront 함수로 처리

  • 리스트에 노드가 2개 이상 있는 경우

    [1] '꼬리 노드'와 '꼬리 노드로부터 두 번째 노드' 찾기
    InsertRear 함수와 비슷하나 현재 스캔하고 있는 노드이 '앞에 있는 노드'를 가리키는 변수 pre 추가
    [2] 꼬리 노드부터 두 번째 노드 E의 다음을 가리키는 포인터에 NULL을 대입하고 꼬리 노드 F의 메모리 영역 해제, 이때 선택한 노드 crnt가 가리키는 노드는 삭제한 다음의 꼬리 노드 pre가 됨

    while문이 종료되면 pre는 노드 E를, ptr은 노드 F를 가리킴

선택한 노드를 삭제하는 RemoveCurrent 함수

현재 선택한 노드(list->crnt)가 가리키는 노드를 삭제하는 함수

void RemoveCurrent(List *list)
{
	if (list->head != NULL) {
		if (list->crnt == list->head)	/* 머리 노드를 선택한 상태라면 */
			RemoveFront(list);	/* 머리 노드를 삭제 */
		else {
        		/*[1]*/
			Node *ptr = list->head;
			while (ptr->next != list->crnt)
				ptr = ptr->next;
                	/*[2]*/
			ptr->next = list->crnt->next;
			free(list->crnt);
			list->crnt = ptr;
		}
	}
}

선택한 노드가 머리 노드인지 아닌지에 따라 다음의 작업 수행

  • crnt가 머리 노드인 경우 : 머리 노드 삭제. RemoveFront 함수로 처리
  • crnt가 머리 노드가 아닌 경우

    [1] 선택한 노드의 앞 노드 찾기. while문은 머리 노드부터 스캔 시작. 선택한 노드 ptr의다음 노드를 가리키는 포인터 ptr->next가 list->crnt와 같을 때까지 반복. while문이 종료되고 난 다음 ptr이 가리키는 노드는 삭제하기 위해 선택한 노드 D의 앞쪽 노드인 노드 C
    [2] 삭제하기 위해 선택한 노드 D의 다음 노드 포인터 list->crnt->next를 노드 C의 다음 노드 포인터 ptr->next에 대입. 노드 C의 다음 노드 포인터가 가리키는 노드가 노드 E로 업데이트 됨. 이후 노드 D의 메모리 영역 해제. 이때 선택한 노드 crnt가 가리키는 노드는 삭제한 노드의 앞 노드(노드 C)로 업데이트 됨

모든 노드를 삭제하는 Clear 함수

연결 리스트의 모든 노드를 삭제하는 함수

void Clear(List *list)
{
	while (list->head != NULL)		/* 텅 빌 때까지 */
		RemoveFront(list);		/* 머리 노드를 삭제 */
	list->crnt = NULL;
}

연결 리스트가 완전히 텅 빈 상태(head == NULL)가 될 때까지 머리 요소의 삭제 작업 반복, 이때 모든 노드를 삭제하면 리스트가 완전히 빈 상태가 되므로 crnt의 값도 NULL로 업데이트됨

선택한 노드의 데이터를 출력하는 PrintCurrent / PrintLnCurrent 함수

선택한 노드의 데이터를 출력하는 함수

/*--- 선택한 노드의 데이터를 출력 ---*/
void PrintCurrent(const List *list)
{
	if (list->crnt == NULL)
		printf("선택한 노드가 없습니다.");
	else
		PrintMember(&list->crnt->data);
}
/*--- 선택한 노드의 데이터를 출력(줄바꿈 문자 포함) ---*/
void PrintLnCurrent(const List *list)
{
	PrintCurrent(list);
	putchar('\n');
}

선택한 노드가 없는 경우(list->crnt == NULL) '선택한 노드가 없습니다.' 출력

리스트의 모든 노드를 출력하는 Print 함수

리스트의 모든 노드를 순서대로 출력하는 함수

void Print(const List *list)
{
	if (list->head == NULL)
		puts("노드가 없습니다.");
	else {
		Node *ptr = list->head;
		puts("【 모두 보기 】");
		while (ptr != NULL) {
			PrintLnMember(&ptr->data);
			ptr = ptr->next;		/* 뒤쪽 노드 선택 */
		}
	}
}

머리 노드부터 꼬리 노드까지 포인터 ptr이 가리키는 데이터 출력

연결 리스트를 종료하는 Terminate 함수

void Terminate(List *list)
{
	Clear(list);		/* 모든 노드를 삭제 */
}

모든 노드를 삭제하는 Clear 함수 호출

🔴보충수업_자기 참조 구조체와 typedef 선언

/*---노드---*/
typedef struct __node {
	Member data;		/* 데이터 */
    	struct __node *next;	/* 다음 노드를 가리키는 포인터 */
} Node;

연결 리스트를 사용한 프로그램

/* 선형 리스트를 사용하는 프로그램 */
#include <stdio.h>
#include "Member.h"    
#include "LinkedList.h"

/*--- 메뉴 ---*/
typedef enum {
	TERMINATE, INS_FRONT, INS_REAR, RMV_FRONT, RMV_REAR, PRINT_CRNT,
	RMV_CRNT, SRCH_NO, SRCH_NAME, PRINT_ALL, CLEAR
} Menu;

/*--- 메뉴 선택 ---*/
Menu SelectMenu(void)
{
	int i, ch;
	char *mstring[] = {
		"머리에 노드를 삽입",   "꼬리에 노드를 삽입",   "머리 노드를 삭제",
		"꼬리 노드를 삭제",     "선택한 노드를 출력",   "선택한 노드를 삭제",
		"번호로 검색",          "이름으로 검색",        "모든 노드를 출력",
		"모든 노드를 삭제",
	};
	
	do {
		for (i = TERMINATE; i < CLEAR; i++) {
			printf("(%2d) %-18.18s ", i + 1, mstring[i]);
			if ((i % 3) == 2)
				putchar('\n');
		}
		printf("( 0) 종료 : ");
		scanf("%d", &ch);
	} while (ch < TERMINATE || ch > CLEAR);
	
	return (Menu)ch;
}

/*--- 메인 ---*/
int main(void)
{
	Menu menu;
	List list;
	
	Initialize(&list);                 /* 선형 리스트를 초기화 */
	do {
		Member x;
		switch (menu = SelectMenu()) {
		/* 머리에 노드를 삽입 */
		case INS_FRONT:
			x = ScanMember("머리에 삽입", MEMBER_NO | MEMBER_NAME);
			InsertFront(&list, &x);
			break;
		
		/* 꼬리에 노드를 삽입 */
		case INS_REAR:
			x = ScanMember("꼬리에 삽입", MEMBER_NO | MEMBER_NAME);
			InsertRear(&list, &x);
			break;

		
		/* 머리 노드를 삭제 */
		case RMV_FRONT:
			RemoveFront(&list);
			break;

		/* 꼬리 노드를 삭제 */
		case RMV_REAR:
			RemoveRear(&list);
			break;

		/* 선택한 노드의 데이터를 출력*/
		case PRINT_CRNT:
			PrintLnCurrent(&list);
			break;

		/* 선택한 노드를 삭제 */
		case RMV_CRNT:
			RemoveCurrent(&list);
			break;

		/* 번호로 검색 */
		case SRCH_NO:
			x = ScanMember("검색", MEMBER_NO);
			if (search(&list, &x, MemberNoCmp) != NULL)
				PrintLnCurrent(&list);
			else
				puts("그 번호의 데이터가 없습니다.");
			break;

		/* 이름으로 검색 */
		case SRCH_NAME:
			x = ScanMember("검색", MEMBER_NAME);
			if (search(&list, &x, MemberNameCmp) != NULL)
				PrintLnCurrent(&list);
			else
				puts("그 이름의 데이터가 없습니다.");
			break;
		
		/* 모든 노드의 데이터를 출력 */
		case PRINT_ALL:
			Print(&list);
			break;

		/* 모든 노드를 삭제 */
		case CLEAR:
			Clear(&list);
			break;
		}
	} while (menu != TERMINATE);
	
	Terminate(&list);               /* 선형 리스트의 뒤처리 */
	
	return 0;
}
profile
란지
콤퓨타공학과
이전 포스트

[Do it 알고리즘] 05. 재귀 알고리즘

다음 포스트

[Do it 알고리즘] 09. 리스트(2)

0개의 댓글