추상자료형 리스트

Posted on | In



개요

추상 자료형으로서의 리스트 개념과 필요한 작업들에 대해서 알아볼것이다.

리스트를 구현하는데는 2가지 방법이 있는데, 배열과 연결리스트이다. 두가지 모두 알아볼 것이다.

자료구조로서의 배열과 연결 리스트의 장단점을 알아볼 것이다.

리스트에 대해서 숙지하고 나면 직접 한번 구현해보겠다.



리스트

리스트는 영어 List란 문자 그대로 목록이라는 뜻이다.

즉 목록을 추상화 한 추상자료형으로써 여러 데이터 항목을 순서대로 저장하여 한꺼번에 관리할 수 있도록 한것이다.

리스트의 구현은 배열을 사용하는 방법과 포인터를 사용하는 방법으로 나뉜다.

각각 배열리스트와 링크드리스트 혹은 연결리스트라고 부른다.

리스트는 추상 자료형이다. 그렇다면 데이터들의 집합과 그걸 처리하는 작업들이 있을 것이다.

그것을 사용자 입장에서 생각을 해보자.

사용자 입장에서 당연히 리스트를 생성하는 작업이 필요할 것이다.

리스트를 생성하였다면 어떤 데이터를 추가 혹은 삭제하는 작업이 필요하다.

이렇게 존재하는 데이터를 검색하는 기능도 필요할 것이다.

리스트를 사용 완료했다면 리스트를 없애는 기능도 필요할 것이다.

이제 구현자 관점에서 보면 리스트를 배열로 만들지 연결 리스트로 만들지를 생각해야한다.

그 다음 필요한 자료들을 생각해보고 작업들을 어떻게 구현할 지 생각해본다.

우선 배열로 리스트를 구현하는 방법에 대해 알아보겠다.



배열 리스트

배열 리스트는 자료형 배열과 같이 위치 인덱스로 자료를 저장하기 때문에 논리적 저장 순서와 물리적 저장 순서가 동일하다.

배열로 구현할 때의 최대 장점은 직접 접근이 가능하는 점이다.

즉 배열 인덱스를 사용하여 검색하려는 데이터를 단번에 찾아내기 때문에 매우 빠른 속도의 검색이 가능하다.

반면 배열은 배열 크기를 컴파일 이전에 미리 선언해야 한다는 점이다.

또한 배열의 크기가 엄청나게 많아진다면 그 배열 인덱스 하나하나를 처리해야 하므로 시간적인 부담이 늘어난다.

다음은 리스트를 구현하는 헤더 파일로 한 단위별로 살펴보겠다.

arraylist.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifndef _ARRAYLIST_
#define _ARRAYLIST_

typedef struct ArrayListNodeType
{
	int data;
} ArrayListNode;

typedef struct ArrayListType
{
	int maxElementCount;		// 최대 원소 개수
	int currentElementCount;	// 현재 원소의 개수
	ArrayListNode *pElement;	// 원소 저장을 위한 1차원 배열
} ArrayList;

ArrayList* createArrayList(int maxElementCount);
void deleteArrayList(ArrayList* pList);
int isArrayListFull(ArrayList* pList);
int addALElement(ArrayList* pList, int position, ArrayListNode element);
int removeALElement(ArrayList* pList, int position);
ArrayListNode* getALElement(ArrayList* pList, int position);
void displayArrayList(ArrayList* pList);
void clearArrayList(ArrayList* pList);
int getArrayListLength(ArrayList* pList);

#endif

#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_

#define TRUE		1
#define FALSE		0

#endif

typedef struct ArrayListNodeType

배열 인덱스 하나 즉 노드 하나를 의미하는 것 같은데 이렇게 되면 구조체 배열인가??? 일반 int형 배열인가??

자료 하나인데 굳이 구조체로 떼어놓은 이유가 무엇일까??

typedef struct ArrayListType

maxElementCount는 최대 원소 개수를 저장하는 용도

currentElementCount는 현재 원소의 개수인데 최대 원소의 개수랑 비교해서 넘지 않게 하는 용도

ArrayListNode *pElement는 pElement라는 구조체 변수로 1차원 배열을 하나 만드는 용도 같다.

여기서 그냥 int *data;하면 안될까??

ArrayList* createArrayList(int maxElementCount);

자료형쪽 * 변수쪽 * 무슨 규칙 같은게 있나?? 같은 결과인 것 같은데

구조체 변수 하나 만들어서 변수.maxElementCount = maxElementCount???

구조체 포인터 변수 하나 만들어서 포인터 변수->maxElementCount = maxElementCount???

근데 리턴형이 ArrayList포인터형이니깐 아래것 같은데???

ArrayList의 크기만큼 동적할당한다.

구조체 포인터 변수 ->maxElementCount = maxElementCount하고

처음 생성이니깐 구조체 포인터 변수 ->currentElementCount는 0으로 하고

ArrayListNode *pElement는 maxElementCount만큼 동적할당하고 구조체 포인터 변수 리턴??

void deleteArrayList(ArrayList* pList);

pList = NULL; 하면 없어지는 것 같은데???

int isArrayListFull(ArrayList* pList);

pList의 currentElementCount랑 maxElementCount이 같으면 true 다르면 false 리턴??

int addALElement(ArrayList* pList, int position, ArrayListNode element);

isArrayListFull해서 true이면 바로 false 리턴/ false일때만 삽입 시작

position이 currentElementCount보다 크면?? 바로 false리턴

정상적인 값이면?? 맨뒤에서부터 position까지 한칸씩 이동

position에 element노드 삽입

currentElementCount늘려주기

int removeALElement(ArrayList* pList, int position);

position이 currentElementCount보다 크면?? 바로 false리턴

정상적인 값이면?? 그냥 땡기고 마지막에만 NULL해주고 currentElementCount줄이면 될거 같은데???

ArrayListNode* getALElement(ArrayList* pList, int position);

유효한 입력인지 확인하고

return (pList->pElement[position])하면 될것 같은데??

void displayArrayList(ArrayList* pList);

이게 리스트 정보를 print하라는건지 노드의 값들을 출력하라는 건지???

void clearArrayList(ArrayList* pList);

반복문으로 싹 돌면서 모든 노드 데이터 0으로 초기화

int getArrayListLength(ArrayList* pList);

currentElementCount리턴하면 될것같은디???



연결 리스트

링크드 리스트 42과제

흔히들 연결리스트를 엮은 굴비로 비유를 한다.

그렇게 데이터들을 줄줄이 엮은 리스트 형태가 링크드 리스트라고 생각하면된다.

배열은 각각의 데이터가 인접해있기 때문에 인덱스로 처리가 가능했지만 링크드 리스트는 포인터로 다음 데이터를 찾아내기 때문에 서로 인접해 있을 필요가 없다.

그렇게 때문에 연결 리스트의 데이터는 데이터 필드뿐만 아니라 다음 것을 가리키는 포인터 필드를 가져야 한다.

이 두가지를 합쳐서 노드라고 부른다. 여러가지 데이터를 합쳐서 하나의 자료형으로 만들어야 하므로 구조체로 선언한다.

그렇다면 첫 노드를 가리키고 있는 친구가 하나 있어야한다. 그것을 헤드 포인터라고 부른다.

이 포인터는 노드를 가리키는 포인터지 노드가 아니다. 그렇기 때문에 해당 노드는 어떠한 데이터도 담고 있지 않는다.

마지막 노드의 다음 노드 포인터는 NULL이어야한다.

연결 리스트의 최대 장점은 노드의 개수를 컴파일 전에 선언해줄 필요가 없다는 것이다.

포인터를 끊고 다시 연결하면 되므로 삽입과 제거가 자유롭다.

링크드 리스트의 단점은 구현이 배열방식보다 훨씬 어렵다는 것이다.

물리적인 횟수만큼의 인덱스로 검색을 하는 것이 아니라 물리적인 횟수만큼 주소를 이동해야하므로 시간이 오래걸린다.

linkedlist.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#ifndef _LINKEDLIST_
#define _LINKEDLIST_

typedef struct ListNodeType
{
	int data;
	struct ListNodeType* pLink;
} ListNode;

typedef struct LinkedListType
{
	int currentElementCount;	// 현재 저장된 원소의 개수
	ListNode headerNode;		// 헤더 노드(Header Node)
} LinkedList;

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);
#endif

#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_

#define TRUE		1
#define FALSE		0

#endif

typedef struct ListNodeType

링크드리스트의 하나의 노드는 데이터를 담고 있는 부분과 다음 노드의 주소를 가지고 있다.

data는 데이터를 담고있는 변수 pLink는 다음 노드의 주소를 가지고 있는 변수이다.

typedef struct LinkedListType

현재 저장된 원소의 개수와 헤드포인터로 전체 리스트 가리킨다.

LinkedList* createLinkedList();

헤더노드를 동적할당 해줘야하나??? 데이터를 0으로 하고 다음노드를 동적할당?? 둘다??

int addLLElement(LinkedList* pList, int position, ListNode element);

예외처리하고 element가 position위치 가리킬 때까지 이동하고 해당 노드가 element가리키고 element가 다음노드 가리키게???

int removeLLElement(LinkedList* pList, int position);

예외처리하고 position까지 이동한 다음 해당 노드가 다다음 노드 가리키게??

그러면 그 지우려는 노드는 동적해제를 해줘야하나??

ListNode* getLLElement(LinkedList* pList, int position);

예외처리하고 position까지 이동한 다음 해당노드 그대로 리턴

void clearLinkedList(LinkedList* pList);

헤드노드부터 NULL 가리킬때까지 돌면서 data 0으로 만들기

int getLinkedListLength(LinkedList* pList);

헤드노드부터 NULL 가리킬때까지 돌면서 카운트

void deleteLinkedList(LinkedList* pList);

리스트 자체를 동적해제 시켜주면 되지 않을까??

리스트 노드마다 동적해제 시켜줘야하나??



연결 리스트의 종류

단순 연결 리스트

지금까지 우리가 한거

원형 연결리스트

대형 컴퓨터에서 사용하는 운영체제를 시공유 시스템이라고 하는데 이는 한정된 CPU 자원을 여러 사람이 짧은 시간 간격을 두고 나눠 가지는 것이다.

이런 상황에서 적합한 방법이 원형 연결 리스트이다.

마지막 노드의 다음 노드 포인터가 다시 첫노드를 가리킴으로써 강강술래하듯이 모든 노드가 루프되는 형태이다.

유의할 점은 최소한 노드 하나는 헤드 포인터 역할을 해야하는 것이다.

이중 연결리스트

우리는 한 노드안에 데이터 하나와 다음 노드를 가리키는 포인터 하나를 만들기로 하고 구현을 했었다.

그렇게 구현함으로써 노드는 항상 다음 노드를 알고있지만 이전 노드는 알 수가 없다.

이중 연결리스트는 이전 노드를 가리키는 포인터를 하나더 만들어서 헤드와 테일이라는 포인터 두개를 가지게 되는 구조이다.

이렇게되면 당연히 각 노드들의 대한 접근성이 좋아진다. 그러나 추가적인 메모리 공간을 차지하게 되며 구현자가 항상 이전 노드 포인터까지 처리해야한다는 번거로움이있다.



배열과 연결 리스트의 비교

배열을 선형 자료구조(Linear Data Structure), 연결 리스트를 연결 자료구조(Linked Data Structure)라고 부른다.

선형이란 단어의 의미는 데이터가 일렬로 붙어있다이고 연결은 당연히 붙는 단어이다.

어떤 방식으로 리스트를 구현할 것인가는 해당 리스트의 용도와 특성에 따라서 결정된다.

공간적인 시각

배열은 정적인 메모리를 할당을 해준다.

즉 컴파일 동안 배열의 크기는 미리 고정되어 사용하지 않는 공간이 발생할 수도 있고 공간이 부족할 수도 있다.

반면 링크드 리스트는 서로 떨어져 있다. 이를 엮기 위해서 포인터를 사용하고, 따라서 연결 리스트는 포인터 변수에 할당되는 메모리 공간만을 필요로 한다.

공간적인 유연성이 좋다는 것이다.

따라서 메모리 공간을 많이 신경쓴다면 링크드리스트를 사용하는 것이 유리하다.

검색 시간

요소들끼리 서로 인접해 있기 때문에 배열에서는 인덱스만 알고있다면 바로 찾을수 있다.

그러나 링크드 리스트는 헤드부터 해당 위치까지 포인터를 통해 계속 따라가야한다.

그렇기 때문에 배열이 유리하다.

삽입, 제거

배열 리스트에서 삽입을 할 경우 모든 데이터들이 한칸씩 밀려나게 된다. 제거를 할 경우에도 모두 한칸씩 당겨진다.

링크드 리스트에서는 노드들의 포인터 변경을 통해 쉽게 이루어질 수 있다.

그렇기 때문에 링크드 리스트가 유리하다.