연결리스트 - 함수들 정리

※ 인프런 강의 "C로 배우는 자료구조 및 여러가지 예제실습(권오흠 교수님)"를 보고 개인적인 복습을 위해 정리한 내용입니다.

 

 

void add ( int index, ...)

 

연결리스트의 index 번째 위치에 새로운 노드를 만들어서 삽입한다.

 

int add(int index, char *item) {
 	if (index < 0)
 		return 0;
    
 	if (index == 0) {        /* 맨 앞에 삽입하는 경우 */
 		add_first(item);
 		return 1;
 	}
    
 Node *prev = get_node(index - 1);     /* 그 이외의 경우 */
 if (prev != NULL) {      
 	add_after(prev, item);
 	return 1;
 }
 return 0;
}

 

삽입에 실패하면 0을, 성공하면 1을 반환하도록 한다.

여기서 삽입함수는 맨 앞에 삽입하는 경우와 그 이외에 삽입하는 경우로 나눌 수 있는데, 두번째 경우는 이전 노드의 주소가 필요하다.

 

 

 

 

 

 

char *remove ( int index, …)

 

index번째 노드를 삭제하고, 그 노드에 저장된 데이터를 반환한다.

 

Node *remove(int index) {
 	if (index < 0) {
 		return NULL;
 	}
 	if (index==0) {       /* 첫번째 노드 삭제 */
 		return remove_first();
 	}
 
 Node *prev = get_node(index-1);    /* 그 이외의 삭제하는 경우 */
 	if (prev==NULL)      /* 삭제할 노드가 존재하지 않음 */
 		return NULL;
 	else {
 		return remove_after(prev);
 		}
}

 

 

 

 

 

char *remove( char *item )

 

입력된 스트링을 저장한 노드를 찾아 삭제한다. 삭제된 노드에 저장된 스트링을 반환한다.

 

Node *remove(char * item) {
 	Node *p = head;
 	Node *q = NULL;
    
 	while (p!=NULL && strcmp(p->data, item)!=0) {
 		q = p;
 		p=p->next;
 }
 	if (p==NULL)
 		return NULL;
    
 	if (q==NULL)        /* 삭제할 노드가 첫번째 노드 */
 		return remove_first();
 	else
 		return remove_after(q);     /* q 다음 노드를 삭제 */
}

 

두 개의 포인터가 필요하며, q는 항상 p의 직전 노드를 가리킨다.

p가 첫번째 노드일 경우 q는 NULL이다.

 

 

 

 

 

void add_to_ordered_list ( char * item )

 

연결리스트에 데이터들이 오름차순으로 정렬되어 있다는 가정 하에서 새로운 데이터를 삽입한다.

 

void add_to_ordered_list(char *item) {
 	Node *p = head;
 	Node *q = NULL;
 	while (p!=null && strcmp(p->data, item)<=0) {
 		q = p;
 		p=p->next;
 }
 	if (q==NULL)
 		add_first(item);
 	else
 		add_after(q);
}

 

strcmp 함수

(1) str1 < str2 인 경우에는 음수 반환

(2) str1 > str2 인 경우에는 양수 반환

(3) str1 == str2 인 경우에는 0을 반환 합니다.