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

목표: ADT를 근거로 리스트를 구현해보자.

 

리스트의 종류(자료구조의 구현방법에 따른 분류)

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

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

위의 ADT는 각각의 특성적 차이 때문에 차이를 두기도 하지만 동일할 수도 있다.  

정의하는 자의 필요에 따라서, 확장이 가능하기 때문에 ADT에 차이가 난다.

 

리스트 자료구조의 가장 기본적이고 중요한 특성

데이터를 나란히 저장하고 중복된 데이터의 저장을 막지 않는다.

 

리스트 자료구조의 ADT

Operations(연산, 함수, 명령...): void ListInit(List * plist); -초기화할 리스트의 주소 값을 인자로 전달한다. -리스트 생성 후 제일 먼저 호출되어야 하는 함수이다. void LInsert(List * plist, LData data); -리스트에 데이터를 저장한다. 매개변수 data에 전달된 값을 저장한다. int LFisrt(List * plist, LData pdata); -첫 번째 데이터가 pdata가 가리키는 메모리에 저장된다. -데이터의 참조를 위한 초기화가 진행된다. -참조 성공시 TRUE, 실패시 FALSE 반환 int LNext(List * plist, LData data); -참조된 데이터의 다음 데이터가 pdata가 가리키는 메모리에 저장된다. -순차적인 참조를 위해서 반복 호출이 가능하다. -참조를 새로 시작하려면 먼저 LFirst 함수를 호출해야 한다. -참조 성공 시 TRUE, 실패 시 FALSE 반환 LData LRemove(List * plist); -LFirst 또는 LNext 함수의 마지막 반환 데이터를 삭제한다. -삭제한 데이터는 반환된다. -마지막 반환 데이터를 삭제하므로 연이은 반복 호출을 허용하지 않는다. int LCount(List * plist); -리스트에 저장되어 있는 데이터의 수를 반환한다.

위의 정보만 가지고는 리스트의 활용방법을 정확히 알지 못하지만, 리스트 자료구조가 제공하는 기능을 어느정도 예측은 할 수 있어야 한다. 정확한 활용방법을 알기 위해서는 헤더파일과 위의 함수들을 호출하는 main 함수를 보아야 한다.

 

아래의 main 함수를 보면서 어떤 라이브러리에 포함되어 있는 리스트의 사용방법을 파악하는 상황이라고 가정하자.

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

int main(void){
	
    //ArrayList의 생성 및 초기화
    List list; //리스트의 생성, List 기반 변수 list 선언(이하 리스트)
    int data;
    ListInit(&list); //리스트의 초기화
    /*
    리스트의 생성 및 초기화
    모든 자료구조는 내부적으로 다양한 정보를 담게 됨.
    이때 데이터 뿐만 아니라 데이터를 효율적으로 저장 및 참조하기 위한 정보들도 담기게 된다.
    따라서 이와 관련된 변수들의 초기화가 선행되어야 하며 이를 담당하는 함수가 ListInit이다.
    */
    
    //5개의 데이터 저장
    LInsert(&list, 11); LInsert(&list, 11); //리스트에 11을 총 2회 저장
    LInsert(&list, 22); LInsert(&list, 22); //리스트에 22를 총 2회 저장
    LInsert(&list, 33); //리스트에 33을 저장
    /*
    데이터의 저장방법
    LInsert(리스트의 주소 값, 리스트에 담을 데이터)
    위와 같은 형태의 LInsert 함수로 데이터를 저장한다.
    */
    
    //저장된 데이터의 전체 출력
    printf("현재 데이터의 수: %d \n", LCount(&list));
    
    if(LFirst(&list, &data)){ //첫 번째 데이터를 변수 data에 저장
    	printf("%d ", data);
        while(LNext(&list, &data)) //두 번째 데이터를 변수 data에 저장
        	printf("%d ", data);
    }
    printf("\n\n");
    /*
    데이터의 참조 방식
    보통 데이터의 저장보다 참조가 더 복잡하다.
    저장된 순서대로 데이터를 참조하여 출력을 진행하되, 마지막 데이터까지 참조하여 출력을 진행하고 있다.
    리스트 ADT에서는 다음과 같이 언급을 하였다.
    "순서대로 참조하려면 먼저 LFirst를 호출해서 첫 번째 데이터를 얻으세요.
    그리고 두 번째 이후의 데이터는 LNext를 호출해서 얻으시면 됩니다.
    그리고 LFirst 함수와 LNext 함순느 더 이상 참조할 데이터가 없으면 FALSE를 반환합니다."
    
    왜 굳이 LFirst의 호출을 요구하는 것인가?
    리스트 내에서 데이터의 참조위치를 기록하기 때문에
    LNext 함수를 호출할 때마다 다음에 저장된 데이터를 얻을 수 있다.
    처음부터 참조를 새롭게 시작하기 위해서는 참조위치에 대한 정보를 초기화 해야하기 때문에
    LFirst 함수의 호출을 요구하는 것이다.
    
    LFirst → LNext → LNext → LNext → LNext ...
    */
    
    //숫자 22을 탐색하여 모두 삭제
    if(LFirst(&list, &data)){ 
    	if(data == 22)
        	LRemove(&list); //위의 LFirst 함수를 통해 참조한 데이터 삭제
        while(LNext(&list, &Data)){
        	if(data == 22)
            	LRemove(&list); //위의 LNext 함수를 통해 참조한 데이터 삭제
        }
    }
    /*
    데이터의 삭제
    삭제관련 코드는 탐색관련 코드와 관련이 깊다. 삭제를 위해서는 탐색이 선행되어야 하기 때문
    LRemove 함수가 호출되면, 바로 직전에 LFirst 또는 LNext 함수의 호출을 통해서 참조된 데이터가 삭제됨.
    */
    
    //삭제 후 남은 데이터 전체 출력
    printf("현재 데이터의 수: %d \n", LCount(&list));
    
    if(LFirst(&list, &data)){
    	printf("%d ", data);
        while(LNext(&list, &data))
        	printf("%d ", data);
    }
    printf("\n\n");
    return 0;
}
    

현재 데이터의 수: 5 11 11 22 22 33 현재 데이터의 수: 3 11 11 33

참고로, 실제로 위의 코드를 실행하려면 아래 파일들을 전부 한 프로젝트에 넣고 컴파일 해야 한다. 원래 안돌아가는게 맞음!

ArrayList.h  리스트 자료구조의 헤더파일 

ArrayList.c  리스트 자료구조의 소스파일

ListMain.c  리스트 관련 main 함수가 담긴 소스 파일(위의 코드)

 

본 글은 윤성우의 열혈 자료구조를 읽으며 개인 공부 용으로 작성되었음을 밝힙니다.

book.naver.com/bookdb/book_detail.nhn?bid=6809127

윤성우의 열혈 자료구조