포인터를 사용하여 단일 연결 목록에서 항목 제거
최근 Slashdot 인터뷰에서 Linus Torvalds는 일부 사람들이 포인터를 올바르게 사용하는 방법을 제대로 이해하지 못하는 방식으로 어떻게 사용하는지에 대한 예를 들었다.
불행히도 나는 그가 말하는 사람 중 한 명이기 때문에 그의 예를 이해하지 못했다.
"prev" 엔트리를 추적하여 단일 링크 리스트 엔트리를 삭제한 후 엔트리를 삭제하는 사람들을 너무 많이 보았습니다.
if (prev) prev->next = entry->next; else list_head = entry->next;그런 코드만 보면 '이 사람은 포인터를 몰라' 이러면서그리고 슬프게도 꽤 흔합니다.포인터를 이해하는 사람들은 "엔트리 포인터 포인터"를 사용하여 list_head 주소로 초기화합니다.그런 다음 목록을 이동할 때 조건 없이 다음과 같은 방법으로 항목을 제거할 수 있습니다.
*pp = entry->next
누가 이 방법이 왜 더 좋은지, 그리고 조건문 없이 어떻게 작동할 수 있는지에 대해 좀 더 설명해 줄 수 있나요?
예를 들어 배우는 것을 좋아하신다면 제가 하나 준비했습니다.다음과 같은 단일 링크 목록이 있다고 가정합니다.
다음과 같이 표시됩니다(클릭하면 확대됩니다).
.value = 8.
코드
이를 위한 간단한 코드는 다음과 같습니다.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
struct node_t {
int value;
node_t *next;
};
node_t* create_list() {
int test_values[] = { 28, 1, 8, 70, 56 };
node_t *new_node, *head = NULL;
int i;
for (i = 0; i < 5; i++) {
new_node = malloc(sizeof(struct node_t));
assert(new_node);
new_node->value = test_values[i];
new_node->next = head;
head = new_node;
}
return head;
}
void print_list(const node_t *head) {
for (; head; head = head->next)
printf("%d ", head->value);
printf("\n");
}
void destroy_list(node_t **head) {
node_t *next;
while (*head) {
next = (*head)->next;
free(*head);
*head = next;
}
}
void remove_from_list(int val, node_t **head) {
node_t *del, **p = head;
while (*p && (**p).value != val)
p = &(*p)->next; // alternatively: p = &(**p).next
if (p) { // non-empty list and value was found
del = *p;
*p = del->next;
del->next = NULL; // not necessary in this case
free(del);
}
}
int main(int argc, char **argv) {
node_t *head;
head = create_list();
print_list(head);
remove_from_list(8, &head);
print_list(head);
destroy_list(&head);
assert (head == NULL);
return EXIT_SUCCESS;
}
이 코드를 컴파일하여 실행하면 다음과 같은 결과를 얻을 수 있습니다.
56 70 8 1 28
56 70 1 28
코드의 설명
**pdouble'*head★★★★★★★★★★★★★★★★★★:
이번에는 어떻게 분석하면 void remove_from_list(int val, node_t **head)하다.head하 *p && (**p).value != val.
에는 이음음음음음음음음음음음음음음음음이 포함되어 있습니다.value 것( 하고 싶은 것)8의 두 후.while (*p && (**p).value != val) '''(**p).value becomes가 되다8그래서 반복을 멈추죠.
:*p를 node_t *next의 범위 내에서node_t그 전이다node_t 것( 하고 싶은 것)**p을할 수 에 매우 합니다.이것에 의해, 다음의 정보를 변경할 수 있기 때문입니다.*nextnode_t에 있어요.node_t삭제하려고 하는 경우, 리스트에서 실질적으로 삭제됩니다.
를 할당해 del->value == 8에 접속합니다.*del포인터
부분은 요.*p가 「」가 되도록 .**p그 다음 한 가지 요소를 가리키고 있었다. *del다음 중 하나:
에서는 「 」라고 부릅니다.free(del) , 、 를 、 를 、 , 、 , 、 , , , 。del->next로로 합니다.NULL하지 않고 '마음'을 '마음'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으'으del->next = NULL:
처음에는, 당신은 한다.
pp = &list_head;
목록을 탐색할 때 이 "예측"을 다음과 같이 진행합니다.
pp = &(*pp)->next;
이렇게 하면 항상 "당신의 출신" 지점을 추적하고 해당 지점에 있는 포인터를 수정할 수 있습니다.
삭제할 엔트리를 찾으면 다음 작업을 수행할 수 있습니다.
*pp = entry->next
이렇게 하면 Afaq가 또 다른 답변에서 언급한 3가지 사례를 모두 처리할 수 있으며, 이를 통해 Afaq가 언급한 3가지 사례를 효과적으로 제거할 수 있습니다.NULLprev.
제 생각은 이렇습니다. 저는 이런 식으로 이해하는 것이 더 쉽다는 것을 알았습니다.
포인터에 대한 포인터를 사용하여 링크 목록에서 노드를 삭제하는 예.
struct node {
int value;
struct node *next;
};
void delete_from_list(struct node **list, int n)
{
struct node *entry = *list;
while (entry && entry->value != n) {
// store the address of current->next value (1)
list = &entry->next;
// list now stores the address of previous->next value
entry = entry->next;
}
if (entry) {
// here we change the previous->next value
*list = entry->next;
free(entry);
}
}
다음 값을 사용하여 목록을 작성한다고 가정합니다.
*node value next
----------------------------------------
a 1 null
b 2 a
c 3 b
d 4 c
e 5 d
값이 3인 노드를 삭제하는 경우:
entry = e
while (entry && entry->value != 3) iterations:
e->value != 3
list = &e->next
entry = d
d->value != 3
list = &d->next
entry = c
c->value == 3
STOP
if (entry)
d->next = b (what was 'list' is dereferenced)
free(entry)
★★★ if (entry)하다
d->next = b
리스트는 다음과 같습니다.
*node value next
----------------------------------------
a 1 null
b 2 a
c 3 b
d 4 b
e 5 d
그리고 마지막으로:
free(entry)
리스트는 다음과 같습니다.
*node value next
----------------------------------------
a 1 null
b 2 a
d 4 b
e 5 d
첫 번째 노드를 삭제해도 동작합니다.처음에는
*list == entry
그 때문에, 다음과 같이 합니다.
*list = entry->next;
*list두 번째 요소를 가리킵니다.
(1) 다음 문구에 주의한다.
list = &entry->next;
다음과 같습니다.
list = &(entry->next);
함수 호출을 사용하여 일치하는 요소를 삭제하는 완전한 코드 예를 다음에 나타냅니다.
rem()를 사용하여 요소를 합니다.rem2()」를 사용해 일치하는 요소를 삭제합니다.
// code.c
#include <stdio.h>
#include <stdlib.h>
typedef struct list_entry {
int val;
struct list_entry *next;
} list_entry;
list_entry *new_node(list_entry *curr, int val)
{
list_entry *new_n = malloc(sizeof(list_entry));
if (new_n == NULL) {
fputs("Error in malloc\n", stderr);
exit(1);
}
new_n->val = val;
new_n->next = NULL;
if (curr) {
curr->next = new_n;
}
return new_n;
}
#define ARR_LEN(arr) (sizeof(arr)/sizeof((arr)[0]))
#define CREATE_LIST(arr) create_list((arr), ARR_LEN(arr))
list_entry *create_list(const int arr[], size_t len)
{
if (len == 0) {
return NULL;
}
list_entry *node = NULL;
list_entry *head = node = new_node(node, arr[0]);
for (size_t i = 1; i < len; ++i) {
node = new_node(node, arr[i]);
}
return head;
}
void rem(list_entry **head_p, int match_val)
// remove and free all entries with match_val
{
list_entry *prev = NULL;
for (list_entry *entry = *head_p; entry; ) {
if (entry->val == match_val) {
list_entry *del_entry = entry;
entry = entry->next;
if (prev) {
prev->next = entry;
} else {
*head_p = entry;
}
free(del_entry);
} else {
prev = entry;
entry = entry->next;
}
}
}
void rem2(list_entry **pp, int match_val)
// remove and free all entries with match_val
{
list_entry *entry;
while ((entry = *pp)) { // assignment, not equality
if (entry->val == match_val) {
*pp = entry->next;
free(entry);
} else {
pp = &entry->next;
}
}
}
void print_and_free_list(list_entry *entry)
{
list_entry *node;
// iterate through, printing entries, and then freeing them
for (; entry != NULL; node = entry, /* lag behind to free */
entry = entry->next,
free(node)) {
printf("%d ", entry->val);
}
putchar('\n');
}
#define CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val) createList_removeMatchElems_print((arr), ARR_LEN(arr), (match_val))
void createList_removeMatchElems_print(const int arr[], size_t len, int match_val)
{
list_entry *head = create_list(arr, len);
rem2(&head, match_val);
print_and_free_list(head);
}
int main()
{
const int match_val = 2; // the value to remove
{
const int arr[] = {0, 1, 2, 3};
CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
}
{
const int arr[] = {0, 2, 2, 3};
CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
}
{
const int arr[] = {2, 7, 8, 2};
CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
}
{
const int arr[] = {2, 2, 3, 3};
CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
}
{
const int arr[] = {0, 0, 2, 2};
CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
}
{
const int arr[] = {2, 2, 2, 2};
CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
}
{
const int arr[] = {};
CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
}
return 0;
}
동작 코드는, 여기를 참조해 주세요.
- gcc https://wandbox.org/permlink/LxgMddqCZWyj7lMI
- clang https://wandbox.org/permlink/5aEkxh24sGfAecwF
다음과 같이 valgrind(메모리 누전 검사기)를 컴파일하여 사용하는 경우:
gcc -std=c11 -Wall -Wextra -Werror -o go code.c && valgrind ./go
든든는 는는는 는는는는 는는 는는는는
첫 번째 방법에서는 노드를 목록에서 링크 해제하여 삭제합니다.
두 번째 방법에서는 삭제할 노드를 다음 노드로 바꿉니다.
두 번째 접근법은 코드를 우아하게 단순화시킨 것 같습니다.확실히 두 번째 접근방식에서는 링크 리스트와 기본 계산 모델을 더 잘 이해할 필요가 있습니다.
주의: 매우 관련성이 있지만 약간 다른 코딩 질문이 있습니다.이해도 테스트에 최적:https://leetcode.com/problems/delete-node-in-a-linked-list/
나는 더미 노드 접근방식을 선호한다. 예를 들어 레이아웃:
|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL
^ ^
| |
curr curr->next // << toDel
삭제할 노드로 이동합니다(toDel = curr > next )
tmp = curr->next;
curr->next = curr->next->next;
free(tmp);
이렇게 하면 첫 번째 요소가 항상 더미이고 삭제되지 않기 때문에 첫 번째 요소가 첫 번째 요소인지 확인할 필요가 없습니다.
노드를 삭제한 후 목록을 다시 연결하는 것이 더 중요합니다.적어도 3가지 경우를 생각해 봅시다.
1. 노드를 처음부터 삭제합니다.
2. 중간에서 노드를 제거합니다.
3. 끝에서 노드를 삭제합니다.
처음부터 삭제
목록의 선두에 있는 노드를 삭제할 때 첫 번째 노드에 선행 노드가 없기 때문에 실행할 노드의 재링크는 없습니다.예를 들어 다음과 같은 노드를 삭제합니다.
link
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
단, 리스트의 선두에 포인터를 고정해야 합니다.
link
|
+-------------+
|
v
--------- --------- ---------
| a | --+---> | b | --+---> | c | 0 |
--------- --------- ---------
중간에서 제거
중간에서 노드를 제거하려면 이전 노드가 제거할 노드를 건너뛸 필요가 있습니다.예를 들어, b:가 있는 노드를 삭제합니다.
link
|
v
--------- --------- ---------
| a | --+--+ | b | --+---> | c | 0 |
--------- | --------- ---------
| ^
+----------------+
즉, 삭제할 노드보다 먼저 노드를 참조할 수 있는 방법이 필요합니다.
끝에서 삭제
노드를 끝에서 삭제하려면 이전 노드가 목록의 새로운 끝이 되어야 합니다(즉, 그 뒤에 아무것도 표시되지 않음).예를 들어, c: 를 사용하여 노드를 삭제합니다.
link
|
v
--------- --------- ---------
| a | --+---> | b | 0 | | c | 0 |
--------- --------- ---------
마지막 2개의 케이스(중간과 끝)는 "삭제하는 노드 앞의 노드가 삭제할 노드를 가리켜야 한다"고 함으로써 조합할 수 있습니다.
@gll:
나는 다음과 같이 간단한 예를 썼다.이게 왜 효과가 있는지 봐주셨으면 좋겠어요.
기능 중void delete_node(LinkedList *list, void *data), 나는 사용하고 있습니다.*pp = (*pp)->next;그리고 그것은 동작한다.솔직히, 왜 이게 효과가 있는지 모르겠어요.포인터 도표까지 그려도 이해가 안 돼요.확실히 해 주셨으면 합니다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _employee {
char name[32];
unsigned char age;
} Employee;
int compare_employee(Employee *e1, Employee *e2)
{
return strcmp(e1->name, e2->name);
}
typedef int (*COMPARE)(void *, void *);
void display_employee(Employee *e)
{
printf("%s\t%d\n", e->name, e->age);
}
typedef void (*DISPLAY)(void *);
typedef struct _node {
void *data;
struct _node *next;
} NODE;
typedef struct _linkedlist {
NODE *head;
NODE *tail;
NODE *current;
} LinkedList;
void init_list(LinkedList *list)
{
list->head = NULL;
list->tail = NULL;
list->current = NULL;
}
void add_head(LinkedList *list, void *data)
{
NODE *node = malloc(sizeof(NODE));
node->data = data;
if (list->head == NULL) {
list->tail = node;
node->next = NULL;
} else {
node->next = list->head;
}
list->head = node;
}
void add_tail(LinkedList *list, void *data)
{
NODE *node = malloc(sizeof(NODE));
node->data = data;
node->next = NULL;
if (list->head == NULL) {
list->head = node;
} else {
list->tail->next = node;
}
list->tail = node;
}
NODE *get_node(LinkedList *list, COMPARE compare, void *data)
{
NODE *n = list->head;
while (n != NULL) {
if (compare(n->data, data) == 0) {
return n;
}
n = n->next;
}
return NULL;
}
void display_list(LinkedList *list, DISPLAY display)
{
printf("Linked List\n");
NODE *current = list->head;
while (current != NULL) {
display(current->data);
current = current->next;
}
}
void delete_node(LinkedList *list, void *data)
{
/* Linus says who use this block of code doesn't understand pointer.
NODE *prev = NULL;
NODE *walk = list->head;
while (((Employee *)walk->data)->age != ((Employee *)data)->age) {
prev = walk;
walk = walk->next;
}
if (!prev)
list->head = walk->next;
else
prev->next = walk->next; */
NODE **pp = &list->head;
while (((Employee *)(*pp)->data)->age != ((Employee *)data)->age) {
pp = &(*pp)->next;
}
*pp = (*pp)->next;
}
int main ()
{
LinkedList list;
init_list(&list);
Employee *samuel = malloc(sizeof(Employee));
strcpy(samuel->name, "Samuel");
samuel->age = 23;
Employee *sally = malloc(sizeof(Employee));
strcpy(sally->name, "Sally");
sally->age = 19;
Employee *susan = malloc(sizeof(Employee));
strcpy(susan->name, "Susan");
susan->age = 14;
Employee *jessie = malloc(sizeof(Employee));
strcpy(jessie->name, "Jessie");
jessie->age = 18;
add_head(&list, samuel);
add_head(&list, sally);
add_head(&list, susan);
add_tail(&list, jessie);
display_list(&list, (DISPLAY) display_employee);
NODE *n = get_node(&list, (COMPARE) compare_employee, sally);
printf("name is %s, age is %d.\n",
((Employee *)n->data)->name, ((Employee *)n->data)->age);
printf("\n");
delete_node(&list, samuel);
display_list(&list, (DISPLAY) display_employee);
return 0;
}
출력:
Linked List
Susan 14
Sally 19
Samuel 23
Jessie 18
name is Sally, age is 19.
Linked List
Susan 14
Sally 19
Jessie 18
언급URL : https://stackoverflow.com/questions/12914917/using-pointers-to-remove-item-from-singly-linked-list
'programing' 카테고리의 다른 글
| vuex 저장소에 데이터의 json을 로드하고 구성 요소에 액세스 (0) | 2022.07.17 |
|---|---|
| Jest + Vue - SyntaxError:예기치 않은 토큰 < (0) | 2022.07.17 |
| 기능 선언을 위한 대체(K&R) C 구문과 프로토타입 (0) | 2022.07.17 |
| C/C++ 단위의 결합 크기 (0) | 2022.07.17 |
| IntelliJ는 사용방법에 대한 메서드 파라미터 힌트를 보여줍니다.사용하지 않는 방법 (0) | 2022.07.17 |