배열은 같은 자료형의 데이터를 연속된 메모리 공간에 저장한다. 인덱스를 통해 빠르게 접근할 수 있다는 장점이 있지만, 크기가 고정되고 중간 데이터를 삽입하거나 삭제하기 어렵다는 단점도 존재한다.
연결 리스트는 각 데이터를 별도의 노드에 저장하고 포인터로 연결한다. 노드들이 메모리에 연속해서 배치될 필요가 없기 때문에 실행 중에 크기를 자유롭게 변경할 수 있다.
이 글에서는 코드조선의 Linked List 강의를 바탕으로 연결 리스트의 구조, 동적 메모리 할당, 앞·뒤 삽입, 이중 포인터를 이용한 순회와 삭제, 재귀적인 메모리 해제 원리를 정리한다.
1. 배열의 특징과 한계
배열은 여러 데이터를 연속된 메모리 공간에 저장한다.
int Numbers[4] = {10, 20, 30, 40};메모리에서는 다음과 비슷한 형태로 배치된다.
주소 값
0x1000 10
0x1004 20
0x1008 30
0x100C 40int가 4바이트라면 각 원소가 4바이트 간격으로 붙어 있다. 따라서 시작 주소와 인덱스를 이용해 원하는 원소의 위치를 바로 계산할 수 있다.
원소 주소 = 시작 주소 + 인덱스 × 자료형 크기다음 접근의 시간복잡도는 O(1)이다.
printf("%d\n", Numbers[2]);하지만 배열은 일반적으로 크기를 미리 결정해야 한다.
int Numbers[4];원소가 4개보다 많아지면 더 큰 배열을 만들고 기존 데이터를 복사해야 한다.
배열 중간에 새로운 값을 삽입할 때도 문제가 생긴다.
삽입 전
10 20 30 4020과 30 사이에 25를 삽입하려면 뒤쪽 값을 이동해야 한다.
10 20 25 30 40
→ →데이터가 N개라면 최악의 경우 N개에 가까운 데이터를 이동해야 하므로 삽입과 삭제의 시간복잡도는 O(N)이 된다.
2. 연결 리스트란 무엇인가?
연결 리스트는 데이터를 노드 단위로 저장하는 자료구조이다.
각 노드는 일반적으로 다음 두 가지 정보를 가진다.
1. 실제 데이터
2. 다음 노드의 주소구조를 그림으로 표현하면 다음과 같다.
┌─────────────┬─────────────┐
│ Data │ Next │
│ 10 │ 다음 주소 │
└─────────────┴─────────────┘여러 노드를 연결하면 다음과 같은 리스트가 만들어진다.
Head
↓
[10 | 다음] → [20 | 다음] → [30 | NULL]마지막 노드는 다음 노드가 없으므로 NULL을 저장한다.
연결 리스트의 노드는 반드시 서로 붙어 있을 필요가 없다.
0x1000 0x3500 0x2200
[10 | 0x3500] → [20 | 0x2200] → [30 | NULL]각 노드가 다음 노드의 메모리 주소를 알고 있으므로 메모리 위치가 떨어져 있어도 하나의 자료구조로 연결할 수 있다.
3. 연결 리스트의 노드 만들기
C 언어에서는 구조체로 노드를 정의할 수 있다.
struct Node
{
int Data;
struct Node* PtrToNextNode;
};Data에는 실제 데이터를 저장한다.
int Data;PtrToNextNode에는 다음 노드의 주소를 저장한다.
struct Node* PtrToNextNode;같은 구조체를 반복해서 작성하지 않도록 typedef를 사용할 수 있다.
typedef struct Node Node_t;전체 코드는 다음과 같다.
typedef struct Node
{
int Data;
struct Node* PtrToNextNode;
} Node_t;이제 다음과 같이 간단하게 노드 자료형을 사용할 수 있다.
Node_t Node;
Node_t* PtrToNode;
4. Head 포인터의 역할
연결 리스트는 첫 번째 노드의 위치를 알아야 전체 노드를 탐색할 수 있다.
첫 번째 노드를 가리키는 포인터를 일반적으로 Head라고 한다.
Node_t* PtrToHeadNode = NULL;리스트가 비어 있을 때 Head는 NULL이다.
Head → NULL첫 번째 노드가 생기면 Head에 첫 번째 노드의 주소를 저장한다.
Head → [10 | NULL]노드가 추가되면 각 노드의 PtrToNextNode를 따라간다.
Head
↓
[10] → [20] → [30] → NULLHead를 잃어버리면 첫 번째 노드에 접근할 방법이 사라진다. 결과적으로 연결된 나머지 노드에도 접근할 수 없다.
따라서 Head는 연결 리스트의 시작점을 보관하는 중요한 포인터이다.
5. 노드는 동적 메모리에 생성한다
연결 리스트는 실행 중에 노드의 개수를 변경하기 위해 동적 메모리를 사용한다.
새로운 노드는 malloc()으로 생성한다.
Node_t* PtrToNewNode =
(Node_t*)malloc(sizeof(Node_t));sizeof(Node_t)는 노드 하나를 저장하는 데 필요한 메모리 크기를 계산한다.
malloc()이 메모리 할당에 실패하면 NULL을 반환한다. 따라서 결과를 확인해야 한다.
assert(PtrToNewNode != NULL);메모리를 할당한 뒤에는 노드의 내용을 설정한다.
PtrToNewNode->Data = InData;
PtrToNewNode->PtrToNextNode = NULL;처음 생성한 노드는 아직 연결 리스트에 포함된 것이 아니다.
기존 리스트
Head → [10] → [20] → NULL새 노드
PtrToNewNode → [30 | NULL]새 노드를 기존 노드와 연결하거나 Head에 넣어야 비로소 리스트의 일부가 된다.
6. 리스트 앞에 노드 삽입하기
리스트의 맨 앞에 노드를 삽입하는 함수는 다음과 같이 작성할 수 있다.
void InsertFront(
Node_t** InPtrToPtrToHeadNode,
int InData)
{
Node_t* PtrToNewNode =
(Node_t*)malloc(sizeof(Node_t));
assert(PtrToNewNode != NULL);
PtrToNewNode->Data = InData;
PtrToNewNode->PtrToNextNode =
*InPtrToPtrToHeadNode;
*InPtrToPtrToHeadNode =
PtrToNewNode;
}함수 매개변수로 Node_t**를 받는 이유는 원래 Head 포인터의 값을 변경해야 하기 때문이다.
InsertFront(&PtrToHeadNode, 10);삽입 전
Head → [20] → [30] → NULL
새 노드 → [10 | NULL]먼저 새 노드가 기존 첫 번째 노드를 가리키게 한다.
PtrToNewNode->PtrToNextNode =
*InPtrToPtrToHeadNode;새 노드 [10] → [20] → [30] → NULL그다음 Head가 새 노드를 가리키게 한다.
*InPtrToPtrToHeadNode =
PtrToNewNode;Head → [10] → [20] → [30] → NULL이 두 문장의 순서가 중요하다.
Head를 먼저 새 노드로 변경하면 기존 첫 번째 노드의 주소를 잃어버릴 수 있다.
앞에 삽입하는 작업은 기존 노드 개수와 관계없이 포인터 두 개만 수정한다. 따라서 시간복잡도는 O(1)이다.
7. 리스트 뒤에 노드 삽입하기
뒤에 삽입하려면 마지막 노드까지 이동해야 한다.
영상에서는 이중 포인터를 이용해 다음과 같이 구현한다.
void InsertRear(
Node_t** InPtrToPtrToHeadNode,
int InData)
{
Node_t* PtrToNewNode =
(Node_t*)malloc(sizeof(Node_t));
assert(PtrToNewNode != NULL);
PtrToNewNode->Data = InData;
PtrToNewNode->PtrToNextNode = NULL;
Node_t** PtrToPtrToLastNode =
InPtrToPtrToHeadNode;
while (*PtrToPtrToLastNode != NULL)
{
PtrToPtrToLastNode =
&((*PtrToPtrToLastNode)
->PtrToNextNode);
}
*PtrToPtrToLastNode =
PtrToNewNode;
}이 코드를 이해하려면 PtrToPtrToLastNode가 노드를 직접 가리키는 포인터가 아니라는 점을 알아야 한다.
Node_t** PtrToPtrToLastNode;이 변수는 현재 노드를 가리키는 포인터의 주소를 저장한다.
처음에는 Head 포인터의 주소를 가진다.
PtrToPtrToLastNode
↓
Head 포인터
↓
첫 노드반복문 안에서는 현재 노드의 PtrToNextNode 주소로 이동한다.
PtrToPtrToLastNode =
&((*PtrToPtrToLastNode)
->PtrToNextNode);여러 줄로 풀면 다음과 같다.
Node_t* PtrToCurrentNode =
*PtrToPtrToLastNode;
Node_t** PtrToPtrToNextNode =
&(PtrToCurrentNode->PtrToNextNode);
PtrToPtrToLastNode =
PtrToPtrToNextNode;리스트가 다음과 같다고 가정한다.
Head → [10] → [20] → [30] → NULL반복할 때마다 가리키는 위치가 다음과 같이 이동한다.
Head 포인터의 주소
→ 10 노드의 next 주소
→ 20 노드의 next 주소
→ 30 노드의 next 주소30 노드의 next에는 NULL이 들어 있다.
PtrToPtrToLastNode
↓
[30 노드의 next 포인터]
↓
NULL따라서 반복문이 종료된다.
마지막으로 그 위치에 새 노드의 주소를 넣는다.
*PtrToPtrToLastNode =
PtrToNewNode;Head → [10] → [20] → [30] → [40] → NULL리스트가 비어 있어도 동작한다
리스트가 비어 있다면 처음부터 다음 상태이다.
PtrToPtrToLastNode → Head
*PtrToPtrToLastNode = NULL반복문은 한 번도 실행되지 않는다.
그다음 문장이 Head에 새 노드의 주소를 넣는다.
*PtrToPtrToLastNode = PtrToNewNode;Head → [새 노드] → NULL이중 포인터를 사용했기 때문에 빈 리스트와 노드가 존재하는 리스트를 같은 코드로 처리할 수 있다.
마지막 노드를 찾기 위해 모든 노드를 지나가므로 시간복잡도는 O(N)이다. 별도의 Tail 포인터를 관리한다면 뒤쪽 삽입을 O(1)로 만들 수 있다.
8. 연결 리스트 전체를 출력하기
연결 리스트를 출력할 때는 Head부터 시작해 NULL을 만날 때까지 이동한다.
void Print(Node_t* InPtrToHeadNode)
{
Node_t* PtrToCurrentNode =
InPtrToHeadNode;
while (PtrToCurrentNode != NULL)
{
printf("%d ", PtrToCurrentNode->Data);
PtrToCurrentNode =
PtrToCurrentNode->PtrToNextNode;
}
printf("\n");
}실행 과정은 다음과 같다.
현재 노드: 10 → 출력
현재 노드: 20 → 출력
현재 노드: 30 → 출력
현재 노드: NULL → 종료결과는 다음과 같다.
10 20 30모든 노드를 확인하므로 시간복잡도는 O(N)이다.
배열은 인덱스를 이용해 특정 위치에 O(1)로 접근할 수 있다. 반면 단일 연결 리스트에서 세 번째 노드를 찾으려면 첫 번째 노드부터 포인터를 따라가야 한다.
Head → 첫 번째 → 두 번째 → 세 번째따라서 특정 위치에 접근하는 시간복잡도도 O(N)이다.
9. 모든 노드를 재귀적으로 삭제하기
malloc()으로 할당한 노드는 사용이 끝났을 때 반드시 free()해야 한다.
영상에서는 재귀함수를 사용해 마지막 노드부터 메모리를 해제한다.
void DestroyRecursively(
Node_t* InPtrToCurrentNode)
{
if (InPtrToCurrentNode == NULL)
{
return;
}
DestroyRecursively(
InPtrToCurrentNode->PtrToNextNode);
printf(
"%d has been deleted.\n",
InPtrToCurrentNode->Data);
free(InPtrToCurrentNode);
}리스트가 다음과 같다고 가정한다.
Head → [10] → [20] → [30] → NULL재귀함수는 먼저 끝까지 이동한다.
Destroy(10)
→ Destroy(20)
→ Destroy(30)
→ Destroy(NULL)NULL에 도달하면 호출된 함수들이 반대 순서로 돌아온다.
30 노드 free()
20 노드 free()
10 노드 free()다음 노드로 먼저 이동한 뒤 현재 노드를 해제하는 이유가 있다.
현재 노드를 먼저 해제하면 다음 노드의 주소도 읽을 수 없기 때문이다.
잘못된 순서는 다음과 같다.
free(InPtrToCurrentNode);
DestroyRecursively(
InPtrToCurrentNode->PtrToNextNode);free() 이후에 PtrToNextNode에 접근하므로 정의되지 않은 동작이 발생한다.
따라서 다음 노드의 주소를 사용한 뒤 현재 노드를 해제해야 한다.
10. free()와 댕글링 포인터
free()는 포인터 변수 자체를 삭제하는 함수가 아니다.
free(InPtrToCurrentNode);포인터가 가리키고 있던 동적 메모리를 반환한다.
free 전
포인터 → 정상적인 노드 메모리free 후
포인터 → 이미 반환된 메모리free() 이후에도 포인터 변수에는 이전 주소가 남아 있다. 이처럼 이미 해제된 메모리를 가리키는 포인터를 댕글링 포인터라고 한다.
다음 접근은 위험하다.
free(PtrToNode);
printf("%d", PtrToNode->Data); // 잘못된 접근보통 해제한 뒤에는 포인터에 NULL을 저장한다.
free(PtrToNode);
PtrToNode = NULL;그러나 함수 매개변수로 전달된 지역 포인터만 NULL로 바꾸어도 원래 Head는 바뀌지 않는다.
void DestroyRecursively(Node_t* Current)
{
free(Current);
Current = NULL;
}Current는 함수 내부의 복사본이기 때문이다.
따라서 전체 삭제가 끝난 뒤 실제 Head를 직접 NULL로 변경한다.
void Destroy(
Node_t** InPtrToPtrToHeadNode)
{
if (*InPtrToPtrToHeadNode == NULL)
{
printf("Linked list is empty.\n");
return;
}
DestroyRecursively(
*InPtrToPtrToHeadNode);
*InPtrToPtrToHeadNode = NULL;
}
11. 특정 데이터를 가진 노드 삭제하기
특정 노드를 삭제하려면 세 가지 작업이 필요하다.
1. 삭제할 노드를 찾는다.
2. 이전 연결을 다음 노드로 변경한다.
3. 삭제할 노드의 메모리를 해제한다.다음 리스트에서 20을 삭제한다고 가정한다.
Head → [10] → [20] → [30] → NULL단순히 20을 free()하면 안 된다.
Head → [10] → 해제된 메모리
[30] → NULL10 노드의 next가 여전히 해제된 20 노드의 주소를 가지고 있기 때문이다. 30 노드로 이어지는 연결도 끊어진다.
삭제하기 전에 10 노드의 next가 30 노드를 가리키도록 변경해야 한다.
연결 변경
[10] ─────────→ [30]
[20]그다음 20 노드를 해제한다.
삭제 완료
Head → [10] → [30] → NULL12. 이중 포인터를 이용한 삭제
영상에서는 이중 포인터를 사용해 첫 번째 노드와 중간 노드를 같은 방식으로 삭제한다.
int Remove(
Node_t** InPtrToPtrToHeadNode,
int InData)
{
Node_t** PtrToPtrToCurrentNode =
InPtrToPtrToHeadNode;
while (*PtrToPtrToCurrentNode != NULL)
{
if ((*PtrToPtrToCurrentNode)->Data
== InData)
{
Node_t* PtrToDeletedNode =
*PtrToPtrToCurrentNode;
*PtrToPtrToCurrentNode =
PtrToDeletedNode->PtrToNextNode;
free(PtrToDeletedNode);
PtrToDeletedNode = NULL;
return 1;
}
PtrToPtrToCurrentNode =
&((*PtrToPtrToCurrentNode)
->PtrToNextNode);
}
return 0;
}PtrToPtrToCurrentNode는 항상 현재 노드를 가리키는 포인터의 주소를 저장한다.
현재 노드가 첫 번째 노드라면 Head 포인터의 주소를 가진다.
PtrToPtrToCurrentNode → Head → 첫 번째 노드현재 노드가 두 번째 노드라면 첫 번째 노드의 next 주소를 가진다.
PtrToPtrToCurrentNode
↓
[첫 번째 노드의 next]
↓
두 번째 노드삭제할 노드를 찾으면 먼저 주소를 보관한다.
Node_t* PtrToDeletedNode =
*PtrToPtrToCurrentNode;그다음 현재 노드를 가리키던 포인터에 삭제할 노드의 다음 주소를 넣는다.
*PtrToPtrToCurrentNode =
PtrToDeletedNode->PtrToNextNode;마지막으로 삭제할 노드의 메모리를 해제한다.
free(PtrToDeletedNode);첫 번째 노드를 삭제하는 경우
삭제 전
Head → [10] → [20] → NULLPtrToPtrToCurrentNode는 Head의 주소를 가진다.
*PtrToPtrToCurrentNode =
PtrToDeletedNode->PtrToNextNode;따라서 Head가 바로 20 노드를 가리키게 된다.
삭제 후
Head → [20] → NULL중간 노드를 삭제하는 경우
삭제 전
Head → [10] → [20] → [30] → NULL20을 찾았을 때 PtrToPtrToCurrentNode는 10 노드의 next 주소를 가진다.
따라서 같은 대입문으로 10 노드의 next가 30을 가리키게 된다.
삭제 후
Head → [10] → [30] → NULL이중 포인터를 사용하면 첫 번째 노드를 삭제하는 특별한 코드를 별도로 작성하지 않아도 된다.
13. 연결 리스트의 시간복잡도
단일 연결 리스트의 주요 연산을 정리하면 다음과 같다.
| 앞쪽 삽입 | O(1) | Head 주변의 포인터만 변경한다. |
| 뒤쪽 삽입 | O(N) | 마지막 노드를 찾아야 한다. |
| 값 탐색 | O(N) | 첫 노드부터 순서대로 확인한다. |
| 특정 위치 접근 | O(N) | 포인터를 따라 해당 위치까지 이동한다. |
| 값 삭제 | O(N) | 삭제할 노드를 먼저 찾아야 한다. |
| 전체 출력 | O(N) | 모든 노드를 방문한다. |
| 전체 삭제 | O(N) | 모든 노드를 한 번씩 해제한다. |
별도의 Tail 포인터를 유지하면 뒤쪽 삽입을 O(1)로 만들 수 있다.
Head → [10] → [20] → [30] ← Tail그러나 중간 노드를 찾거나 특정 인덱스에 접근하는 작업은 여전히 O(N)이다.
14. 배열과 연결 리스트 비교
| 메모리 배치 | 연속적이다. | 떨어져 있어도 된다. |
| 크기 | 일반적으로 미리 결정한다. | 실행 중 변경하기 쉽다. |
| 인덱스 접근 | O(1)이다. | O(N)이다. |
| 앞쪽 삽입 | O(N)이다. | O(1)이다. |
| 중간 삭제 | 데이터 이동이 필요하다. | 연결 변경이 필요하다. |
| 추가 메모리 | 데이터만 저장한다. | 노드마다 포인터가 필요하다. |
| 캐시 효율 | 비교적 좋다. | 비교적 낮을 수 있다. |
| 구현 난이도 | 비교적 단순하다. | 포인터 관리가 필요하다. |
연결 리스트가 항상 배열보다 좋은 것은 아니다.
빠른 인덱스 접근이 중요하면 배열이 적합하다. 데이터의 앞쪽 삽입과 삭제가 자주 발생하거나 실행 중 크기가 자주 변한다면 연결 리스트가 적합할 수 있다.
15. 연결 리스트에서 주의할 점
새 노드를 반드시 기존 리스트에 연결해야 한다
Node_t* NewNode = malloc(sizeof(Node_t));메모리만 할당했다고 리스트에 포함되는 것은 아니다.
NewNode->PtrToNextNode = *Head;
*Head = NewNode;연결 작업까지 완료해야 한다.
NULL에 역참조를 사용하면 안 된다
Node_t* Ptr = NULL;
printf("%d", Ptr->Data); // 잘못된 접근노드를 사용하기 전에 포인터가 NULL인지 확인해야 한다.
free() 이후에 노드에 접근하면 안 된다
free(PtrToNode);
PtrToNode->Data = 10; // 잘못된 접근해제된 메모리는 더 이상 사용할 수 없다.
연결을 변경하기 전에 필요한 주소를 보관해야 한다
삭제할 노드의 다음 주소를 잃어버리면 이후 노드에 접근할 수 없게 된다.
Node_t* Deleted = *CurrentLink;
*CurrentLink = Deleted->PtrToNextNode;
free(Deleted);할당한 노드는 반드시 해제해야 한다
malloc()으로 생성하고 free()하지 않으면 메모리 누수가 발생한다.
malloc()으로 할당
→ 사용
→ free()로 반환마무리
연결 리스트는 각 데이터를 노드에 저장하고 포인터를 이용해 노드들을 연결하는 자료구조이다.
Head → [Data | Next] → [Data | Next] → NULL연결 리스트를 이해하기 위한 핵심은 다음과 같다.
- 노드는 데이터와 다음 노드의 주소를 가진다.
- Head는 첫 번째 노드를 가리킨다.
- 새 노드는 malloc()으로 동적 할당한다.
- 앞쪽 삽입은 새 노드를 기존 Head 앞에 연결한다.
- 뒤쪽 삽입은 마지막 NULL 포인터의 위치를 찾는다.
- 이중 포인터를 사용하면 Head와 노드의 next를 같은 방식으로 다룰 수 있다.
- 삭제할 때는 먼저 연결을 변경한 뒤 free()해야 한다.
- 전체 삭제 후에는 Head를 NULL로 변경해야 한다.
특히 영상 코드에서 반복해서 등장하는 이중 포인터는 다음 관점으로 이해하면 된다.
Node_t** PtrToPtrToCurrentNode;이는 단순히 현재 노드를 가리키는 것이 아니다.
현재 노드를 가리키고 있는 포인터 변수의 주소를 저장한다.
이 관점을 이해하면 다음 코드도 자연스럽게 해석할 수 있다.
PtrToPtrToCurrentNode =
&((*PtrToPtrToCurrentNode)
->PtrToNextNode);현재 노드에서 다음 노드로 단순히 이동하는 것을 넘어, 다음 노드를 가리키는 포인터 변수의 위치로 이동한다는 뜻이다.
이 덕분에 삽입과 삭제에서 Head 포인터와 각 노드의 next 포인터를 동일한 방식으로 수정할 수 있다.
'C언어 > 개념·이론' 카테고리의 다른 글
| HashSet과 HashMap은 어떻게 빠르게 데이터를 찾을까? (0) | 2026.07.23 |
|---|---|
| 재귀함수와 반복문의 시간복잡도, 그리고 출력 순서가 뒤집히는 이유 (0) | 2026.07.21 |