연결 리스트란?
연결 리스트(Linked List)는 동적 메모리 할당(dynamic memory allocation) 방식을 사용하는 자료구조입니다. 즉, 저장해야 할 데이터의 양에 따라 크기가 유동적으로 늘어나거나 줄어들 수 있습니다. 연결 리스트는 여러 개의 노드(Node)가 모여 이루어진 집합으로 정의되며, 각 노드는 두 부분으로 구성됩니다.
- 데이터(Data): 실제로 저장하고자 하는 값
- 링크(Link): 다음 노드를 가리키는 포인터
데이터, 링크 및 연결 리스트 전체의 구조는 아래 그림과 같이 표현할 수 있습니다.
연결 리스트의 주요 연산
C 언어에서 연결 리스트에 수행할 수 있는 대표적인 연산은 다음 세 가지입니다.
- 삽입(Insertion) — 리스트에 새로운 노드를 추가합니다.
- 삭제(Deletion) — 리스트에서 기존 노드를 제거합니다.
- 순회(Traversing) — 첫 번째 노드부터 마지막 노드까지 차례대로 방문하며 데이터를 처리합니다.
삭제(Deletion) 연산의 동작 원리
노드를 삭제할 때는 해당 노드의 앞 노드가 삭제할 노드가 아닌, 그다음 노드를 직접 가리키도록 링크를 변경한 뒤 메모리를 해제하는 것이 핵심입니다. 아래 예시를 통해 단계별로 살펴보겠습니다.
노드 2 삭제
노드 1 삭제
노드 3 삭제
삭제 연산 C 프로그램
다음은 연결 리스트에서 지정한 위치의 요소를 삭제하는 C 언어 프로그램입니다.
#include <stdio.h>
#include <stdlib.h>
struct Node{
int data;
struct Node *next;
};
void push(struct Node** head_ref, int new_data){
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void deleteNode(struct Node **head_ref, int position){
//리스트가 비어 있는 경우
if (*head_ref == NULL)
return;
struct Node* temp = *head_ref;
if (position == 0){
*head_ref = temp->next;
free(temp);
return;
}
for (int i=0; temp!=NULL && i<position-1; i++)
temp = temp->next;
if (temp == NULL || temp->next == NULL)
return;
struct Node *next = temp->next->next;
free(temp->next); //메모리 해제
temp->next = next;
}
void printList(struct Node *node){
while (node != NULL){
printf(" %d ", node->data);
node = node->next;
}
}
int main(){
struct Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
push(&head, 8);
puts("Created List: ");
printList(head);
deleteNode(&head, 3);
puts("\n List after Deletion at position 3: ");
printList(head);
return 0;
}프로그램 설명
- push 함수: 새 노드를 생성하여 리스트의 맨 앞에 추가합니다.
- deleteNode 함수: 삭제할 위치(position)를 매개변수로 받습니다. 위치가 0이면 헤드 노드를 바로 삭제하고, 그렇지 않으면 해당 위치의 이전 노드까지 이동한 후 링크를 재설정하고
free()로 메모리를 해제합니다. - printList 함수: 리스트 전체를 순회하며 각 노드의 데이터를 출력합니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Created List: 8 2 3 1 7 List after Deletion at position 3: 8 2 3 7
출력 결과에서 확인할 수 있듯이, 초기 리스트 8 2 3 1 7에서 3번째 위치(값 1)의 노드가 성공적으로 삭제되어 8 2 3 7이 된 것을 볼 수 있습니다.