리스트 List(배열 기반)

 

 

 

으래 그냥 리스트라고 하면 연결 리스트를 종종 떠올린다.

하지만, 리스트에는 순차 리스트와 연결 리스트가 있다.

 

순차 리스트는 배열을 기반으로 구현된 리스트이며

연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트이다.

 

 

하지만 이는 리스트의 구현방법의 차이에서 비롯된 것이기 때문에

이 둘의 ADT가 동일하다고 해서 문제가 될 것은 없다.

물론 각각의 특성의 차이 때문에 ADT에 차이를 두기도 한다.

 

이는 ADT는 각종 자료구조들의 표준이 아니기 때문이다.

 

정의하는 사람이나 회사에 따라서, 다시 말해 피룡에 따라서 ADT에도 차이가 난다.

물론 필요에 따라 확장도 가능하다. 

하지만 그렇다고 해서 해당 자료구조의 기본 특성을 무시하는 형태로 ADT가 정의되는 것은 아니다.

 

리스트 ADT 정의를 위해서 리스트 자료구조의 가장 기본적이고 중요한 특성을 소개하자면

 

"리스트 자료구조는 데이터를 나란히 저장한다. 그리고 중복된 데이터의 저장을 막지 않는다."

 

 

자료구조 중에서는 중복된 데이터의 저장을 허용하지 않는 경우도 있다.

하지만 리스트는 이를 허용하며 수학적으로 중복을 허용하지 않는 '집합'과는 다른 개념이다.

그리고 이것이 리스트 ADT를 정의 하는데 있어서 고려해야 할 유일한 요소이다.

 

 

리스트의 ADT

 

리스트의 특성을 소개하였으니 이를 가지고 ADT를 정의해 보자.

다시 말해서 리스트 자료구조가 제공해야 할 기능들을 나열하면 된다.

 

 

 

위에서 보이듯, 이후에 구현할 자료구조들과의 이름충돌을 막기 위해서

리스트를 의미하는 L을 접두사로 하여 함수의 이름을 정의하였다.

 

 

리스트의 ADT를 기반으로 정의된 main 함수

 

리스트의 ADT를 정의하였으니, 이를 기반으로 main 함수를 만들 차례이다.

아래에서 제시하는 main 함수를 기반으로 리스트 ADT에서 소개하는 함수들의 기능을

완전히 이해하기로 하자.

아래의 main 함수를 보면서,

어떤 라이브러리에 포함되어 있는 리스트의 사용방법을 파악하는 상황이라고 

생각하기를 바라며, 그 어떤 라이브러리가 C의 표준함수라고 가정해도 괜찮다.

 

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

int main(void)
{

	// ArrayList 의 생성 및 초기화

	List list;
	int data;
	ListInit(&list);

	// 5개의 데이터 저장 
	LInsert(&list, 11); LInsert(&list, 11);
	LInsert(&list, 22); LInsert(&list, 22);
	LInsert(&list, 33);

	// 저장된 데이터의 전체 출력
	printf("현재 데이터의 수 : %d \n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d", data);

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

	// 숫자 22을 탐색하여 모두 삭제

	if (LFirst(&list, &data))
	{
		if (data == 22)
			LRemove(&list);

		while (LNext(&list, &data))
		{
			if (data == 22)
				LRemove(&list);
		}
	}

	// 삭제 후 남은 데이터 전체 출력
	printf("현재 데이터의 수 : %d \n", LCount(&list));

	if (LFirst(&list, &data))
	{
		printf("%d", data);

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


	return 0;
}

 

 

배열 기반 리스트의 단점

- 배열의 길이가 초기에 결정되어야 한다. 변경이 불가능하다.

- 삭제의 과정에서 데이터의 이동(복사)가 매우 빈번히 일어난다.

 

배열 기반 리스트의 장점

- 데이터의 참조가 쉽다.
인덱스 값을 기준으로 어디든 한 번에 참조가 가능하다.