Linked lists · 연결된 리스트
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
포인터로 연결된 노드
- 연결 목록(list) 은 히프(heap) 상에 산재해 있는 작은 구조체인 노드(nodes) 들의 체인입니다.
- 각 노드는 값과 다음 노드를 가리키는 포인터를 포함합니다. 포인터를 따라가면 목록 전체를 순회할 수 있습니다.
- 배열과 달리 목록은 다른 요소를 이동시키지 않으면서 한 번에 하나의 노드만 증가시킬 수 있습니다.
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
자기 참조 구조체(self-referential struct)
- 노드는 자신의 타입을 가리키는 포인터를 포함하는 구조체입니다:
struct Node { int data; struct Node *next; };—data은 값(value)이며,next는 다음 노드를 가리킵니다.- 이는 스타터(starter)에서 모두
Node로 제공됩니다. 마지막 노드의next은NULL입니다.
head and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
head와 NULL 종점
- 단일 포인터인 head가 첫 번째 노드를 가리킵니다.そこから 나머지 노드에 도달할 수 있습니다.
- 가장 마지막 노드는列表의 끝을 나타내는
NULL를 가리킵니다. - 빈 목록은 단순히
head == NULL일 뿐이며, 노드가 전혀 없습니다.
#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;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
앞쪽(newest/front)에 노드 추가하기
- 앞쪽에 추가하려면 새 노드를 만들고, 이 노드의
next를 기존 head에 연결한 뒤, 새 노드를 새로운 head로 반환합니다. - 이 과정은 빠릅니다. 다른 노드는 아무런 조작도 받지 않습니다.
- head가 변경되므로 함수는 새로운 head를 반환하며, 호출侧(code)에서는 이를 저장해야 합니다.
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
흔한 실수
head포인터를 잃으면 전체 목록에 접근할 수 없게 됩니다.- 모든 노드를 해제(free)해야 합니다. 마지막 노드는
NULL를 가리킵니다.
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
이제 직접 해보기
- 리스트를 traversal하려면
cur포인터와cur = cur->next을 사용하고,NULL에 도달하면 멈춥니다. - 새 노드는
malloc(sizeof(Node))에서 가져옵니다. 체크程序가 목록을 자동으로 해제합니다. 따라서 반드시main은 작성하지 마십시오.
Nodes and pointers · 노드와 포인터
Each node points to the next; insert/delete by re-linking. · 각 노드는 다음 노드를 가리키며, 삽입/삭제는 링크 변경을 통해 수행됩니다.
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not write a main. · int length(const Node *head)을 완성하여 리스트 내의 노드 수를 세십시오(빈 리스트인 경우 0). ->next로 탐색하여 NULL이 될 때까지 진행하십시오. Node 타입은 주어졌습니다. **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not write a main. · int sum_list(const Node *head)을 완성하여 모든 노드의 data 합계를 반환하십시오(빈 리스트인 경우 0). Node 타입은 주어졌습니다. **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not write a main. · Node *push_front(Node *head, int value)을 완성하여 새로운 노드(malloc 포함)를 만들고, 이 노드의 next를 기존 head을 가리키게 하여 새 헤드로 반환하십시오. 체크러가 리스트를 해제합니다. **main**을 작성하지 마십시오.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.