[C] 자료구조 - 연결리스트

빈 리스트, 길이, 초기화 연산 구현

빈 리스트

int is_empty(ListType *list){
	if(list->head == NULL)
    	return 1;
    else
    	return 0;
}

길이

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

초기화

void init(ListType *list){
	if(list == NULL)
    	return;
    list->length = 0;
    list->head = NULL;
}

삽입 연산 코드

// phead : 리스트의 헤더 포인터의 포인터
// p : 선행노드
// new_node : 삽입될 노드
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node){
	if( *phead == NULL){ // 공백 리스트
    	*phead = new_node;
    }
    else if( p == NULL){
    	new_node->link = *phead;
        *phead = new_node;
    }
    else{
    	new_node->link = p->link;
        p->link = new_node;
    }
}

add 연산

• 새로운 데이터를 임의의 위치에 삽입
• get_node_at()가 지정된 위치의 노드 주소를 반환하면, 이 값을 이용

// 주어진 위치에 데이터를 삽입
void add(ListType *list, int position, element data){
	ListNode *p;
    if ((position >= 0) && (position <= list->length)){
    	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
        
        node->data = data;
        node->link = NULL;
        p = get_node_at(list, position-1);
        insert_node(&(list->head), p, node);
        list->length++;
    }
}

• 새로운 데이터를 임의의 위치에 삽입
• 항목의 위치를 노드 포인터로 변환해주는 함수 get_node_at 필요

// 리스트 안에서 pos 위치의 노드를 반환
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;
}

delete 연산

• 임의의 위치의 데이터 삭제
• 항목의 위치를 노드 포인터로 변환해주는 함수 get_node_at 필요

// 주어진 위치의 데이터를 삭제
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--;
    }
}

삭제 연산

// phead : 헤드 포인터에 대한 포인터
// p : 삭제될 노드의 선행 노드
// removed : 삭제될 노드
void remove_node(ListNode **phead, ListNode *p, ListNode *removed){
	if( p == NULL )
    	*phead = removed->link; // *phead = (*phead)->link;
    else
    	p->link = removed->link;
    free(removed);
}

get_entry 연산

// 주어진 위치에 해당하는 데이터 반환
element get_entry(ListType *list, int pos){
	ListNode *p;
    if( pos < 0 || pos >= list->length)
    	printf("위치 오류");
    p = get_node_at(list, pos);
    return p->data;
}

display 연산

// 버퍼의 내용을 출력
void display(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");
}

is_in_list 연산

// 데이터 값이 s인 노드 찾기
int is_in_list(ListType *list, element item){
	ListNode *p;
    p = list->head; // 헤드 포인터부터 시작
    while((p != NULL)){
    	// 노드 데이터가 item인 경우
        if( p->data == item)
        	break;
        p = p->link;
    }
    if( p == NULL)
    	return fALSE;
    else
    	return TRUE;
}