4. 연결 리스트 2

4-1. 연결 리스트의 개념적인 이해

 

* 연결 리스트의 이해

연결 리스트는 노드들을 연결한 구조로 구성된다. (메모리에서 인접할 필요가 없다.)

노드는 데이터와 노드를 연결하는 포인터로 구성된다.

연결 리스트는 필요할 때마다 노드를 하나씩 동적 할당하여 이들을 연결한다.

연결 리스트

* 간단한 연결 리스트

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

typedef struct _node {
	int data; // 데이터를 담을 공간
	struct _node* next; // 연결의 도구
}Node;

int main()
{
	Node* head = NULL; // 리스트의 머리를 가리키는 포인터 변수
	Node* tail = NULL; // 리스트의 꼬리를 가리키는 포인터 변수
	Node* cur = NULL; // 저장된 데이터의 조회에 사용되는 포인터 변수
	Node* newNode = NULL;
	int readData;

	while (1) {
		printf("자연수 입력: ");
		scanf("%d", &readData);
		if (readData < 1)
			break;

		// 데이터 삽입
		newNode = (Node*)malloc(sizeof(Node)); // 노드의 생성
		newNode->data = readData; // 노드에 데이터 저장
		newNode->next = NULL; // 노드의 next를 NULL로 초기화

		if (head == NULL) // 추가한 노드가 첫 번째 노드라면
			head = newNode; // 첫 번째 노드를 head가 가리키게 함
		else // 두 번째 이후 노드라면 
			tail->next = newNode; // 마지막 노드의 다음에 추가
		tail = newNode; // 노드의 끝을 tail이 가리키게 함
	}
	printf("\n");

	printf("입력 받은 데이터의 전체 출력\n");
	if (head == NULL)
		printf("저장된 데이터가 없습니다.\n");
	else {
		// 데이터 조회
		cur = head;  // cur이 리스트의 첫 번째 노드를 가리킨다.
		printf("%d ", cur->data); // 첫 번째 데이터 출력
		while (cur->next != NULL) { // 연결된 노드가 존재한다면
			cur = cur->next;  // cur이 다음 노드를 가리키게 한다.
			printf("%d ", cur->data); // cur이 가리키는 노드를 출력한다.
		}
		printf("\n\n");

		if (head == NULL)
			return 0;
		
		// 데이터 삭제
		Node* delNode = head;
		// 삭제될 노드의 다음 노드의 주소 값을 저장하지 않으면 삭제한 후 다음 노드에 접근할 수 없다.
		Node* delNextNode = head->next; 

		printf("%d을(를) 삭제합니다.\n", delNode->data);
		free(delNode); // 첫 번째 노드 삭제

		while (delNextNode != NULL) { // 두 번째 이후 노드 삭제를 위한 반복문
			delNode = delNextNode;
			delNextNode = delNextNode->next;
			printf("%d을(를) 삭제합니다.\n", delNode->data);
			free(delNode);
		}
		
		return 0;
	}
}

 

4-2. 단순 연결 리스트의 구현

 

* 노드를 어디에 추가할 것인가?

단순 연결 리스트를 구현하기 위해 새 노드를 추가할 때, 리스트의 머리와 꼬리 중 어디에 추가를 할 것인지 결정해야 한다.

두 가지 방법 모두 장점과 단점이 있다.

• 머리에 추가할 경우
  • 장점: 포인터 변수 tail이 불필요하다.
  • 단점: 저장된 순서를 유지하지 않는다.
• 꼬리에 추가할 경우
  • 장점: 저장된 순서가 유지된다.
  • 단점: 포인터 변수 tail이 필요하다.

포인터 변수 tail을 유지하기 위해서 넣어야 할 부가적인 코드가 번거롭게 느껴질 수 있고 리스트 자료구조는 저장된 순서를 유지해야 하는 자료구조가 아니므로 많은 수의 자료구조 서적에서 노드를 머리에 추가하는 방식으로 연결 리스트를 구현한다. 

 

* 더미 노드 기반의 단순 연결 리스트

위의 간단한 연결 리스트에서는 노드를 추가, 삭제 그리고 조회하는 방법에 있어서 첫 번째 노드와 두 번째 이후의 노드에 차이가 있다. 리스트의 맨 앞에 더미 노드가 있는 단순 연결 리스트는 처음 추가되는 노드가 구조상 두 번째 노드가 되므로 노드의 추가, 삭제 및 조회의 과정을 일관된 형태로 구성할 수 있다.

더미 연결 리스트

 

* 더미 노드 기반의 단순 연결 리스트의 구현

#define TRUE 1
#define FALSE 0

typedef int LData;

typedef struct _node {
	LData data;
	struct _node* next;
}Node;

// 연결 리스트를 의미하는 구조체
typedef struct _linkedList {
	Node* head; // 더미 노드를 가리키는 노드 포인터
	Node* cur; // 참조 및 삭제를 돕는 노드 포인터
	Node* before; // 삭제를 돕는 노드 포인터
	int numOfData; // 저장된 데이터의 수
}LinkedList;

typedef LinkedList List;

void ListInit(List* plist) {
	plist->head = (Node*)malloc(sizeof(Node)); // 더미 노드의 생성
	plist->head->next = NULL;
	plist->numOfData = 0;
}

void LInsert(List* plist, LData data) {
	Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
	newNode->data = data; // 새 노드에 데이터 저장
	newNode->next = plist->head->next; // 새 노드가 다른 노드를 가리키게 함
	plist->head->next = newNode; // 더미 노드가 새 노드를 가리키게 함
	(plist->numOfData)++; // 저장된 노드의 수를 하나 증가시킴
}

int LFirst(List* plist, LData* pdata) {
	if (plist->head->next == NULL) // 더미 노드가 NULL을 가리키면
		return FALSE; // 반환할 데이터 없음
	plist->before = plist->head; // before은 더미 노드를 가리키게 함
	plist->cur = plist->head->next; // cur은 첫 번째 노드를 가리키게 함
	*pdata = plist->cur->data; // 첫 번째 노드의 데이터를 전달
	return TRUE; // 데이터 반환 성공
}

int LNext(List* plist, LData* pdata) {
	if (plist->cur->next == NULL) // cur이 NULL을 가리키면
		return FALSE; // 반환할 데이터가 없음
	plist->before = plist->cur; // cur이 가리키던 것을 before가 가리킴
	plist->cur = plist->cur->next; // cur이 다음 노드를 가리킴
	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 전달
	return TRUE; // 데이터 반환 성공
}

LData LRemove(List* plist) {
	Node* rpos = plist->cur; // 삭제할 노드의 주소값을 rpos에 저장
	LData rdata = plist->cur->data; // 삭제할 노드의 데이터를 rdata에 저장
	plist->before->next = plist->cur->next; // 삭제할 노드를 리스트에서 제거
	plist->cur = plist->before; // cur이 가리키는 위치 재조정
	free(rpos); // 리스트에서 삭제한 노드 소멸 
	(plist->numOfData)--; // 저장된 데이터 수 감소
	return rdata; // 삭제된 노드의 데이터 반환
}

int LCount(List* plist) {
	return plist->numOfData;
}