Xóa một nút trong danh sách liên kết đơn lẻ

Question

Làm thế nào để xóa một nút trong danh sách liên kết đơn lẻ chỉ với một con trỏ trỏ đến nút sẽ bị xóa?

[Bắt đầu và kết thúc con trỏ không được tiết lộ, thông tin có sẵn là con trỏ đến nút cần được xóa]

Answer 1

Bạn có thể xóa một nút mà không nhận được nút trước đó, bằng cách để nó bắt chước các nút sau và xóa mà một thay vào đó:

void delete(Node *n) { 
    if (!is_sentinel(n->next)) { 
    n->content = n->next->content; 
    Node *next = n->next; 
    n->next = n->next->next; 
    free(next); 
    } else { 
    n->content = NULL; 
    free(n->next); 
    n->next = NULL; 
    } 
} 

Như bạn có thể thấy, bạn sẽ cần phải xử lý đặc biệt cho phần tử cuối cùng. Tôi đang sử dụng một nút đặc biệt làm nút gửi để đánh dấu kết thúc có content và next là NULL.

UPDATE: các dòng Node *next = n->next; n->next = n->next->next cơ bản shuffles nội dung nút, và giải phóng các nút: Hình ảnh mà bạn nhận được một tham chiếu đến nút B để được xóa trong:

A   /To be deleted 
    next ---> B 
       next ---> C 
          next ---> *sentinel* 

Bước đầu tiên là n->content = n->next->content: sao chép nội dung của nút sau vào nút để được "xóa":

A   /To be deleted 
    next ---> C 
       next ---> C 
          next ---> *sentinel* 

sau đó, thay đổi next điểm:

A   /To be deleted 
    next ---> C  /---------------- 
       next ---| C   | 
          next ---> *sentinel* 

kế website thực sự miễn phí các yếu tố sau đây, nhận được đối với trường hợp cuối cùng:

A   /To be deleted 
    next ---> C 
       next ---> *sentinel* 

Answer 2

Các chỉ hợp lý và an toàn tùy chọn dưới những hạn chế như vậy là để đánh dấu nút xóa mà không thực sự bỏ liên kết nó, trì hoãn mà đến một thời gian sau đó.

Answer 3

Không thể.

Có nhiều lỗi để bắt chước quá trình xóa.

Nhưng không ai trong số đó thực sự sẽ xóa nút mà con trỏ trỏ đến.

Giải pháp phổ biến của xóa sau nút và sao chép nội dung của nó đến thực tế nút để bị xóa có tác dụng phụ nếu bạn có con trỏ bên ngoài trỏ đến nút trong danh sách, trong trường hợp một mà con trỏ bên ngoài trỏ đến nút sau sẽ trở nên lơ lửng.

Bạn có thể tìm thấy một số cuộc thảo luận về SO here.