열혈 자료구조 - 3-2. 배열을 이용한 리스트의 구현(1)

리스트의 이해

- 구분

    -> 순차 리스트 : 배열을 기반으로 구현된 리스트 

    -> 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

    -> 리스트의 기본 기능은 같으나 성격, 성능은 다를 수 있음

- 특징 : 데이터를 나란히(하나의 열로) 저장하고 중복을 허용

- 이러한 특징을 만족하기 위해 배열, 메모리 동작 할당의 구현 방법을 사용

 

리스트 자료구조의 ADT

- 순차 리스트, 연결 리스트간 ADT는 달라지지 않음

- 리스트의 특징만 만족하면 기능을 추가하거나 뺄 수 있음

- 초기화 : 초기화될 리스트를 인자로 전달하고 리스트 생성 후 가장 먼저 호출되어야 함

void ListInit(List* plist);

- 데이터 저장 : 리스트에 데이터를 저장

void LInsert(List* plist, LData data);

- 저장된 데이터의 탐색 및 탐색 초기화 : 저장된 데이터 중에서 첫번째 데이터를 반환받음. 반환 값은 성공 여부

int LFirst(List* plist, LData* pdata);

- 다음 데이터의 참조(반환) : LFirst 이후의 데이터를 반환받을 때 사용. LFirst -> LNext -> LNext ...

    -> LFirst, LNext를 구분한 이유 : 데이터를 참조할 때 처음부터 참조하겠다라는 것을 명시적으로 해주기 위해

int LNext(List* plist, LData* pdata);

- 바로 이전에 참조(반환)한 데이터를 삭제 : LFirst, LNext 함수의 마지막 반환 데이터를 삭제

LData LRemove(List* plist);

- 현재 저장되어 있는 데이터의 수를 반환

int LCount(List* plist);

int main(void)
{
	int data;
	List list;			// 리스트 생성
	ListInit(&list);	// 초기화(필수)

	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);
	}

	/*** 숫자 22을 탐색하여 모두 삭제 ***/
	if(LFirst(&list, &data))
	{
		if(data == 22)
			LRemove(&list);
		
		while(LNext(&list, &data))
		{
			if(data == 22)
				LRemove(&list);
		}
	}

	return 0;
}

데이터가 나란히 저장된 모습