연결 리스트 2

유석현(SeokHyun Yu)·2022년 7월 28일
자료구조
0

자료구조 & 알고리즘

목록 보기
6/15
post-thumbnail

1. 원형 연결 리스트(Circular Linked List)

앞 챕터에서 우리가 구현한 연결 리스트의 마지막 노드는 NULL을 가리켰다.

바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 '원형 연결 리스트'가 된다.

즉 단순 연결 리스트가 다음의 구조라면,

마지막 노드가 첫 번째 노드를 가리켜서, 연결의 형태가 원을 이루는 다음 구조의 연결 리스트를 가리켜 '원형 연결 리스트'라 한다.

그럼 원형 연결 리스트의 특성을 조금 더 알기 위해서 위 그림의 상태에서 숫자 1이 저장된 노드를 머리 부분에 초가해보겠다.

그럼 리스트는 다음의 형태가 된다.

이번엔 반대로 숫자 1이 저장된 노드를 꼬리에 추가해보겠다.

그럼 리스트는 다음의 형태가 된다.

이제 위의 두 그림을 비교해 보자.

그러면 다음 사실을 알 수 있다.

"두 연결 리스트 모두 8이 저장된 노드는 1이 저장된 새 노드를 가리키고, 1이 저장된 새 노드는 2가 저장된 노드를 가리킨다."

이러한 특성 때문에 원형 연결 리스트에서는 머리와 꼬리의 구분이 없다고도 이야기한다.

실제로 위 그림에서 보이는 두 연결 리스트의 유일한 차이점은 포인터 변수 head가 무엇을 가리키느냐에 있다.

그것을 제외하면 위의 두 연결 리스트는 차이가 없다.

이번에는 마지막 그림과 같이 꼬리에 노드를 추가하는 방법에 대해서 고민해보자.

이를 위해서는 리스트의 꼬리를 가리키는 포인터 변수 tail이 필요하다는 생각이 든다.

그렇지 않은가?

하지만 그렇게 되면 원형 연결 리스트의 장점이 반감되어 버린다.

원형 연결 리스트의 장점 중 하나는 다음과 같기 때문이다.

"단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도,

하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다."

그래서 변형된 모델로 알려져 있지만, 실제로는 보다 일반적인 모델로 인식되는 '변형된 원형 연결 리스트'를 소개할 생각이다.

그럼 포인터 변수 tail이 없어서 문제라 했던, 연결 리스트의 끝에 노드를 추가하는 다음 그림을 다시 보자.

위의 그림상에서 꼬리에 새로운 노드를 추가하는 방법을 고민해보자.

head가 가리키는 것은 머리이니, 꼬리에 노드를 추가하기 위해서는 head를 시작으로 리스트의 끝을 찾아가는 과정을 거쳐야만 하는 상황이다.

하지만 위의 그림을 조금만 변경하면 이야기는 180도 달라진다.

"하나의 포인터 변수가, 머리가 아닌 꼬리를 가리키게 합시다!"

즉 다음과 같은 형태가 되게 하는 것이다.

위의 그림에서는 포인터 변수인 tail이 리스트의 끝을 가리키는 상황이니, 새로운 노드를 리스트의 끝에 추가하는 것은 어렵지 않다.

어디 그뿐인가? tail->next가 가리키는 것이 첫 번째 노드이니, 이것을 이용하면 리스트의 머리에도 노드를 쉽게 추가할 수 있다.

즉 다음과 같이 생각하면 되는 상황이다.

- 꼬리를 가리키는 포인터 변수는? tail 입니다!

- 머리를 가리키는 포인터 변수는? tail->next 입니다!

이렇듯 첫 번째 노드와 마지막 노드를 가리키는 포인터 변수가 각각 존재하는 상황이니, 어렵지 않게 머리와 꼬리에 새로운 노드를 추가할 수 있다.

앞 챕터에서 구현한 연결 리스트에서 나름 의미를 부여하고 싶은 함수를 묻는다면, 개인적으로는 다음 세 함수를 뽑고 싶다.

LFirst, LNext, LRemove

이유는 이들이 연결 리스트의 활용가치를 높인 함수들이기 때문이다.

저장한 데이터를 적절한 방법으로 참조하고 또 삭제할 수 없다면, 그저 저장이 전부였다면 활용가치는 높지 않았을 것이다.

따라서 원형 연결 리스트의 구현에도 이 세 함수를 추가할 것이다.

다만, 원형 연결 리스트의 구조적 특성상 LNext 함수의 기능을 다음과 같이 조금 변경하고자 한다.

"LNext 함수는 무한 반복 호출이 가능하며, 리스트의 끝에 도달할 경우 첫 번째 노드부터 다시 조회가 시작됩니다."

반면 정렬과 관련이 있었던 기능은 제외시키고자 한다.

이는 원형 연결 리스트를 구현하는데 있어서 불필요한 부분을 최소화하기 위함이다.

끝으로 데이터를 저장하는 함수는 두 개를 정의하고자 한다.

이는 리스트의 머리에, 그리고 꼬리에 노드를 추가할 수 있게 하기 위함이다.

원칙은 이 시점에서 원형 연결 리스트의 ADT를 정의하는 것이 옳으나, 앞서 보인 연결 리스트의 ADT와 차이가 나는 부분이 매우 적으니, 바로 이어서 헤더파일을 정의하도록 하겠다.

CLinkedList.h

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

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

typedef struct _CLL
{
	Node * tail;
	Node * cur;
	Node * before;
	int numOfData;
} CList;


typedef CList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);
void LInsertFront(List * plist, Data data);

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
Data LRemove(List * plist);
int LCount(List * plist);

#endif

위의 헤더파일에 담긴 배용 대부분이 익숙할 것이다.

다만 데이터의 입력과 관련해서 다음과 같이 두 개의 함수가 선언된 점에만 유의하자.

void LInsert(List * plist, Data data);
void LInsertFront(List * plist, Data data);

다음은 헤더파일의 소스파일이다.

CLinkedList.c

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

void ListInit(List * plist)
{
	plist->tail = NULL;
	plist->cur = NULL;
	plist->before = NULL;
	plist->numOfData = 0;
}

void LInsertFront(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

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

	(plist->numOfData)++;
}

void LInsert(List * plist, Data data)
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

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

	(plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
	if(plist->tail == NULL) // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->tail; // before가 꼬리를 가리키게 한다.
	plist->cur = plist->tail->next; // cur이 머리를 가리키게 한다.

	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환
	return TRUE;
}

int LNext(List * plist, Data * pdata)
{
	if(plist->tail == NULL) // 저장된 노드가 없다면
		return FALSE;

	plist->before = plist->cur; // before가 다음 노드를 가리키게 한다.
	plist->cur = plist->cur->next; // cur이 다음 노드를 가리키게 한다.

	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환
	return TRUE;
}

Data LRemove(List * plist)
{
	Node * rpos = plist->cur;
	Data rdata = rpos->data;

	if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
	{
		if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
			plist->tail = NULL;
		else
			plist->tail = plist->before;
	}

	plist->before->next = plist->cur->next;
	plist->cur = plist->before;

	free(rpos);
	(plist->numOfData)--;
	return rdata;
}

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

위의 원형 연결 리스트를 테스트하기 위한 main 소스파일이다.

CLinkedListMain.c

#include <stdio.h>
#include "CLinkedList.h"

int main(void)
{
	// 원형 연결 리스트의 생성 및 초기화 ///////
	List list;
	int data, i, nodeNum;
	ListInit(&list);

	// 리스트에 5개의 데이터를 저장 /////// 
	LInsert(&list, 3);
	LInsert(&list, 4);
	LInsert(&list, 5);
	LInsertFront(&list, 2);
	LInsertFront(&list, 1);
	
	// 리스트에 저장된 데이터를 연속 3회 출력 ///////
	if(LFirst(&list, &data))
	{
		printf("%d ", data);
		
		for(i=0; i<LCount(&list)*3-1; i++)
		{
			if(LNext(&list, &data))
				printf("%d ", data);
		}
	}
	printf("\n");

	// 2의 배수를 찾아서 모두 삭제 ///////
	nodeNum = LCount(&list);

	if(nodeNum != 0)
	{
		LFirst(&list, &data);
		if(data%2 == 0)
			LRemove(&list);
		
		for(i=0; i < nodeNum-1; i++)
		{
			LNext(&list, &data);
			if(data%2 == 0)
				LRemove(&list);
		}
	}

	// 전체 데이터 1회 출력 ///////
	if(LFirst(&list, &data))
	{
		printf("%d ", data);
		
		for(i=0; i<LCount(&list)-1; i++)
		{
			if(LNext(&list, &data))
				printf("%d ", data);
		}
	}
	return 0;
}

2. 양방향 연결 리스트

'양방향 연결 리스트(doubly linked list)' 또는 '이중 연결 리스트'라고도 불리는 이 자료구조는 그 이름이 의미하듯이 노드가 양쪽 방향으로 연결된 구조의 리스트이다.

즉 왼쪽 노드가 오른쪽 노드를 가리킴과 동시에 오른쪽 노드도 왼쪽 노드를 가리키는 구조이다.

이제는 리스트의 그림만 보아도 구조를 이해할 수 있을 정도가 되었을 것이다.

따라서 양방향 연결 리스트의 유형 몇 가지를 그림을 통해서 소개하고자 한다.

먼저 가장 기본이 되는 모델을 소개하겠다.

위 그림에서 보이듯이 하나의 노드가 자신의 왼쪽과 오른쪽 노드를 동시에 가리키는 구조가 양방향 연결 리스트이다.

때문에 양방향 연결 리스트의 노드를 표현하는 구조체는 다음과 같이 정의된다.

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

그리고 다음 그림과 같이 더미 노드가 추가된 양방향 연결 리스트도 존재하는데, 더미 노드의 이점은 단순 연결 리스트에서 보인 바와 같다.

또한 다음 그림과 같이 양방향 연결 리스트이면서 원형 연결 리스트의 구조를 동시에 지니는 리스트도 존재한다.

하지만 지금 보인 이 세 가지 모델이 양방향 연결 리스트의 전부는 아니다.

양방향이라고 해서 구현이 어려울 것 같지만 그렇지 않다!

포인터 변수 before의 용도를 기억하는가?

이는 리스트가 한쪽 방향으로만 조회 가능하기 때문에 유지해야 하는, 삭제의 과정을 위해 유지해야 하는 멤버이다.

하지만 양방향 연결 리스트는 양방향으로 얼마든지 조회가 가능하다.

따라서 포인터 변수 before가 불필요하고, before를 유지하기 위해 곳곳에 존재하는 문장들도 불필요하다.

이렇듯 양방향으로 노드를 연결하는 것에는 큰 이점이 있다.

물론 노드를 양방향으로 연결하기 위해서는 몇몇 문장이 추가된다.

하지만 그래봤자 노드의 삽입 및 삭제 과정에서 한두 문장이 더 추가되는 정도이다.

때문에 코드가 더 복잡해진다는 생각은 버리는 것이 옳다.

그럼 지금까지 설명한 양방향 연결 리스트의 헤더파일과 소스파일을 정리해 보이겠다.

DBLinkedList.h

#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

typedef struct _dbLinkedList
{
	Node * head;
	Node * cur;
	int numOfData;
} DBLinkedList;

typedef DBLinkedList List;

void ListInit(List * plist);
void LInsert(List * plist, Data data);

int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);

int LCount(List * plist);

#endif

DBLinkedList.c

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

void ListInit(List * plist)
{
	plist->head = NULL;
	plist->numOfData = 0;
}

void LInsert(List * plist, Data data) // 첫 번재 노드의 추가 과정만 담음
{
	Node * newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;

	newNode->next = plist->head;
	if(plist->head != NULL) // 두 번째 이후의 노드를 추가할 때만 실행
		plist->head->prev = newNode;

	newNode->prev = NULL;
	plist->head = newNode;

	(plist->numOfData)++;
}

int LFirst(List * plist, Data * pdata)
{
	if(plist->head == NULL)
		return FALSE;

	plist->cur = plist->head;
	*pdata = plist->cur->data;

	return TRUE;
}

int LNext(List * plist, Data * pdata)
{
	if(plist->cur->next == NULL)
		return FALSE;

	plist->cur = plist->cur->next; // cur을 오륵쪽으로 이동
	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환

	return TRUE;
}

int LPrevious(List * plist, Data * pdata)
{
	if(plist->cur->prev == NULL)
		return FALSE;

	plist->cur = plist->cur->prev; // cur을 왼쪽으로 이동
	*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환

	return TRUE;
}

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

DBLinkedListMain.c

#include <stdio.h>
#include "DBLinkedList.h"

int main(void)
{
	// 양방향 연결 리스트의 생성 및 초기화  ///////
	List list;
	int data;
	ListInit(&list);

	// 8개의 데이터 저장  ///////
	LInsert(&list, 1);  LInsert(&list, 2);
	LInsert(&list, 3);  LInsert(&list, 4);
	LInsert(&list, 5);  LInsert(&list, 6);
	LInsert(&list, 7);  LInsert(&list, 8);

	// 저장된 데이터의 조회  ///////
	if(LFirst(&list, &data))
	{
		printf("%d ", data);

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

	return 0;
}
profile
유석현(SeokHyun Yu)
Backend Engineer
이전 포스트

연결 리스트 1

다음 포스트

스택(Stack)

0개의 댓글