[DS/자료구조] 리스트 - 배열 리스트와 연결 리스트

배열 리스트와 연결 리스트

 

리스트(List)

리스트는 자료를 순서대로 저장하는 자료구조이다. 리스트를 구현하는 방법에는 배열을 이용하거나 포인터를 이용하여 리스트를 구현할 수 있다. 기본적인 기능으로는 리스트 생성, 원소 추가, 원소 반환, 원소 제거(리스트 초기화), 리스트 삭제로 볼 수 있다. C언어의 경우 리스트를 지원하지 않는 대신 배열을 지원한다. 즉, 리스트를 사용하려면 직접 만들거나 라이브러리를 사용해야 한다. 

- 리스트의 대표 기능

• 엘리먼트를 추가/삭제하는 기능
• 리스트에 데이터가 있는지 체크하는 기능
• 모든 데이터에 접근할 수 있는 기능

 

배열 리스트(ArrayList)

배열은 인덱스와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다. 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되며, 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다. 연결 리스트보다 탐색의 시간 복잡도(O(1))가 좋고 구현이 간단하지만 삽입이나 삭제 시 데이터를 옮겨주는 작업이 필요하므로 시간 복잡도(O(N))가 좋지 않다.

위키백과 배열 사진

- 배열 리스트의 구현

• 구조체

typedef struct ArrayListNodeType
{
	int data;
} ArrayListNode;

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

• 배열 리스트의 생성

ArrayList* createArrayList(int maxElementCount);

• 원소 추가

내부적으로 데이터를 배열에 저장한다. 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면, 이후의 데이터들이 한 칸씩 뒤로 물러나야 한다.

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

• 원소 제거

삭제도 추가와 유사하게 빈자리가 생기면 빈자리를 채우기 위해서 순차적으로 한 칸씩 당겨야 한다.

void deleteArrayList(ArrayList* pList);
int removeALElement(ArrayList* pList, int position);
void clearArrayList(ArrayList* pList);

• 기타

int isArrayListFull(ArrayList* pList);					// 꽉 찼는지 검사
ArrayListNode* getALElement(ArrayList* pList, int position);		// position의 요소를 반환
void displayArrayList(ArrayList* pList);				// 모든 요소를 출력
int getArrayListLength(ArrayList* pList);				// 길이를 반환

 

배열 리스트의 특징

• 고정된 크기를 갖는 같은 자료형의 원소들이 연속적인 형태로 구성된 자료 구조이다.
• 배열의 공백을 허락하지 않는다. 
• 논리적 순서와 물리적 순서가 동일하다.
• 빠르게 탐색(조회)할 수 있다.

 

연결 리스트(LinkedList)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제 시간 복잡도(O(1))가 좋다. 하지만 특정 위치의 데이터를 탐색할 때 시간 복잡도(O(N))는 좋지 않다.

위키백과 연결 리스트 사진

- 단일 연결 리스트

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

- 이중 연결 리스트

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

- 원형 연결 리스트

원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

위키백과 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 사진

- 연결 리스트의 구현

• 구조체

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);
void clearLinkedList(LinkedList* pList);
void deleteLinkedList(LinkedList* pList);

• 기타

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

 

연결 리스트의 특징

• 빈틈없이 데이터가 연속적으로 위치한다.
• 필요할 때마다 동적 메모리 생성 이용하여 노드를 생성한다.
• 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트 등이 있다.

 

배열 리스트와 연결 리스트의 장점과 단점

	배열 리스트	연결 리스트
장점	- 내부적으로 배열을 사용하기 때문에 인덱스를 이용해서 접근하는 것이 빠르다.	- 동적으로 메모리 사용이 가능하다. - 최대 원소 개수 지정이 불필요하다. - 추가시 원소를 이동하는 연산이 불필요하다. - 대용량 데이터 처리에 적합하다.
단점	- 배열 내의 데이터 이동 및 재구성이 어렵다. - 동적으로 사용하기 힘들다.	- 구현이 어렵다. - 탐색 연산의 시간복잡도(O(N))가 좋지않다. - 메모리를 추가적으로 사용해야한다. - 논리적 순서와 물리적 저장 순서가 일치하지 않는다.

 

배열 리스트와 연결 리스트의 차이점

배열 리스트와 연결 리스트는 선형 자료 구조이다. 배열 리스트는 최대 저장 개수가 정해진 반면 연결 리스트는 동적 할당을 이용하기 때문에 최대 저장 개수에 제한이 없다. 연결 리스트의 경우 원소를 제거하더라도 앞 뒤 자료 사이 포인터만 재설정하면 돼서 간편한 것 같지만 코드 구현이 어렵다. 실제로 구현해봤을 때 데이터에 접근하는 방법에 따라 값이 다르게 나오기도 했다.