연결 리스트(Linked List)는 동적 메모리 할당(dynamic memory allocation)을 사용하는 자료구조로, 필요에 따라 크기가 늘어나거나 줄어듭니다. 즉, 여러 개의 노드(Node)가 모여 이루어진 집합이라고 할 수 있습니다.
노드는 두 가지 부분으로 구성됩니다.
- 데이터(Data): 실제 저장되는 값
- 링크(Link): 다음 노드를 가리키는 포인터(주소)
연결 리스트의 주요 연산
연결 리스트에서 수행할 수 있는 대표적인 연산은 다음 세 가지입니다.
- 삽입(Insertion)
- 삭제(Deletion)
- 순회(Traversing)
삭제(Deletion) 연산의 기본 절차
연결 리스트에서 노드를 삭제할 때는 다음과 같은 단계를 거칩니다.
- 삭제할 노드를 찾습니다.
- 노드를 해제하더라도 리스트가 끊어진 상태(unconnected components)가 되지 않도록 링크를 재조정합니다.
- 삭제할 요소를 반환하거나 화면에 출력합니다.
- 해당 노드의 메모리를 해제(deallocate)합니다.
머리(Head) 노드 삭제하기
C 언어에서 연결 리스트의 머리(head) 요소를 삭제하는 절차와 코드는 다음과 같습니다.
1. void del_head()
2. {
3. int x;
Node *temp;
4. if(Head==NULL)
5. {
6. printf("List is empty");
7. return;
8. }
9. x=Head->ele;
10. temp=Head;
11. if(Head==Tail)
12. Head=Tail=NULL;
13. else
14. Head=Head->next;
15. printf("Deleted element %d",x);
16. free(temp);
17. }각 단계별 동작을 살펴보면 다음과 같습니다.
- 4단계 – 리스트가 비어 있는지 확인합니다.
- 9단계 – 삭제할 요소를 읽어옵니다.
- 10단계 – 임시 포인터(temp)가 머리 노드를 가리키도록 합니다.
- 11단계 – 마지막 남은 노드의 삭제 여부를 확인합니다.
- 14단계 – 머리 포인터를 다음 노드로 이동시킵니다.
- 15단계 – 삭제된 요소를 화면에 출력합니다.
- 16단계 – 해당 노드의 메모리를 해제합니다.
꼬리(Tail) 노드 삭제하기
C 언어에서 연결 리스트의 꼬리(tail) 요소를 삭제하는 절차와 코드는 다음과 같습니다.
1. void del_tail()
2. {
3. int x;
4. Node *temp;
5. if(Head==NULL)
6. {
7. printf("List is empty");
8. return;
9. }
10. temp=Head;
11. while(temp->next !=Tail)
12. temp=temp->next;
13. x=Tail->ele;
14. Tail=temp;
15. Temp=temp->next;
16. Tail->next=NULL;
17. printf("Deleted element %d",x);
18. free(temp);
19. }각 단계별 동작을 살펴보면 다음과 같습니다.
- 5단계 – 리스트가 비어 있는지 확인합니다.
- 10~12단계 – 임시 포인터(temp)를 리스트의 뒤에서 두 번째 노드로 이동시킵니다.
- 13단계 – 삭제할 꼬리 요소를 읽어옵니다.
- 14단계 – 꼬리 포인터를 뒤에서 두 번째 노드로 이동시킵니다.
- 15단계 – 임시 포인터를 리스트의 마지막 노드로 이동시킵니다.
- 16단계 – 꼬리 노드가 임시 노드를 참조하지 않도록 연결을 제거합니다(NULL 설정).
- 17단계 – 삭제된 요소를 화면에 출력합니다.
- 18단계 – 해당 노드의 메모리를 해제합니다.
이처럼 연결 리스트에서 노드를 삭제할 때는 단순히 노드를 제거하는 것이 아니라, 앞뒤 노드 간의 연결 관계를 적절히 재조정한 후 메모리를 해제해야 리스트의 무결성이 유지됩니다.