(C) 자료구조 - 단일 연결 리스트(Singly Linked List)

안녕하세요!

오늘은 단일 연결 리스트 (Singly Linked list) 를 구현해 보도록 하겠습니다.

블로그를 돌아다니시면 많은 예제들이 있겠지만 

이런 방식도 있구나! 할 수 있게 도움 되시라고

제가 공부하면서 구현한것도 설명과 함께 올려 보도록 할게요.

C 의 Malloc 과 free 를 사용 하였습니다!

 

1. 단일 연결 리스트(Singly Linked list)란?

 

각 노드가 데이터와 다음 노드 정보를 가지고

한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입니다!

오직 다음 노드 정보만 가지고 있기에 단일 이라는 이름이 붙었습니다.

 

2. 단일 연결 리스트(Singly Linked list) 방식 설명

 

링크드 리스트를 찾아보셧다면 구현한 방법들이 조금씩 다르다는 것 느끼셧을거에요

대표적으로 더미 노드를 사용 하는 방법, 사용 안 하는 방법이 있습니다.

더미노드를 사용하면 약간의 byte 를 더 소모하는 대신 

로직을 좀 더 단순화 할수 있다는 장점이 있습니다.

오늘 구현할 방식은 더미노드를 사용하는 방식이에요.

 

제가 구현할 단일 연결 리스트 구조는 이렇습니다.

더미 = 데이터를 가지고 있지 않고 노드 정보만 가지고 있다.

head(머리 더미) = 데이터 없이 첫번째 노드를 가르킨다.

tail(꼬리 더미) = 데이터 없이 꼬리 자신을 가르킨다.

즉 head 와 tail 은 오로지 처음과 끝을 알리는 역할만 합니다.

아래 그림에서 Nodes는 상황에 따라 0개가 될수도 여러개가 될수도 있겠죠!

head 와 tail 은 Initlist 함수를 호출 한 이후 계속 존재 하고 그 사이에 있는 Nodes만 삽입하고 제거 하는 식입니다.

tail 은 다음노드를 가리킬수 없으니 tail 자기 자신을 가르킬 것이구요!

아래 그림에서 Initlist 는 head와 tail 을 만들고

그 이후 다른 함수에서는 파란색 박스만 수정할 거에요!

구현 로직

 

 

3. 단일 연결 링크드 리스트 구현

 

노드는 다음과 같이 구성되어있습니다.

struct Node
{
	int data;	// 가지고 있는 데이터
	Node* next;	// 다음 노드 정보
};

 

다음으로는 구현할 내용들을 선언하도록 하겠습니다.

Node* head;	//더미 머리 
Node* tail;	//더미 꼬리 
int size;	//링크드 리스트 크기

void InitList();						//리스트 초기화
bool InsertAfter(int value, Node* node);			//특정 노드 뒤 삽입
bool DeleteNext(Node* node);					//특정 노드 뒤 삭제
bool DeleteNode(Node* node);					//특정 노드 삭제
Node* FindNodeUsingValue(int value);				//data 비교하여 노드 찾기
Node* FindNodeUsingIndex(int num);				//index 비교하여 노드찾기
int GetIndex(int value);					//특정 data 의 index 반환
int GetSize() { return size; }					//리스트의 크기 반환
void DeleteAll();						//모든 노드 제거
void PrintList();						//모든 노드 출력

 

구현해 놓고 보니 이것 저것 많네요

일단 생각나는 기능들을 다 구현한거 같아요.

함수 하나씩 살펴보도록 하겠습니다.

 

InitList

void InitList()
{
	head = (Node*)malloc(sizeof(Node));		//머리 메모리 할당
	tail = (Node*)malloc(sizeof(Node));		//꼬리 메모리 할당
	head->next = tail;				//머리 다음은 꼬리
	tail->next = tail;				//꼬리 다음도 꼬리
	size = 0;					//사이즈는 0
}

더미 노드인 head 와 tail 을 만들어 주는 함수입니다.

 

InsertAfter

bool InsertAfter(int value, Node* node)
{
	if (node == tail)				//꼬리 뒤에 삽입 할수 없다.
		return false;

	Node* newNode = (Node*)malloc(sizeof(Node));	//메모리 할당
	newNode->data = value;				//값을 넣어준다
	newNode->next = node->next;			//특정노드가 가르키던 노드를 내가 대신 가르키고
	node->next = newNode;				//특정노드가 나를 가르키게 한다.
	++size;						//크기를 하나 늘려준다.
	printf("Insert : %d \n", newNode->data);	//메세지 출력
	return true;
}

기본적으로 링크드리스트는 이전노드가 아닌 다음 노드의 정보를 가지고 있기 때문에

특정 노드 뒤에 Insert 하는 방식으로 구현하였습니다.

 

tail은 끝을 알리는 더미데이터 이기때문에 tail 뒤에 삽입 할수 없도록 return 을 시켜줍니다.

나머지는 그림으로 살펴보도록 하겠습니다.

노드를 생성한다.

특정 노드가 가르키던 노드를 가르킨다.

특정노드가 생성된 노드를 가르키게 한다.

newNode 가 2번째 자리로 오게되었다 

 

DeleteNext

bool DeleteNext(Node* node)
{
	if (node->next == tail)				//꼬리를 지울수 없다.
		return false;

	Node* deleteNode = node->next;			//지울 노드를 기억한다.
	printf("delete : %d \n", deleteNode->data);	//메세지 출력
	node->next = deleteNode->next;			//지울 노드가 가르키던 노드를 특정 노드가 가르키게 한다.
	free(deleteNode);				//메모리를 해제해준다(중요)
	--size;						//크기를 줄여준다.
	return true;
}

이 함수는 특정 노드가 아니라 특정 노드의 다음 노드를 지우는 함수입니다!

 

마지막 노드라면 (꼬리를 가르키고 있으면) 지울 노드가 없기때문에 return

지울노드를 tempdeleteNode 에 저장해 주고

지울노드가 가르키던 노드를 특정 노드가 가르키게 합니다.

그리고 지울노드를 메모리 해제를 시켜줌으로써 Delete가 되었습니다.

 

DeleteNode

bool DeleteNode(Node* node)
{
	if (node == head || tail == node)	//머리나 꼬리는 지울수 없다.
		return false;

	Node* preNode = head;			//노드는 이전노드 정보를 가지고 있지 않아서 따로 기억해야한다.
	Node* temp = head->next;		//찾는 노드

	while (temp != tail)					//리스트를 끝까지 돈다.
	{
		if (node == temp)				//지울 노드를 찾았다면
		{
			Node* deleteNode = node;		//지울 노드를 기억한다.
			preNode->next = deleteNode->next;	//이전 노드가 지울 노드의 다음을 가르키게한다.
			printf("delete : %d \n", deleteNode->data);
			free(deleteNode);			//지울 노드를 메모리 해제
			--size;					//크기를 줄여준다.
			return true;
		}

		preNode = temp;			//못 찾았으면
		temp = temp->next;		//다음 노드로
	}
	return false;
}

이 함수는 특정 노드를 지우는 함수입니다.

특정노드를 지운다면 앞 뒤를 연결 해 주어야 하는데

나를 가리키는 노드의 정보를 알수 없으니

나를 가리키는 노드인 이전노드 (preNode)가 필요합니다

이전노드가 지울노드가 가르키던 노드를 가르키게 하고

노드를 지워줍니다.

 

FindNodeUsingValue

Node* FindNodeUsingValue(int value)
{
	Node* temp = head->next;		//찾는 노드
	while (temp != tail)			//리스트를 끝까지 돈다
	{
		if (temp->data == value)	//특정 값을 가진 노드를 찾았으면
		{
			printf("Find Value Data : %d \n", temp->data);
			return temp;		//노드를 반환한다.
		}
		temp = temp->next;		//못 찾았으면 다음 노드로
	}
	return temp;				//끝까지 돌았는데 없으면 꼬리 노드 반환
}

노드가 가지고 있는 값을 비교해서 그 노드를 반환하는 함수입니다!

따로 설명드릴만한건 없는거 같네요!

 

FindNodeUsingIndex

Node* FindNodeUsingIndex(int num)
{
	if (num < 0 || num >= size)			//크기에 벗어나 있으면 꼬리반환
		return tail;

	Node* temp = head->next;			//head next 가 index 0 노드이다
	for (int i = 0; i < num;++i)			//반복문을 돌아서
		temp = temp->next;			//num 번째 node를 찾는다.

	printf("Find index : %d Data : %d \n", num, temp->data);
	return temp;
}

index 를 입력하면 그 index 의 노드를 반환하는 함수입니다.

 

GetIndex

int GetIndex(int value)
{
	int index = 0;
	Node* temp = head->next;		
	while (temp != tail)		
	{
		if (temp->data == value)
		{
			printf("Value : %d index : %d \n", value, index);
			return index;
		}
		++index;
		temp = temp->next;
	}

	return -1;
}

FindNodeUsingValue 함수와 같습니다.

단지 반환값이 그 노드가 아니라 그 노드의 index 라는 것만 다를 뿐입니다!

참고로 Index 는 0 부터 시작합니다!

 

DeleteAll

void DeleteAll()
{
	Node* temp = head->next;		//찾는 노드
	Node* deleteNode;			//지울 노드
	while (temp != tail)			//리스트 끝까지 돈다.
	{
		deleteNode = temp;		//현재 노드를 지울 노드로 지정한다.
		temp = temp->next;		//현재 노드는 다음 노드로 넘어간다.
		free(deleteNode);		//지울 노드를 지워준다.
	}
	size = 0;				//사이즈 초기화
	head->next = tail;			//다 비었으니 head 다음은 tail

	printf("Delete All\n");
}

모든 노드를 지워주는 함수 입니다!

맨 처음에 head 와 tail 을 제외한 노드들만 삽입되고 제거 된다고 했는데

head 와 tail 사이에 있는 모든 노드를 제거 하는 함수 입니다.

 

PrintList

void PrintList()
{
	Node* temp = head->next;			//찾는 노드
	while (temp != tail)				//리스트 끝까지 돈다.
	{
		printf("%d \n", temp->data);		//메세지 출력
		temp = temp->next;			//다음 노드로
	}
	printf("size : %d \n", size);			//크기도 출력
}

리스트에 담겨 있는 모든 노드를 출력합니다.

head 와 tail 사이에 있는 노드들을 순서대로 출력합니다.

 

4. 테스트

int main()
{
	InitList();		//시작 전에 꼭 해주어야 한다.
    
	InsertAfter(10, head);
	InsertAfter(20, FindNodeUsingIndex(0));
	InsertAfter(30, FindNodeUsingValue(10));
	InsertAfter(40, FindNodeUsingIndex(GetSize() - 1));
	PrintList();
    
	printf("\n");
	DeleteNode(FindNodeUsingIndex(GetIndex(40)-1));
	DeleteNode(FindNodeUsingValue(10));
	DeleteNode(FindNodeUsingValue(100));	//find 실패로 작동하지 않음
	PrintList();

	printf("\n");
	DeleteNext(FindNodeUsingIndex(GetSize() - 1));	// nextNode가 tail이라 delete 작동 하지 않음
	DeleteNext(FindNodeUsingIndex(0));
	DeleteNext(FindNodeUsingValue(100));	//find 실패로 작동하지 않음
	InsertAfter(50, head);
	PrintList();

	printf("\n");
	DeleteAll();
	PrintList();
}

출력 결과

음.... 알아보기 조금 힘들긴 하지만 그래도 원하는데로 작동하였습니다!

추가로 맨 마지막에 값이 추가 되는 Add 함수를 정의하고 싶다면 아래와 같이 하면 될 거에요.

void Add(int value)
{
	if(GetSize() == 0)
		InsertAfter(value, head);
	else
		InsertAfter(value, FindNodeUsingIndex(GetSize() - 1));
}

 

감사합니다!

 

 

다른 자료구조

단일 연결 리스트(Singly Linked List)

이중 연결 리스트(Doubly Linked List)

스택(Stack) - 배열(Array), 링크드리스트(Linked List)

큐(Queue) - 배열(Array), 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

이진트리(Binary Tree) - 링크드리스트(Linked List)

우선순위 큐(Priority Queue) - 힙(Heap) - 배열(Array)