소개
이 프로젝트에서는 C 언어로 이중 연결 리스트 자료 구조를 구현하는 방법을 배우게 됩니다. 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드 모두에 대한 포인터를 포함하는 연결 리스트의 한 유형으로, 정방향 및 역방향 모두에서 효율적인 탐색을 가능하게 합니다.
👀 미리보기
$ gcc test_list.c list.c -o test
$ ./test
welcome
to
labex
online
🎯 과제
이 프로젝트에서 다음을 배우게 됩니다:
- 이중 연결 리스트를 초기화하는 방법
- 이중 연결 리스트를 탐색하고 각 노드에 대해 콜백 함수를 실행하는 방법
- 이중 연결 리스트에서 주어진 노드 뒤에 새 노드를 삽입하는 방법
- 이중 연결 리스트에서 주어진 노드 앞에 새 노드를 삽입하는 방법
- 이중 연결 리스트에서 노드를 삭제하는 방법
🏆 성과
이 프로젝트를 완료하면 다음을 수행할 수 있습니다:
- 이중 연결 리스트의 기본 구조와 연산을 이해합니다.
- 이중 연결 리스트 관리에 필요한 핵심 함수를 구현합니다.
- C 언어에서 포인터와 동적 메모리 할당을 사용하는 능력을 보여줍니다.
- 제공된 이중 연결 리스트 구현을 수정하고 개선하기 위해 지식을 적용합니다.
세그멘테이션 오류 수정
이 단계에서는 free_list 함수가 노드를 해제한 후 current 포인터를 업데이트하지 않아 세그멘테이션 오류가 발생합니다. 이 문제를 지금 수정해야 합니다.
list.c파일에서free_list()함수를 찾습니다.- 업데이트된
free_list()함수는 다음과 같습니다:
void free_list(struct List* list) {
struct Node* current = list->head;
struct Node* next = NULL;
while (current) {
next = current->next;
free(current);
current = next; // Updated
}
free(list);
}
주어진 노드 뒤에 노드 삽입
이 단계에서는 이중 연결 리스트에서 주어진 노드 뒤에 새 노드를 삽입하는 방법을 배우게 됩니다.
list.c파일에서insert_after()함수를 찾습니다.- 이 함수는
struct List*,struct Node*(새 노드를 삽입할 노드), 그리고 새 노드의data를 인수로 받습니다. - 이 함수는 새로운
struct Node를 생성하고 제공된data로 해당data필드를 초기화해야 합니다. - 그런 다음 함수는 새 노드와
prev노드의next및prev포인터를 업데이트하여 새 노드를 올바르게 삽입해야 합니다. - 마지막으로, 새 노드가 리스트의 끝에 삽입되는 경우 함수는
tail포인터를 업데이트해야 합니다.
업데이트된 insert_after() 함수는 다음과 같습니다:
void insert_after(struct List* list, struct Node* prev, void* data) {
struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
newnode->data = data;
if (prev) { // Updated
newnode->next = prev->next;
newnode->prev = prev;
prev->next = newnode;
if (newnode->next) newnode->next->prev = newnode;
else list->tail = newnode; // Updated
} else {
newnode->next = list->head;
newnode->prev = NULL;
if (list->head) list->head->prev = newnode;
else list->tail = newnode; // Updated
list->head = newnode;
}
}
insert_after (list, NULL, data);를 찾아 다음 코드로 변경합니다:
insert_after (list, list->tail, data);
주어진 노드 앞에 노드 삽입
이 단계에서는 이중 연결 리스트에서 주어진 노드 앞에 새 노드를 삽입하는 방법을 배우게 됩니다.
list.c파일에서insert_before()함수를 찾습니다.- 이 함수는
struct List*,struct Node*(새 노드를 삽입할 노드), 그리고 새 노드의data를 인수로 받습니다. - 이 함수는 새로운
struct Node를 생성하고 제공된data로 해당data필드를 초기화해야 합니다. - 그런 다음 함수는 새 노드와
next노드의next및prev포인터를 업데이트하여 새 노드를 올바르게 삽입해야 합니다. - 마지막으로, 새 노드가 리스트의 시작 부분에 삽입되는 경우 함수는
head포인터를 업데이트해야 합니다.
업데이트된 insert_before() 함수는 다음과 같습니다:
void insert_before(struct List* list, struct Node* next, void* data) {
struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
newnode->data = data;
if (next) { // Updated
newnode->prev = next->prev;
newnode->next = next;
next->prev = newnode;
if (newnode->prev) newnode->prev->next = newnode;
else list->head = newnode; // Updated
} else {
newnode->prev = list->tail;
newnode->next = NULL;
if (list->tail) list->tail->next = newnode;
else list->head = newnode; // Updated
list->tail = newnode;
}
}
insert_before (list, NULL, data);를 찾아 다음 코드로 변경합니다:
insert_before (list, list->head, data);
이중 연결 리스트에서 노드 삭제
이 단계에서는 이중 연결 리스트에서 노드를 삭제하는 방법을 배우게 됩니다.
list.c파일에서delete_from()함수를 찾습니다.- 이 함수는
struct List*와struct Node*(삭제할 노드) 를 인수로 받습니다. - 이 함수는 주어진 노드를 리스트에서 제거하기 위해 인접 노드의
next및prev포인터를 업데이트해야 합니다. - 또한, 삭제된 노드가 리스트의
head또는tail인 경우 함수는head및tail포인터도 업데이트해야 합니다. - 마지막으로, 함수는 삭제된 노드가 차지하는 메모리를 해제해야 합니다.
업데이트된 delete_from() 함수는 다음과 같습니다:
void delete_from(struct List* list, struct Node* node) {
if (node->prev) node->prev->next = node->next;
else list->head = node->next; // Updated
if (node->next) node->next->prev = node->prev;
else list->tail = node->prev; // Updated
free(node);
}
이제 list.c 파일의 이중 연결 리스트 구현이 올바르게 작동해야 합니다. 제공된 test_list.c 파일을 사용하여 이중 연결 리스트의 기능을 테스트할 수 있습니다. 테스트 결과는 다음과 같습니다:
$ gcc test_list.c list.c -o test
$ ./test
welcome
to
labex
online
요약
축하합니다! 이 프로젝트를 완료했습니다. LabEx 에서 더 많은 랩을 연습하여 기술을 향상시킬 수 있습니다.
