연결리스트, 이들의 종류와 간단한 단일 연결리스트 구현.

 

* 앞서 리스트와 배열에 대해 알아보았는데

 

보통 컴퓨터 관련 학과에 진학하고 2학년 1학기쯤 되면 자료구조를 배우게 된다.

 

이 자료구조 수업시간에 가장 초기에 하는 구현은 연결리스트 구현이다.

 

연결리스트의 종류에는 크게 세 가지 정도가 있다.

 

단일 연결리스트, 원형 연결리스트, 양방향 연결리스트

 

이렇게 있다. 또 Head와 Tail의 유무 그리고 삽입 위치가 어디에 있냐에 따라 또 구현이 어느정도 달라진다.

 

연결리스트에서 새로운 노드를 추가할 때 리스트의 머리(head)부분과 꼬리(tail) 중 어디에 저장하여

 

노드를 연결하냐에 따라 구현이 달라진다는데 각 장단점을 서로 반대로 가지고 있다.

 

	장점	단점
머리	포인터 변수 Tail이 불필요하다	저장된 순서가 유지되지 않는다.
꼬리	저장된 순서가 유지된다	포인터 변수 Tail이 필요하다

 

이렇게 된다.

 

둘 중 누가 더 좋냐 안좋냐는 케이스 바이 케이스라고 할 수 있다.

 

[원형 연결리스트]

 

원형 리스트에 대해 잠깐 이야기를 하자면, 

 

보통 단일 리스트의 끝 부분은 NULL이 된다. 즉 아무것도 가리키지 않는다.

 

그러나 원형 연결 리스트에서는 이 끝 부분의 노드의 포인터는 head부분을 가리키게 된다.

 

그래서 노드를 순환하여 출력할 수 있게 된다.

 

이러한 특징으로 인하여 원형 연결리스트는 보통 head와 tail을 구분한다.

 

 

[양방향 연결리스트]

 

단일 리스트, 원형 리스트들의 포인터는 다음 노드를 가리키는 next밖에 존재하지 않는다.

 

그러나 양방향 연결 리스트는 next 포인터 외에 이전 노드를 가리키는 prev도 존재한다.

 

양방향 연결 리스트는 head와 tail의 유무, 그리고 원형 연결 리스트 기반 등 여러 종류에 따라 구현이 조금씩 달라진다.

 

[단방향 연결리스트]

 

단방향 연결리스트는 말 그대로 한가지의 방향으로만 연결되어 있는 리스트 자료구조이다.

 

단방향 연결리스트에도 여려 종류가 있는데 head와 tail모두가 존재하는 리스트,

 

그리고 head와 dummy Node가 존재하는 리스트 크게 이 두가지가 있다.

 

여기서 더미데이터는 head가 가리키는 값인데 아무런 데이터도 존재하지 않는다.

 

이 들의 차이점은 위의 표에 존재한다. 그렇지만 난 친절하니까 또 복붙을 해줄거다.

 

	장점	단점
머리	포인터 변수 Tail이 불필요하다	저장된 순서가 유지되지 않는다.
꼬리	저장된 순서가 유지된다	포인터 변수 Tail이 필요하다

 

이렇다. 구현은 어떻게 될까?

 

구현은, 윤성우의 열혈 자료구조를 참고하였다.

 

[Tail이 존재하는 단일 연결리스트, 책에서는 동적 메모리 할당을 설명하기 위해 짜여진 코드이다.]

#include "pch.h"
#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_s("%d", &readdata);					// 연결의 도구

		if (readdata < 1) {
			break;
		}

		// 노드의 추가 과정
		newNode = (Node*)malloc(sizeof(Node));	// 노드에 메모리 할당
		newNode->data = readdata;				// 새로운 노드에 입력한 데이터 집어넣기
		newNode->next = NULL;					// 이 노드의 다음 포인트는 Null을 가리킴

		if (head == NULL) {
			head = newNode;
		}
		else {
			tail->next = newNode;
		}

		tail = newNode;							// 노드의 끝을 Tail이 가리키게 함.
	}
	printf("\n");

	// 입력 받은 데이터의 출력 과정
	printf("입력 받은 데이터의 전체 출력! \n");
	if (head == NULL) {
		printf("저장된 자연수가 존재하지 않습니다. \n");
	}
	else {
		cur = head;
		printf("%d ", cur->data);

		while (cur->next != NULL) {
			cur = cur->next;
			printf("%d", cur->data);
		}
	}
	printf("\n\n");

	// 메모리 해제
	if (head == NULL) {
		return 0;
	}
	else {
		Node *delNode = head;
		Node *delnextNode = head->next;

		printf("%d를 삭제합니다. \n", head->data);
		free(delNode);

		while (delnextNode != NULL) {
			delNode = delnextNode;
			delnextNode = delnextNode->next;

			printf("%d를 삭제합니다. \n", delNode->data);
			free(delNode);
		}
	}

	return 0;
}

 

 

[tail이 존재하지 않고 head가 dummy Data를 가리키는 코드]

 

[헤더파일]

#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__

#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;
	int (*comp)(Ldata d1, Ldata d2);
} LinkedList;

typedef LinkedList List;

void ListInit(List *plist);

void LInsert(List *plist, Ldata data);

void FInsert(List *plist, Ldata data);

void SInsert(List *plist, Ldata data);

int LFirst(List *plist, Ldata *pdata);

int LNext(List *plist, Ldata *pdata);

Ldata LRemove(List *plist);

int LCount(List *plist);

void SetSortRule(List *plist, int(*comp)(Ldata d1, Ldata d2));

#endif 

 

 

[함수 구현 및 실행 파일]

 

#include "pch.h"
#include "DLinkedList.h"
#include <stdlib.h>
#include <stdio.h>

void ListInit(List *plist) {				// 리스트 초기화
	// Head에 메모리 할당(데이터는 들어있지 않는 더미 데이터)
	plist->head = (Node*)malloc(sizeof(Node));
	// 더미데이터(해드)의 다음 노드(첫 데이터 노드) Null 할당
	plist->head->next = NULL;
	plist->comp = 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) {					// 첫 노드로 돌아가기
	
	// 더미 노드가 NULL을 가리킨다면
	if (plist->head->next == NULL) {
		// 반환할 것이 없다.
		return FALSE;
	}

	// Before는 더미 노드를 가리키게 한다.
	plist->before = plist->head;
	// cur는 첫 번째 노드(더미 노드 다음)을 가리키게 한다.
	plist->cur = plist->head->next;

	// 첫 번째 노드의 데이터를 전달하는 매개포인터 pdata로 해당 데이터가 넘겨진다.
	*pdata = plist->cur->data;
	// 반환 성공
	return TRUE;
}

int LNext(List *plist, Ldata *pdata) {		// 다음 노드 받아오기

	// 현재노드의 다음 노드가 NULL을 가리킨다면
	if (plist->cur->next == NULL) {
		// 반환할 것이 없음
		return FALSE;
	}

	// 이전 커서는 현재 노드를 가리키고
	plist->before = plist->cur;
	// 현재 커서(반환하고자 하는 노드 위치)는 다음 노드를 가리킨다.
	plist->cur = plist->cur->next;

	// 반환하고자 하는 데이터를 가리키는 매개 포인터 pdata
	*pdata = plist->cur->data;

	// 반환 성공
	return TRUE;
}

Ldata LRemove(List *plist) {				// 해당 노드 삭제
	
	// 현재 노드의 위치를 가져오는 rpos포인터
	Node *rpos = plist->cur;
	// 현재 노드의 데이터를 가져오는 rdata
	Ldata rdata = rpos->data;

	// before의 다음은, 현재 위치의 다음을 가리킨다(한 자리씩 앞당긴다)
	plist->before->next = plist->cur->next;
	// Cur는 before을 가리킨다(한 자리씩 앞당겨진다)
	plist->cur = plist->before;

	// 삭제되는 데이터 메모리 반환
	free(rpos);
	// numofdata 1 줄이기
	(plist->numofdata)--;
	
	// 반환 성공하면 해당 데이터를 반환
	return rdata;
}

int LCount(List *plist) {					// 현재 데이터 수 반환
	return plist->numofdata;
}

#pragma region 일반 더미 노드를 가지고 있는 링크드 리스트
int main() {

	// 리스트 생성 및 초기화
	List list;
	int data;
	ListInit(&list);

	// 데이터 저장
	LInsert(&list, 11); LInsert(&list, 22);
	LInsert(&list, 33); LInsert(&list, 44);
	LInsert(&list, 55); LInsert(&list, 22);

	// 저장된 데이터 전체 출력
	printf("현재 데이터 수 : %d \n", LCount(&list));

	if (LFirst(&list, &data)) {
		printf("%d ", data);		// pdata로부터 데이터를 전해받은 data

		while (LNext(&list, &data)) {
			printf("%d ", data);
		}
	}

	printf("\n\n");

	// 숫자 22를 검색하여 전부 삭제
	if (LFirst(&list, &data)) {

		if (data == 22) {
			LRemove(&list);
		}

		while (LNext(&list, &data)) {
			if (data == 22) {
				LRemove(&list);
			}
		}
	}

	// 삭제 후 남아있는 데이터 전체 출력
	printf("현재 데이터 수 : %d \n", LCount(&list));

	if (LFirst(&list, &data)) {
		printf("%d ", data);		// pdata로부터 데이터를 전해받은 data

		while (LNext(&list, &data)) {
			printf("%d ", data);
		}
	}
	printf("\n\n");

	return 0;
}
#pragma endregion

 

 

-끗-