(C언어) 연결 리스트(2)(삽입, 삭제 연산) [자료구조]

지난번에 연결 리스트에서 노드의 기본적인 것들을 알아보았다.

(C언어) 연결 리스트(1) [자료구조]

(C언어) 연결 리스트(1) [자료구조]

이전에 배웠던 것을 활용해서 연결 리스트에서 삽입과 삭제 연산을 구현해보자.

---

 

##삽입 연산

삽입 연산은 노드의 연결을 이용해 구현할 수 있다. 삽입연산은 리스트의 첫 부분에 새로운 노드를 추가하는 연산과, 리스트의 중간에 새로운 노드를 추가하는 연산을 구현해보겠다. 결국 같은 원리이지만 선행 노드 변수의 유무로 인해 코드상 약간의 차이가 생긴다.

 

1) 첫 부분에 추가하는 경우

위 그림처럼 특정 리스트가 있고 추가할 새로운 노드가 있는 상황이 있다고 가정해보겠다. 노드 C를 리스트 맨 앞에 넣기 위해서는 어떻게 해야 할까?? 먼저 동적 메모리 할당으로 C에 해당하는 노드를 생성한 뒤 C의 링크부분이 A를 향하게 한뒤 헤드 포인터가 C를 향하게 하면 된다. 그림으로 천천히 보자.

먼저 동적 메모리 할당을 통해 새로운 노드 P 생성, 생성한 노드의 데이터값에 C 삽입

 

p->link를 현재 head의 값으로 변경

Head의 값을 p로 변경

ListNode* insert_first(ListNode *head,int value)
{
	ListNode *p = (ListNode *)malloc(sizeof(ListNode)); //p의 노드 생성
	p->data = value; // p의 data는 추가할 값
	p->link = head;  // p의 링크는 헤드포인터가 가리키는 노드를 가리킴
	head = p; // 헤드포인터는 이제 p를 가리킴
	return head; 
}

 

2) 중간에 추가하는 경우

이전에도 말했듯이 중간에 추가하는 경우도 처음에 추가하는 경우와 방법은 같다. 단지 변수 하나가 추가되었을 뿐이다. 왜냐하면 중간에 삽입하기 위해서는 중간의 위치가 어디인지 알아야 하기 때문에, 삽입할 위치 이전의 노드(선행 노드) 변수가 추가된 것이다. 동적 메모리 할당으로 노드를 생성한 후에 값을 넣어주고 링크 부분은 선행 노드가 가리키는 노드를 향하게 해 준다. 그리고 선행 노드의 링크 부분이 삽입한 노드를 향하게 해 주면 해결된다. 방법은 이전과 같으므로 그림으로 간단히 보겠다.

Pre: 선행노드

삽입할 위치의 이전 노드, 즉 선행 노드를 가리키는 포인터 Pre이다. C의 값을 가진 P 노드를 동적으로 생성하고 삽입 위치에 넣어보자.

전체적인 과정을 한 그림에 표현해 보았다. 쉽게 이해가 될 것이다.

ListNode* insert(ListNode *head,ListNode *pre,int value)
{
	ListNode *p = (ListNode *)malloc(sizeof(ListNode)); // 삽입할 노드 동적 생성
	p->data = value; // 삽입할 노드 값 입력
	p->link = pre->link; // 선행노드가 가리키는 노드를 향함
	pre->link=p; // 선행노드가 추가한 노드 P를 가리킴
	return head;
}

이렇게 삽입 연산을 구현해 보았다. 배열로 구현한 순차 리스트와 다르게 연결 리스트는 삽입이나 삭제를 할 때마다 다른 노드들의 이동이 필요 없다는 장점을 몸소 느낄 수 있다.

---

## 삭제 연산

삭제 연산도 첫 번째 노드를 삭제하는 경우와 중간에 있는 노드를 삭제하는 경우, 2가지로 나누어서 생각해보도록 하겠다. 삽입 연산과 마찬가지로 두 경우 모두 원리는 같지만 선행 노드 변수 유무의 차이이다. 

 

1) 첫 번째 노드를 삭제하는 경우

 

위 그림에서 A 노드를 삭제하려고 한다. 어떻게 해야 할까? 첫 번째 노드의 완벽한 삭제를 위해 removed라는 노드를 임시 생성한다. 헤드 포인터의 값을 removed에 복사한다. 그리고 헤드 포인터의 값을 첫 번째 노드가 가리키는 노드(즉 두 번째 노드)로 변경해준다. 그리고 removed를 동적 메모리를 반환함으로써 완벽히 첫 번째 노드를 삭제한다.

헤드 포인터의 값을 두 번째 노드(removed->link) 로 변경

removed 동적 메모리 반환

ListNode* delete_first(ListNode *head)
{
	ListNode *removed; // 삭제를 위한 임시 노드 생성
	if(head==NULL) return NULL; // 연결 리스트가 비어있다면 NULL 반환
	removed = head; // removed에 헤드 포인터의 값 복사
	head = removed->link; // 헤드 포인터는 첫 번째 노드가 가리키는 노드(두 번째 노드)를 가리킴
	free(removed); // removed 동적 메모리 반환
	return head;
}

 

2) 중간 노드 삭제하는 경우

중간에 삭제하기 위해서는 삽입 연산과 마찬가지로 삭제 위치를 알기 위한 선행 노드 변수가 필요하다. 이후 방법은 첫 번째 노드 삭제와 같다. removed 노드를 임시로 생성한 후 삭제할 노드를 복사해준다. 그리고 선행 노드를 삭제할 노드의 다음 노드로 연결해주고 removed를 동적 메모리 반납을 하면 된다.

노드 C 삭제

B노드의 링크 필드가 D 노드를 가리키게 함

removed(노드 C) 동적 메모리 반환

ListNode* delete(ListNode *head, ListNode *pre)
{
	ListNode *removed; 
	removed = pre->link; // 삭제할 노드 복사
	pre->link = removed->link; // 선행노드와 삭제할 노드의 다음노드와 연결
	free(removed); // 삭제할 노드 메모리 반환
	return head;
}

---

이렇게 연결 리스트의 삽입, 삭제 연산을 알아보았다. 이 내용은 앞으로 많은 자료구조 형태에서 사용함으로 반드시 알고 있어야만 하는 부분이다. 이 연산들을 활용해서 직접 삽입, 삭제를 테스트해보면 도움이 많이 될 것이다. 마지막으로 테스트를 위한 출력 함수만 다루도록 하겠다.

void print_list(ListNode *head)
{
	for(ListNode *p= head;p!=NULL;p=p->link) // head 노드 부터 p가 NULL 이 나올때까지 p=p->link를 통해 옆으로 이동
		printf("%d->",p->data); // 각 노드의 값 출력
	printf("NULL\n");
}