- 데이터(노드)를 저장할 때 하나의 데이터와 그 다음 데이터로의 위치(보통 다음 노드의 주소나 참조)를 함께 저장하여 논리적으로 연결(link)하는 방식으로 자료를 저장
- 선형 자료 구조
- 물리적으로 연속된 공간에 저장하지 않고, 메모리 동적 할당을 통해 필요할 때마다 새로운 공간을 할당받아 저장
- 추가와 삭제가 자유로움
파이썬의 참조와 C 언어의 포인터의 차이
파이썬의 참조(Reference)
- 파이썬에서는 변수들이 실제 객체에 대한 참조를 저장
- 메모리 주소를 직접적으로 다루지 않기 때문에 메모리 관리가 자동으로 이루어지며, 개발자는 객체의 참조만을 다룸
- 예를 들어, 리스트의 노드가 다른 노드를 가리킬 때 그 노드는 단순히 다른 객체를 참조하고 있다는 뜻
- 파이썬의 참조는 안전하고 메모리 관리를 자동으로 하기 때문에, 메모리 누수나 잘못된 접근 문제로부터 비교적 자유로움
C 언어의 포인터(Pointer)
- C 언어에서는 포인터를 통해 변수의 메모리 주소를 직접 다룸
- 개발자는 변수나 객체의 메모리 주소를 명시적으로 지정 및 관리 가능
- 포인터는 강력한 기능을 제공하지만,
- 메모리 할당 및 해제를 수동으로 관리해야 하며,
- 잘못된 메모리 접근으로 인한 오류(예: 세그멘테이션 오류) 발생 가능성이 있음
- C 언어의 연결 리스트 구현에서, 각 노드는 다음 노드에 대한 포인터를 명시적으로 포함함
연결 리스트의 유형
단일 연결 리스트(Single Linked List)
- 각 노드는 데이터와 다음 노드를 가리키는 포인터(
next)를 가짐 - 순차 탐색 가능
- 삽입과 삭제가 쉬움
- 항상 처음부터 탐색해야해, 특정 위치에 있는 노드를 찾기 위해서는 비효율적
이중 연결 리스트(Doubly Linked List)
- 각 노드는 데이터와 다음 노드를 가리키는 포인터(
next), 이전 노드를 가리키는 포인터(prev)를 가짐 - 양쪽 탐색이 가능해 단일 연결 리스트보다 탐색이 유연함 (뒤로 이동하거나 역순 탐색 시에 효율적)
- 각 노드가 두 개의 포인터를 저장하므로 메모리 사용량이 많음
원형 연결 리스트(Circular Linked List)
- 마지막 노드가 다시 첫 번째 노드를 가리키는 형태로, 리스트의 끝이 없는 원형 구조를 가짐
- 순환 구조
- 메모리 효율성이 높으며, 원형 구조를 이용한 알고리즘에 유리함
- 탐색에 대한 종료 조건이 필요하며, 리스트가 무한 반복 될 수 있음
