기본 자료 구조; 리스트의 구현

○ 리스트  ADT

add_last(list,item) :: = 리스트의 맨끝에 원소를 삽입한다. (insert())

add_first(list,item) :: = 리스트의 처음에 원소를 삽입한다.

add(list,pos,item) :: = pos 위치에 원소를 삽입한다.

delete(list, pos) :: = pos 위치의 원소를 제거한다.

delete(list,item) :: = 리스트에서 원소 item을 제거한다.

clear(list) :: = 리스트의 모든 원소를 제거한다. (erase())

is_in_list(list,item) :: = item이 리스트 안에 있는지 검사한다. (member())

get_entry(list,pos) :: = pos 위치의 원소를 반환한다. (return())

get_length(list) :: = 리스트의 길이를 구한다.

is_empty(list) :: = 리스트가 비었는지 검사한다.

is_full(list) :: = 리스트가 꽉 찼는지 검사한다.

visit(list) :: = 리스트의 모든 원소를 방문/출력한다. (display(), print())

 

 

○ 구현 방법

- 배열

: 1차원 배열에 항목들을 순서대로 저장한다. 삽입, 삭제 연산시  오버헤드(항목 이동)가 발생하며, 항목의 개수가 제한된다. 임의 접근(random access)이 가능하고, 구현이 간단하다.

 

 

· 리스트 생성 및 리스트 상태 점검 함수

: ArrayListType 구조체 구현, init(), is_empty(), is_full() 함수 구현.

//ArrayListType 구현
typedef int element;
typedef struct{
	element list[MAX_LIST_SIZE];	//배열 정의
	int length;		//현재 배열에 저장된 원소들의 개수
} ArrayListType;

//리스트 초기화
void init(ArrayListType *L){
	L->length = 0;
}

//리스트가 비어있으면 1, 비어있지 않으면 0 반환
int is_empty(ArrayListType *L){
	return L->length == 0;
}

//리스트가 포화상태면 1, 그렇지 않으면 0 반환
int is_full(ArrayListType *L){
	return L->length == MAX_LIST_SIZE;
}

 

· 리스트 원소 관리 함수

: add(), delete() 함수 구현

//삽입연산
void add(ArrayListType *L, int position, element item){
	if(!is_full(L) && (position>=0) && (position<=L->length){ //삽입 위치가 적합한 범위에 있는지
		int i;
		for(i=(L->length-1); i>=position; i--)	//항목 이동
			L->list[i+1] = L->list[i];
		L->list[position] = item;
		L->length++;
	}
}


//삭제연산
element delete(ArrayListType *L, int position){
	int i;
	element item;

	if(position<0 || position>=L->length)	//삭제 위치가 유효하지 않은 경우
		error("위치 오류");
        
	item = L->list[problem];
    
	for(i=position; i<(L->length-1); i++)	//항목 이동
		L->list[i] = L->list[i+1];
	L->length--;
    
	return item;
}

 

 

- 연결리스트

: 리스트의 원소들을 노드의 데이터 필드에 저장하고, 각 노드의 링크 필드에 다음 원소가 저장되어 있는 노드를 가리키는 주소도 같이 저장한다. 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요하지 않고, 배열에 비해 크기 제한이 자유롭다. 그러나 배열에 비해 구현이 다소 어렵고, 오류가 발생하기 쉽다는 단점이 있다. 임의 접근이 아닌, 순차 접근 방식(sequential access)이다.

 

 

· 리스트 생성 및 리스트 상태 점검 함수

: ListNode와 ListType 구조체 구현, is_empty(), get_length(), is_in_list() 함수 구현.

//ListNode 구현
typedef int element;
typedef struct ListNode{
    element data;
    struct ListNode *link;
} ListNode;

//ListType 구현
typedef struct{
    ListNode *head;
    int length;
} ListType;

//리스트가 비어있는지 검사
int is_empty(ListType *list)
{
    if( list->head == NULL ) return 1;
    else return 0;
}

//리스트 항목 개수 반환
int get_length(ListType *list)
{
    return list->length;
}

//데이터 값이 s인 노드가 존재하는지 확인
int is_in_list(ListType *list, element item)
{
    ListNode *p;
    p = list->head;
    while( p != NULL ){
        if( p->data == item )
            break;
        p = p->link;
    }
    if( p == NULL ) return FALSE;
    else return TRUE;
}

 

· 리스트 원소 관리 함수

: add(), delete() 함수 구현. 연결리스트 함수 insert_node()와 remove_node()를 이용.

//항목의 위치를 노드 포인터로 변환해주는 함수
ListNode *get_node_at(ListType *list, int pos)
{
    int i;
    ListNode *tmp_node = list->head;
    if( pos < 0 ) return NULL;
    for( i=0; i<pos; i++ )
        tmp_node = tmp_node->link;
    return tmp_node;
}

//주어진 위치에 데이터 삽입
void add(ListType *list, int pos, element data)
{
    ListNode *p;
    if ((pos >= 0)&&(pos <= list->length)){
        ListNode *node = (ListNode*)malloc(sizeof(ListNode));
        if( node == NULL ) error("메모리 할당 에러");
        node->data = data;
        p = get_node_at(list, pos-1);
        insert_node(&(list->head), p, node);
        list->length++;
    }
}

//리스트 처음에 데이터 삽입
void add_first(ListType *list, element data)
{
    add(list, 0, data);
}

//리스트 맨 뒤에 데이터 삽입
void add_last(ListType *list, element data)
{
    add(list, get_length(list), data);
}


//주어진 위치의 데이터 삭제
void delete(ListType *list, int pos)
{
    if(!is_empty(list) && (pos >= 0) && (pos < list->length)){
        ListNode *p = get_node_at(list, pos-1);
        ListNode *removed = get_node_at(list, pos);
        remove_node(&(list->head), p, removed);
        list->length--;
    }
}

 

· 리스트 출력 함수

: get_entry(), visit() 함수 구현.

//해당 위치의 데이터를 반환
element get_entry(ListType *list, int pos)
{
    ListNode *p;
    if( pos >= list->length ) error("위치 오류");
    p = get_node_at(list, pos);
    return p->data;
}


//리스트의 각 노드를 방문해 데이터를 출력
void visit(ListType *list)
{
    int i;
    ListNode *node = list->head;
    printf("(");
    for(i=0; i<list->length; i++){
        printf("%d ",node->data);
        node = node->link;
    }
    printf("\n");
}