74.0 연결 리스트 구현하기

프로그래밍에서 빼놓을 수 없는 부분이 자료구조입니다. 이번에는 간단하면서도 널리 쓰이는 연결 리스트(linked list)를 구현해보겠습니다.

연결 리스트는 데이터가 담긴 노드(메모리 공간)를 일렬로 연결해놓았다고 해서 연결 리스트라고 부르며 특징은 다음과 같습니다.

  • 리스트의 중간 지점에 노드를 손쉽게 추가하거나 삭제할 수 있습니다.
  • 특정 노드를 찾으려면 노드를 모두 검색해야 합니다(최악의 경우).
  • 크기가 고정되어 있지 않습니다.

다음은 다른 노드를 가리키는 포인터가 하나씩만 있는 단일 연결 리스트(singly linked list)입니다.

그림 74‑1 단일 연결 리스트

지금부터 구조체, 포인터, 함수, 메모리 할당을 사용하여 단일 연결 리스트를 구현하는 방법을 알아보겠습니다. 참고로 연결 리스트는 기본적인 자료 구조이지만 포인터를 사용하다 보니 많은 사람들이 어려워하는 부분입니다. 따라서 이해가 잘 안 되더라도 걱정할 필요는 없습니다.

최근 수정: 2016년 12월 15일, 목요일, 오전 10:23