[자료구조] 5. 리스트(List)2 - 단순 연결 리스트 구현

단순 열결 리스트란?

 

5.1 단순 연결 리스트 구현 

    1) 노드의 정의 

    2) 단순 연결 리스트 생성 

    3) 노드의 생성

    4) 노드의 연결

 

5.2 단순 연결 리스트 연산 구현

    1) 삽입 연산 

    2) 삭제 연산

    3) 방문 연산

    4) 기타 연산

    5) 연결 리스트 연산 예시

 

단순 연결 리스트 : 하나의 방향으로만 연결 되어 있는 연결 리스트.

 

단순 연결 리스트에서는 노드들이 하나의 링크 필드를 가지며 마지막 링크 필드의 값은 NULL이 된다. 

 

---

5.1 단순 연결 리스트 구현

 

1) 노드의 정의

 

노드는 자기 참조 구조체를 이용하여 정의된다.

* 자기 참조 구조체 : 자기 자신을 참조하는 포인터를 포함하는 구조체 

 

// [노드의 정의]
typedef int element;

typedef struct ListNode {      //노드 타입을 정의
	element data;   //데이터 필드
	struct ListNode* link;    //링크 필드
}ListNode;

 

노드 타입 구조체 안에는 데이터 필드와 링크 필드가 존재한다.

• 데이터 필드 - element 타입의 데이터를 저장.
• 링크 필드 - ListNode를 가리키는 포인터를 저장. 다음 노드의 주소가 저장된다.

 

 

2) 단순 연결 리스트 생성 - 공백 리스트 생성

 

위의 노드 구조체 정의는 노드의 구조를 정의하였을뿐 아직 노드가 생성된 것은 아니다. 

 

단순 연결 리스트는 헤드 포인터만 있으면 모든 노드를 찾을 수 있다. 따라서 헤드 포인터를 정의하면 하나의 단순 연결 리스트가 생성되었다고 볼 수 있다. 헤드 포인터는 첫 번째 노드를 가리킨다.

//[공백 리스트의 생성] - 헤드 포인터 정의
ListNode *head = NULL;     //아직 생성된 노드가 없으므로 head의 값은 NULL이 된다.

 

* 연결 리스트가 공백 상태인지 검사하는 방법 - 헤드 포인터가 NULL인지를 검사한다.

 

 

3) 노드의 생성

 

연결 리스트에서는 malloc() 함수를 이용하여 노드의 크기만큼  동적 메모리를 할당 받는다. 이 동적 메모리가 하나의 노드가 된다. 

//[노드의 생성] 
ListNode *p;   //구조체 포인터 선언
p = (ListNode*)malloc(sizeof(ListNode));  //하나의 노드 생성
p->data = 10;      //데이터 필드에 데이터 저장
p->link = NULL;     //링크 필드에 포인터 저장

 

 

4) 노드의 연결

 

앞에 오는 노드의 링크 필드에 다음에 올 노드의 포인터를 저장한다.

 

각각 포인터 p1, p2가 가리키는 두 개의 노드가 있다고 가정하자. 

p1->link = p2;

 

---

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

 

단순 연결 리스트에서 함수를 작성하여 수행할 연산들은 다음과 같다.

• 리스트의 시작 부분에 항목을 삽입하는 연산  →  insertFirst()
• 리스트의 중간 부분에 항목을 삽입하는 연산  →  insert()
• 리스트의 첫 번째 항목을 삭제하는 연산  →  deleteFirst()
• 리스트의 중간 항목을 삭제하는 연산  →  delete()
• 리스트를 방문하여 모든 항목을 출력하는 연산  →  printList()
• 리스트를 방문하여 특정한 값을 탐색하는 연산 → searchList()
• 두 개의 리스트를 하나로 합치는 연산  →  concatList()
• 리스트를 역순으로 만드는 연산  →  reverse()

 

[단순 연결 리스트 정의]

 

단순 연결 리스트는 원칙적으로 헤드 포인터만 있으면 된다. → 헤드 포인터 값만 알면 해당 연결 리스트의 모든 노드에 접근이 가능하다.

ListNode *head;

 

 

1) 삽입 연산

 

① insertFirst() - 리스트의 첫 부분에 새로운 노드 추가하는 함수

 

[알고리즘]

• 동적 메모리 할당을 통해 새로운 노드 p를 생성한다.
• p->data에 value(데이터)를 저장한다.
• p->link를 기존의 head 값으로 변경한다.
• head를 p값으로 변경한다.
• 변경된 헤드 포인터를 반환한다.

[코드 구현]

// 'head'는 헤드 포인터
ListNode* insetFirst(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;
	head = p;
	return head;
}

 

 

② insert() - 리스트의 중간 부분에 새로운 노드 추가하는 함수 

 

[알고리즘]

• 동적 메모리 할당을 통해 새로운 노드 p를 생성한다.
• p->data에 value(데이터)를 저장한다.
• p의 링크 필드가 p 다음에 올 노드를 가리키게 변경한다.
• p의 앞에 오는 노드의 링크 필드가 p를 가리키도록 변경한다.
• 변경된 헤드 포인터를 반환한다.

[코드 구현]

// 'pre'는 추가할 노드의 선행 노드를 가리키는 포인터
ListNode* insertFirst(ListNode* head, ListNode* pre, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = pre->link;
	pre->link = p;
	return head;
}

 

 

2) 삭제 연산 

 

① deleteFirst() : 리스트의 첫 번째 노드를 삭제하는 함수

 

[알고리즘]

• 헤드 포인터의 값을 removed에 복사한다.
• 헤드 포인터의 값을 head->link로 변경한다. 
• removed가 가리키는 동적 메모리를 운영체에 반납한다.
• 변경 헤드 포인터를 반환한다. 

[코드 구현]

ListNode* deletrFirst(ListNode* head) {
	ListNode *removed;
	if (head == NULL) return NULL;  //연결 리스트가 공백 상태인지 검사
	// 연결 리스트가 공백 상태가 아닐 경우
	removed = head; 
	head = removed->link;
	free(removed);      //동적 메모리 반납
	return head;
}

 

 

② delete() : 리스트의 중간 노드를 삭제하는 함수

 

[알고리즘]

• 삭제할 노드를 찾는다.
• 삭제할 노드의 선행 노드 링크 필드가 뒤에 오는 노드를 가리키게 변경한다.
• 삭제할 노드의 동적 메모리를 운영체제에 반납한다.
• 변경된 헤드 포인터를 반환한다.

[코드 구현]

// 'pre'는 삭제할 노드의 선행 노드를 가리키는 포인터
ListNode* delete(ListNode* head, ListNode* pre) {
	ListNode* removed;
	removed = pre->link;
	pre->link = removed->link;
	free(removed);
	return head;
}

 

 

3) 방문 연산

 

① printList() : 모든 노드를 방문하면서 노드의 데이터를 화면에 출력하는 함수

 

[알고리즘]

• 연결리스트의 헤드 포인터가 가리키는 노드부터 (첫 노드) 노드의 링크값이 NULL(마지막 노드)이 아닐 때까지 계속 링크를 따라가면서 노드를 방문한다.
• 링크값이 NULL이면 반복을 중단한다. 

 

[코드 구현]

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

 

 

② searchList() : 특정한 값을 탐색하는 함수

 

[코드 구현]

ListNode* searchList(ListNode* head, element x) {
	ListNode* p = head;

	while (p != NULL) {
		if (p->data == x) return p;  //탐색 값을 가지고 있는 노드의 주소를 반환
		p = p->link;     //링크를 따라 다음 노드로 이동
	}
	return NULL;   //탐색 실패
}

 

4) 기타 연산 

 

① concatList() : 두 개의 리스트를 하나로 합치는 함수

 

[알고리즘]

• 첫 번째 리스트의 헤드 포인터를 검사하여 공백 상태이면 두 번째 리스트의 헤드 포인터를 반환한다.
• 두 번째 리스트의 헤드 포인터를 검사하여 공백 상태이면 첫 번째 리스트의 헤드 포인터를 반환한다.
• 두 리스트 모두 공백 상태가 아닐 경우, 첫 번째 리스트의 링크들을 따라 마지막 노드로 이동한다. 
• 마지막 노드의 링크가 두 번째 리스트의 첫 번째 노드를 가리키도록 변경한다. 
• 첫번째 리스트의 헤드 포인터를 반환한다. 

[코드 구현]

ListNode* concatList(ListNode* head1, ListNode* head2) {
	if (head1 == NULL) return head2;
	else if (head2 == NULL) return head1;
	else{
		ListNode *p;
		p = head1;
		while (p->link != NULL)   //마지막 노드를 가리킬 때까지 포인터 P의 값을 변경하며 이동한다.
			p = p->link;  
		p->link = head2;    //마지막 노드의 링크 필드를 NULL에서 head2로 변경
		return head1;
	}
}

 

② reverse() : 리스트를 역순으로 만드는 연산

 

세 개의 포인터 c,n,r을 사용하여 연결 리스틀를 순회하면서 링크의 방향을 역순으로 바꾼다. 

세 개의 포인터들은 각각 c는 역순으로 만들 리스트, n는 현재 역순으로 만들 노드, r은 이미 역순으로 변경된 리스트를 가리킨다. r은 n을, n은 c를 차례대로 따라간다.

순회를 마친 후 최종적으로 n이 원본 리스트의 마지막 노드를 가리키므로  n의 값이 역순으로 만들어진 리스트의 헤드 포인터 값이 된다. ( * r은 마지막 노드 바로 전의 노드를 가리키고, c는 아무것도 가리키지 않는 상태로 순회 종료됨 )

 

[코드 구현]

ListNode* reverse(ListNode* head) {
	ListNode *c, *n, *r;  // 순회 포인터

	c = head;   //c는 역순으로 만들 리스트
	n = NULL;   //n은 역순으로 만들 노드

	while (c != NULL) {  //역순으로 만들 리스트가 더이상 존재하지 않을 때까지 순회 반복 
		r = n;               //r은 이미 역순으로 된 리스트, n의 링크 방향을 반대로 바꾸기 전에 미리 연결할 뒤의 노드를 알아야 한다.
		n = c;               //현재 역순으로 바꿀 노드를 가리킨다.
                c = c->link;         //다음 작업 수행을 위해 링크를 따라 이동
		n->link = r;         //노드 n의 링크 방향을 반대로 바꾼다.
	}

	return n;  
}

 

 

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* insetFirst(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;
	head = p;
	return head;
}

ListNode* deletrFirst(ListNode* head) {
	ListNode *removed;
	if (head == NULL) return NULL;  //연결 리스트가 공백 상태인지 검사
	// 연결 리스트가 공백 상태가 아닐 경우
	removed = head; 
	head = removed->link;
	free(removed);      //동적 메모리 반납
	return head;
}

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

//=========================================================================================
int main(void) {
	ListNode* head = NULL;   //하나의 단순 연결 리스트 생성

	// 반복적으로 리스트의 첫 부분에 5개의 노드 추가
	for (int i = 0; i < 5; i++) {
		head = insertFirst(head, i);    //삽입 연산 함수가 반환하는 헤드 포인터를 head에 대입
		printList(head);     //연산 후 연결 리스트의 현재 상태를 화면에 출력
	}

	// 반복적으로 리스트의 첫 노드를 5번 삭제
	for (int i = 0; i < 5; i++) {
		head = deleteFirst(head);
		printList(head);
	}
}

 

 

② 단어들을 저장하는 연결 리스트 

#define _CRT_SECURE_NO_WARNINGS

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

//[리스트 항목 타입 정의]
typedef struct {
	char name[100];
} element;

//[노드 타입 정의]
typedef struct ListNode{
	element data;
	struct ListNode* link;
} ListNode;

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

//[연산 함수]
ListNode* insertFirst(ListNode* head, element value) {
	ListNode* p = (ListNode*)malloc(sizeof(ListNode));
	p->data = value;
	p->link = head;
	head = p;

	return head;
}

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


// ====================================================================================================
int main(void) {
	ListNode* head = NULL;  //연결 리스트 생성
	element data;

	strcpy(data.name, "APPLE");
	head = insertFirst(head, data);
	printList(head);

	strcpy(data.name, "KIWI");
	head = insertFirst(head, data);
	printList(head);

	strcpy(data.name, "BANANA");
	head = insertFirst(head, data);
	printList(head);

	return 0;
}