C++ 싱글 링크드리스트(Singly Linked List) 구현 및 핵심 개념
Source
Evernote/Technote scraps/준환이형님쩜넷 - 따뜻하게 즐기는 코딩 한 잔~♪ C++ - 쉽게 설명한 링크드리스트(Linked list) 이야기.md
Summary
이 문서는 C++에서 배열 기반 리스트의 한계(삽입 시 데이터 이동 오버헤드, 메모리 비효율)를 설명하며 링크드리스트의 필요성을 제시합니다. 링크드리스트 이해를 위한 5가지 핵심 전제(자료형 정의, 생성 방식 다양성, 용어 명확화, NULL 초기화 중요성, 스왑 개념)를 설명하고, Node 클래스와 SLL(Single Linked List) 클래스를 사용한 싱글 링크드리스트의 ‘앞단 삽입(Insert First)’ 구현 예제를 제공합니다. 특히 새 노드의 tail 포인터를 기존 LinkHead로 연결한 후, LinkHead를 새 노드로 업데이트하는 순서의 중요성을 강조합니다.
Key Points
- 배열 리스트는 임의 위치 삽입 시 O(n)의 데이터 이동 비용이 발생하지만, 링크드리스트는 포인터 연결만으로 효율적인 삽입/삭제가 가능합니다.
- 링크드리스트 구현에는 클래스/구조체, 동적할당(new), 포인터 개념이 필수적입니다.
- 용어 정의: 노드 내부의 연결 포인터는
head/tail, 리스트 전체의 시작 지점은LinkHead, 임시 작업용 포인터는tempPoint로 명확히 구분하는 것이 좋습니다. - 포인터는 반드시 NULL 초기화해야 하며, 리스트 종단 조건(
!= NULL)을 올바르게 설정해야 세그멘테이션 폴트 등을 방지할 수 있습니다. - 앞단 삽입 로직: 1) 새 노드 생성 및 데이터 할당, 2) 새 노드의 다음 포인터(
tail)를 현재LinkHead로 연결, 3)LinkHead를 새 노드로 갱신합니다. - 싱글 링크드리스트를 이해하면 더블 링크드리스트나 환형 링크드리스트로 확장하는 것이 용이합니다.