이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
포인터로 연결된 노드
- 연결 목록(list) 은 히프(heap) 상에 산재해 있는 작은 구조체인 노드(nodes) 들의 체인입니다.
- 각 노드는 값과 다음 노드를 가리키는 포인터를 포함합니다. 포인터를 따라가면 목록 전체를 순회할 수 있습니다.
- 배열과 달리 목록은 다른 요소를 이동시키지 않으면서 한 번에 하나의 노드만 증가시킬 수 있습니다.
자기 참조 구조체(self-referential struct)
- 노드는 자신의 타입을 가리키는 포인터를 포함하는 구조체입니다:
struct Node { int data; struct Node *next; };—data은 값(value)이며,next는 다음 노드를 가리킵니다.- 이는 스타터(starter)에서 모두
Node로 제공됩니다. 마지막 노드의next은NULL입니다.
head와 NULL 종점
- A single pointer, the head, points to the first node. From there you reach the rest.
- 가장 마지막 노드는
NULL를 가리키며, 이는 목록의 끝을 나타냅니다. - 빈 목록은 단순히
head == NULL일 뿐이며, 노드가 전혀 없습니다.
English
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
앞쪽(newest/front)에 노드 추가하기
- 앞쪽에 추가하려면 새 노드를 만들고, 이 노드의
next를 기존 head에 연결한 뒤, 새 노드를 새로운 head로 반환합니다. - 이 과정은 빠릅니다. 다른 노드는 아무런 조작도 받지 않습니다.
- 헤드가 변경되므로 함수는 새로운 헤드를 반환하며, 호출자가 이를 저장합니다.
흔한 실수
head포인터를 잃으면 전체 목록에 접근할 수 없게 됩니다.- 모든 노드를 해제(free)해야 합니다. 마지막 노드는
NULL를 가리킵니다.
이제 직접 해보기
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - 새 노드는
malloc(sizeof(Node))에서 생성되며, 체크러가 목록을 해제합니다.main를 작성하지 마십시오.
탐색하기
노드와 포인터
각 노드는 다음 노드를 가리키며, 삽입/삭제는 링크 변경을 통해 수행됩니다.
난이도 5/5 · 400코인 + 오늘 첫 완료 시 작은 보너스 추가
int length(const Node *head)을 완성하여 리스트 내의 노드 수를 세십시오(빈 리스트인 경우 0). ->next로 탐색하여 NULL이 될 때까지 진행하십시오. Node 타입은 주어졌습니다. **main**을 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 5/5 · 400코인 + 오늘 첫 완료 시 작은 보너스 추가
int sum_list(const Node *head)을 완성하여 모든 노드의 data 합계를 반환하십시오(빈 리스트인 경우 0). Node 타입은 주어졌습니다. **main**을 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.
난이도 5/5 · 400코인 + 오늘 첫 완료 시 작은 보너스 추가
Node *push_front(Node *head, int value)을 완성하여 새로운 노드(malloc 포함)를 만들고, 이 노드의 next를 기존 head을 가리키게 하여 새 헤드로 반환하십시오. 체크러가 리스트를 해제합니다. **main**을 작성하지 마십시오.
출력을 보려면 '실행'을 클릭하세요.