널널한 개발자 TV의 자료구조 강의 시리즈를 정리할 것이다.
단일 연결 리스트(Single Linked List)
노드(Node)
- 데이터를 담기위한 바구니, 컨테이너 같은 것
- 연결 리스트(Single List)는 컨테이너라고도 한다.
- 연결 리스트는 여러 구조체 인스턴스를 체인처럼 줄줄이 포인터로 연결한 자료구조이다.
- 연결에 사용된 포인터 숫자가 1개이고, 자기 다음을 가리키는 것이 특징이다.
연결 리스트 코딩 요령
- 구조체 배열로 테스트한다.
- 연결 순서를 임의로 변경해본다.
- 리스트 출력은 별도 함수로 분리한다.
- 디버거(Debugger)로 노드 하나씩 따라가며 메모리 위치를 확인한다.
실험을 위한 단일 연결 리스트 구조 생성하기
보통 연결 리스트 예제를 작성할 때는 메모리를 동적 할당하는 것이 일반적이지만 구조체를 배열로 선언하는 단순한 방법으로 연결 리스트를 생성한다.
이해를 목적으로 만드는 예제이기 때문이다.
#include <stdio.h>
typedef struct NODE
{
// 관리될 데이터
int nData;
// 데이터 관리를 위한 포인터
struct NODE *next;
} NODE;
int main(void)
{
NODE list[5] = { 0, };
// 값 초기화
list[0].nData = 100;
list[1].nData = 200;
list[2].nData = 300;
list[3].nData = 400;
list[4].nData = 500;
// 연결 리스트 구조화
list[0].next = &list[1];
list[1].next = &list[2];
list[2].next = &list[3];
list[3].next = &list[4];
list[4].next = NULL;
for (int i = 0; i < 5; ++i)
printf("list[%d]: %d\n", i, list[i].nData);
printf("\n");
NODE *pTmp = &list[0];
while (pTmp != NULL)
{
printf("%p: %d\n", pTmp, pTmp->nData);
pTmp = pTmp->next;
}
return 0;
}실행 결과
