동적인 단일 연결 리스트 (Singly Linked List) - 2

이야 안녕하십니까~? 테슬라입니다...
포스팅을 쓴지 오래된것 같군요...네 오래됬군요...
음음 각설하고 드디어 동적인 단일 연결리스트 2를 쓰게됬습니다...
이번 포스팅에서는 저번에 예고한대로 노드의 삭제와 리스트의 병합에 대하여 해볼까요?
음 우선 노드의 삭제는 연결리스트에서 필요없는 데이터가 있는 리스트를 삭제하는 것입니다.
음 예를 들어 1을 삭제하려고 한다면...
그림으로 표현하자면 이런식이겠군요...

음 그림처럼 1의 노드와의 연결을 끊어버리고 앞에서 다음 노드를 가리키면,
1의 노드와의 관계는 사라지겠죠?
이후 1의 노드를 free해주면 1의 노드와는 작별하게 되는거죠~
코드로 나타내면 다음과 같습니다...
NODE *deleteNode(NODE *p,int num) { NODE *prev,*curr; curr = p; if(curr->data == num){ //삭제할 노드가 맨 처음일 때 p = p->next; free(curr); } else{ while(curr->data != num){ //삭제할 노드를 찾습니다 if(curr->next == NULL) //일치하는 노드가 없을시 변화없이 주소 리턴 return p; prev = curr; //찾을때까지 앞으로 나아갑니다 curr = curr->next; } //삭제할 노드(curr)를 찾았으므로 free하기 위해 prev의 next에 curr의 next의 주소값 할당 prev->next = curr->next; free(curr); } return p; //주소 리턴 } 음 이런식으로 표현이 가능하군요...
예를 들어 3의 노드를 삭제한다고 하면 그림으로 나타내면

이런식으로 3의 노드를 curr이 가리키고,
그 curr의 다음 노드의 주소를 curr를 가리키던 prev->next에 할당해주면
prev다음은 curr의 다음 부분을 가리키겠죠?
그럼 삭제할 노드 curr을 free해주는 것이죠...
이야, 참 쉽죠?(...)
자 그럼 다음으로 두 리스트의 결합을 생각해볼까요?
간단하게는 다른 리스트의 맨 뒤에 꼬리붙이듯이 연결 할 수도 있겠지만,
순서대로 정렬하며 넣는다면 리스트가 깔끔하겠죠?
NODE *merge(NODE *p,NODE *q) { NODE *r=NULL,*temp; //둘 중 하나가 NULL이면 NULL이 아닌값이 결과 리스트 if(p == NULL) r=q; else if(q == NULL) r=p; //맨 처음 노드 찾기 else{ //p->data가 q->data보다 작은 경우 if(p->data < q->data){ r = p; temp = p; p = p->next; temp->next = NULL; } //p->data와 q->data가 같은 경우 else if(p->data == q->data){ r = p; temp = p; p = p->next; q = q->next; temp->next = NULL; } //q->data가 p->data보다 작은 경우 else{ r = q; temp = q; q = q->next; temp->next = NULL; } //둘 중 NULL이 나오기 전까지 루프 while((p != NULL) && (q != NULL)){ if(p->data < q->data){ temp->next = p; p = p->next; temp = temp->next; temp->next = NULL; } else if(p->data == q->data){ temp->next = p; p = p->next; q = q->next; temp = temp->next; temp->next = NULL; } else{ temp->next = q; q = q->next; temp = temp->next; temp->next = NULL; } } //둘 중 NULL이 아닌 리스트가 있으면 남은 노드들은 뒤에 연결 if(p != NULL) temp->next = p; if(q != NULL) temp->next = q; } return r; } 길군요...
이 코드는 차례대로 두 노드를 비교해서 작은 값의 노드는 먼저 연결하고,
작은 부분의 노드의 다음 노드와 남아있던 노드를 다시 비교하는 형태입니다.
마지막에는 이 종합된 리스트의 맨 처음 노드의 주소인 r을 리턴하며 함수가 종료됩니다.
이런식으로 구현하면 순서대로 각 리스트의 노드들이 하나의 리스트로 연결이 되겠죠?
아 같은 값의 노드들은 하나만 연결하고 둘의 다음 노드를 가리킴으로써 중복되는 노드를 하나만 연결했습니다...
어때요? 참쉽..(히익, 죄송합니다...)
음...음...이렇게 아직도 어설픈 두번째 포스팅도 이렇게 끝이 났는데요...
다음 포스팅에는 지금까지의 응용으로 동적인 단일 연결 리스트를 이용한 스택과 큐를 다루겠습니다...
그럼 길고 산만한 포스팅을 읽어주신 여러분께 인사드리며 다음 이 시간에 다시 뵙겠습니다...