단일 링크 된 목록에서 요소 삭제

Question

function에서 value로 지정된 목록에서 일부 요소를 삭제하고 싶습니다. 함수의 'val'이 목록의 첫 번째 요소와 같으면 내 함수가 작동하지 않습니다. 그렇지 않으면 잘 작동합니다. 어떤 아이디어?

struct elem { 
    int val; 
    struct elem *next; 
}; 

void del(struct elem *list, int val) { 
    struct elem* tmp = list; 
    struct elem* prev = NULL; 

    while (tmp != NULL) { 
     if (tmp->val == val) { 
      if (prev == NULL) { 
       tmp = tmp->next; 
       free(list); 
       list = tmp; 
      } else { 
       prev->next = tmp->next; 
       free(tmp); 
       tmp = prev->next; 
      } 
     } else { 
      prev = tmp; 
      tmp = tmp->next; 
     } 
    } 
} 

Answer 1

호출 기능에서 list이 업데이트되었음을 ​​알 수 없습니다. 삭제 된 동일한 list을 참조 할 수도 있습니다. 어느 쪽이 좋지 않은가.

하나의 해결책은 struct elem **list로 목록을 전달하는 것입니다 :

void del(struct elem **list, int val) { 
    struct elem* tmp = *list; 
    struct elem* prev = NULL; 

    while (tmp != NULL) { 
     if (tmp->val == val) { 
      if (prev == NULL) { 
       tmp = tmp->next; 
       free(*list); 
       *list = tmp; 
      } else { 
       prev->next = tmp->next; 
       free(tmp); 
       tmp = prev->next; 
      } 
     } else { 
      prev = tmp; 
      tmp = tmp->next; 
     } 
    } 
} 

편집 : 다른 솔루션이 있습니다. 당신은 새 목록 포인터를 반환 할 수 있습니다 :

struct elem *del(struct elem *list, int val) { ... } 

을 그리고 당신은 다음과 같이 호출 :

이 솔루션은 list 통화에서 다소 중복되는 단점이있다

list = del(list, 12); 

과는 생략하는 법률입니다 결과적으로 목록을 업데이트하지 않습니다.

내가 좋아하는 솔루션은 목록에 대한 컨트롤 구조체를 정의하는 것입니다. 지금이 순간, 그건 그냥 헤드 포인터를 포함합니다 :

struct list { 
    struct elem *head; 
}; 

다음 인수로이 구조에 대한 포인터를 가지고 목록에서 작동 귀하의 기능 :

void del(struct list *list, int val) { 
    struct elem* tmp = list->head; 
    struct elem* prev = NULL; 

    while (tmp != NULL) { 
     if (tmp->val == val) { 
      if (prev == NULL) { 
       tmp = tmp->next; 
       free(list->head); 
       list->head = tmp; 
      } else { 
       prev->next = tmp->next; 
       free(tmp); 
       tmp = prev->next; 
      } 
     } else { 
      prev = tmp; 
      tmp = tmp->next; 
     } 
    } 
} 

struct list가 추가 필드를 가질 수에 대한 끝까지 빠르게 추가 할 수있는 꼬리 포인터. 목록 길이를 추적 할 수도 있습니다.