C로 만드는 자료구조-연결 리스트

연결 리스트(Linked List)란?

연결 리스트는 배열 리스트와 다르게 포인터를 이용하여 구현한다. 포인터를 이용하여 순차적으로 자료를 연결하기 때문에 물리적으로 각 자료들이 어디에 위치해 있는지 상관이 없어진다. 아래 그림과 같이 각 자료들이 어디에 물리적 위치는 인접해 있지 않지만 자료들은 순차적으로 연결되어 있다.

추가적으로 연결 리스트는 배열 리스트와 다르게 저장 가능한 최대 원소의 개수를 지정해 주지 않아도 된다.
연결 리스트는 자료들끼리 붙어있어야 한다는 물리적 제약이 없기 때문에 그냥 새로운 원소를 생성하고 포인터를 이용해 연결만 잘해주면 된다.

연결 리스트의 구조

배열 리스트의 노드(원소)는 자료(Data)만 담고 있었지만 연결 리스트의 노드는 자료에 다음 노드로 연결되는 링크(Link)도 가지고 있어야 한다. 이때 맨 마지막 노드는 연결할 다음 노드가 없으므로 NULL값을 준다. 아래 그림은 연결 리스트에서의 노드값의 구조이다.

연결 리스트의 노드 추가

배열 리스트에서 했던 원소 추가를 그대로 한다고 생각해보자, 배열 리스트에서는 원소를 원하는 자리에 추가하기 위해서 기존 원소 이동이 필요 했지만 연결 리스트에서는 포인터를 사용하기 때문에 원소 이동이 필요 없다. 그냥 링크만 재설정해주면 된다. 그림을 통해 알아보자.

위 그림과 같이 인덱스 2에 새로운 원소 '5'를 집어 넣기 위해서는 새로운 원소 생성 후 기존에 존재하던 링크 중 불필요한 링크('2'->'3')를 제거하고 새로운 링크('2'->'5', '5'->'3')를 추가해 주면 된다.

연결 리스트의 노드 제거

연결 리스트에서의 노드 제거도 마찬가지로 불필요한 링크 및 노드는 삭제하고 새로 만들어야할 링크들을 추가해주면 된다. 그림을 통해 알아보자.

위 그림과 같이 인덱스 2에 있는 원소'3'을 제거하기 위해 불필요한 링크('2'->'3' , '3' ->4)를 제거하고
('2'->'4')를 추가 해주면 된다. 이때 주의해야 할 점은 원소 제거 후 메모리를 해제하는 추가 과정이 필요하다. 여기서는 '3'의 메모리를 해제해주어야 한다.

연결 리스트의 장단점

장점

- 원소 이동이 적다
배열 리스트와 다르게 원소를 추가/제거할 때 적절하게 노드 사이에 링크만 재설정해주면 되기 때문에 원소를 하나하나씩 이동시켜줘야 하는 배열 리스트에 비해 연산이 적다.

- 최대 원소 개수를 지정해주지 않아도 된다.
배열 리스트는 물리적으로도 연결되어야 하기 때문에 리스트 생성 시 메모리를 할당할 때 반드시 최대 원소 개수를 지정해주어야 한다. 따라서 예상보다 더 많은 원소를 저장해야 한다면 다시 메모리를 할당하고 옮겨야 하는 불편함이 있다. 하지만 연결 리스트에서는 물리적 제약이 없기 때문에 링크만 제대로 설정한다면 새로운 원소를 얼마든지 추가할 수 있다.

단점

- 구현이 어렵다.
연결 리스트는 포인터를 사용하기 때문에 동적 할당, 포인터 연산 등을 해야 하기 때문에 상대적으로 배열 리스트 구현이 간단하고 직관적이다.

- 탐색 연산 비용이 높다.
배열 리스트 같은 경우에는 자료들이 물리적으로 연결되어 있기 때문에 원하는 위치에 있는 원소를 쉽게 찾을 수 있다. 그러나 연결 리스트 같은 경우에는 자료를 찾는 방법이 오직 맨 처음 원소부터 시작해 원하는 위치에 있는 원소까지 링크를 따라가야 하므로 연산 비용이 높아진다. 예를 들어 배열 리스트 경우에는 pElement [위치 인덱스]로 바로 원하는 위치로 접근이 가능 하지만 연결 리스트의 경우는 for문을 이용하여 원하는 위치 인덱스까지 따라 접근해야 한다.

연결 리스트 구현

소스 파일의 구성은 다음과 같다.

파일 이름	내용
linkedlist.h	구조체 및 함수 선언
linkedlist.cpp	함수 구현
LinkedListMain.cpp	main 함수 실행

1.linkedlist.h

#include<iostream>
using namespace std;

typedef struct ListNode {
	int data;
	struct ListNodeType* pLink;
};
typedef struct LinkedList {
	int currentElementCount;
	ListNode headerNode;
};

LinkedList* createLinkedList();//연결 리스트 생성
int addLLElement(LinkedList* pList, int position, ListNode element);//리스트에 원하는 위치에 자료 추가
int removeLLElement(LinkedList* pList, int position);// 리스트에서 해당위치에 존재하는 자료 제거
ListNode* getLLElement(LinkedList* pList, int position);//리스트에서 해당위치에 존재하는 자료 반환

void clearLinkedList(LinkedList* pList);//리스트 비우기
int getLinkedListLength(LinkedList* pList);// 리스트 길이 반환
void deleteLinkedList(LinkedList* pList);// 리스트 삭제

-ListNode는 자료 값(data)과 링크(pLink)로 구성되어 있다.
-LinkedList는 현재 저장 중인 원소의 개수(currentElementCount)와 headerNode로 구성되어 있다. 여기서 헤더 노드(headerNode)는 실제로 값을 저장하는 노드는 아니고 리스트 기능 구현을 쉽게 하기 위한 일종의 더미(Dummy) 노드이다. 다시 말해 원하는 노드로 가기 위한 도구라고 생각하면 된다. 보통 리스트의 헤더 노드의 링크(headerNode->pLink)는 리스트의 맨 처음 노드에 연결되어있다.
추가적으로 #define을 이용해 TURE은 1, FALSE는 0 값으로 정의해주었다.

2.linkedlist.cpp

-createLinkedList()

LinkedList* createLinkedList() {
	LinkedList *pReturn = NULL;
	pReturn = new LinkedList;
	if (pReturn != NULL)
		memset(pReturn, 0, sizeof(LinkedList));
	else {
		cout << "오류, 메모리 할당 createLinkedList()\n" << endl;
		return NULL;
	}
	return pReturn;
}//연결 리스트 생성

LinkedList에 대한 메모리를 할당하고 값을 0으로 준다. 이때 pReturn!= NULL을 하는 이유는 메모리 할당이 잘되었는지 검증하기 위함이다.

-addLLElement()

int addLLElement(LinkedList* pList, int position, ListNode element) {
	int ret = FALSE;
	int i = 0;
	ListNode* pPreNode = NULL;
	ListNode* pNewNode = NULL;
	if (pList != NULL) {
		if (position >= 0 && position <= pList->currentElementCount) {
			pNewNode = new ListNode;
			if (pNewNode != NULL) {
				*pNewNode = element;
				pNewNode->pLink = NULL;

				pPreNode = &(pList->headerNode);
				for (i = 0; i < position; i++) {
					pPreNode = pPreNode->pLink;
				}
				pNewNode->pLink = pPreNode->pLink;
				pPreNode->pLink = pNewNode;

				pList->currentElementCount++;
				ret = TRUE;
			}
			else {
				cout << "오류,메모리 할당 addLLElement()\n" << endl;
				return ret;
			}
		}
		else {
			cout << "오류,위치 인덱스, addLLElement()\n" << endl;
	
		}
	}
	return ret;
}//리스트에 원하는 위치에 자료 추가

배열 리스트에서의 원소 추가와 마찬가지로 pList!= NULL인지 체크하고 새로 노드를 추가하려는 위치가 적합한지 체크한다. 확인되면 pNewNode에 메모리를 할당하고 입력받은 원소로 값을 준다. 그 후에는 링크 재설정을 위해 새로운 원소를 넣을 위치 한 단계 앞에 있는 노드(인덱스 position-1에 위치한 노드)를 찾아야 한다. 따라서 pPreNode를 시작 값인 hederNode값으로 초기화해주고 for 문을 이용하여 pPreNode를 인덱스 position-1에 위치한 노드까지 이동시킨다.
이동시킨 후에는 새로 추가할 노드(pNewNode), 해당 위치에 존재하는 노드(pPreNode->pLink), 해당 위치 이전에 존재하는 노드(pPreNode)를 다 찾았으므로 링크를 재설정해준다. 성공하면 currentElementCount에 1을 더해주고 TRUE를 반환한다. 이때 원소가 하나도 없는 상태라면 herderNode->pLink=pNewNode가 된다. 아래 그림은 함수의 과정을 나타낸다.

-removeLLElement()

int removeLLElement(LinkedList* pList, int position) {
	int ret = FALSE;
	int i = 0;
	int arrayCount = 0;
	ListNode* pPreNode = NULL;
	ListNode* pDelNode = NULL;
	if (pList != NULL) {
		arrayCount = getLinkedListLength(pList);
		if (position >= 0 && position < arrayCount) {
			pPreNode = &(pList->headerNode);
			for (i = 0; i < position; i++) {
				pPreNode = pPreNode->pLink;
			}
			pDelNode = pPreNode->pLink;
			pPreNode->pLink = pDelNode->pLink;
			delete pDelNode;
			pList->currentElementCount--;
			ret = TRUE;
		}
		else {
			cout << "오류,위치 인덱스, addLLElement()\n" << endl;
			return ret;
		}
		return ret;
	}
}// 리스트에서 해당위치에 존재하는 자료 제거

원소 추가와 마찬가지로 pList!= NULL인지 체크하고 새로 노드를 추가하려는 위치가 적합한지 체크한다.
체크 후에는 삭제할 노드(pDelNode)와 삭제하는 위치 한 칸 앞에 있는 노드(pPreNode)를 찾아야 한다. pPreNode를 headerNode로 초기화하고 for 문을 이용해 인덱스 position-1에 위치한 노드를 찾는다. 이때 position-1에 있는 링크에 연결된 노드가 삭제할 노드가 된다. 이제 링크를 재설정해준다. 추가적으로 delete를 사용하여 pDelNode의 메모리 할당을 해제해주어야 한다. 성공하면 currentElementCount에 1을 빼주고 TRUE를 반환한다. 아래 그림은 함수의 과정을 나타낸다.

나머지 함수

나머지 기능들을 구현한 함수의 코드이다. 이해하기 어렵지 않을 것이다.

ListNode* getLLElement(LinkedList* pList, int position) {
	ListNode* pReturn = NULL;
	int i = 0;
	ListNode* pNode = NULL;

	if (pList != NULL) {
		if (position >= 0 && position < pList->currentElementCount) {
			pNode = &(pList->headerNode);
			for (i = 0; i <= position; i++) {
				pNode = pNode->pLink;
			}
			pReturn = pNode;
		}
	}
	return pReturn;
}// 리스트에서 해당위치에 존재하는 자료 반환

void clearLinkedList(LinkedList* pList) {
	if (pList != NULL) {
		if (pList->currentElementCount > 0) {
			removeLLElement(pList, 0);
		}
	}
}//리스트 비우기
int getLinkedListLength(LinkedList* pList) {
	int ret = 0;
	if (pList != NULL) {
		ret = pList->currentElementCount;
	}
	return ret;
}// 리스트 길이 반환
void deleteLinkedList(LinkedList* pList) {
	if (pList != NULL) {
			clearLinkedList(pList);
			delete pList;
		
	}
}// 리스트 삭제

int isEmpty(LinkedList* pList) {
	int ret = FALSE;
	if (pList != NULL) {
		if (pList->currentElementCount == 0) {
			ret = TRUE;
		}
	}
	return ret;
}//빈 리스트 인지 확인
void displayLinkedList(LinkedList* pList) {
	if (pList != NULL) {
		cout << "현재 원소의 개수: " << pList->currentElementCount << endl;
		for (int i = 0; i < pList->currentElementCount; i++) {
			cout << getLLElement(pList, i)->data << '\t';
		}
	}
	else {
		cout << "원소가 존재하지 않습니다." << endl;
	}
	cout << endl;
}//리스트를 출력하는 함수

3.LinkedListMain.cpp

#include "stdafx.h"
#include"linkdist.h"

int main()
{	
	int arrayCount = 0;
	LinkedList *pList = NULL;
	ListNode* pNode = NULL;
	ListNode node;

	pList = createLinkedList();

	if (pList != NULL) {
		node.data = 1;
		addLLElement(pList, 0, node);

		node.data = 3;
		addLLElement(pList, 1, node);

		node.data = 5;
		addLLElement(pList, 2, node);
		displayLinkedList(pList);

		removeLLElement(pList, 0);
		displayLinkedList(pList);

		deleteLinkedList(pList);
	}


    return 0;
}

실행결과

728x90

저작자표시 비영리

'컴퓨터 공학 > 자료구조' 카테고리의 다른 글

C로 만드는 자료구조- Stack이란? (0)	2020.08.29
C로 만드는 자료구조-이중 연결 리스트 (0)	2020.08.22
C로 만드는 자료구조-원형 연결 리스트 (0)	2020.08.22
C로 만드는 자료구조-배열 리스트 (0)	2020.08.16
C로 만드는 자료구조-List란? (0)	2020.08.15