Danh sách liên kết đơn
Xây dựng danh sách liên kết bởi liên kết các node với nhau.
Điểm mạnh:
Danh sách liên kết có kích thước động, có thể mở rộng hay thu hẹp rất dễ ràng. Việc chèn hay xóa một phần tử trong danh sách liên kết là rất dễ dàng, ta chỉ cần thay đổi vị trí trỏ của các con trỏ thay vì phải dịch toàn bộ phần dữ liệu còn lại. Xem ví dụ sau khi ta muốn chèn node C vào giữa node A và B:
Trước khi chèn:
Sau khi chèn:
Điểm yếu:
Danh sách liên kết mang yếu điểm của cấp phát động về hiệu năng. Điều này cũng dễ hiểu vì mảng có vị trí bộ đệm tốt hơn [là các khối các ô nhớ liên tiếp] so với danh sách liên kết. Ta không thể truy cập ngẫu nhiên một phần tử trong danh sách liên kết ngay lập tức, mà phải thực hiện duyệt từ đầu danh sách cho tới khi gặp phần tử đó. Do vậy ta không thể thực hiện tìm kiếm nhị phân với các danh sách liên kết. - Cần thêm không gian bộ nhớ cho con trỏ trong mỗi phần tử của danh sách liên kết.
Xây dựng danh sách liên kết đơn với C/C++
Các node: Mỗi node bao gồm hai thành phần: phần dữ liệu và phần liên kết là một con trỏ để trỏ tới vị trí của node tiếp theo, nói cách khác, con trỏ này có giá trị là địa chỉ của node tiếp theo. Node cuối cùng của danh sách liên kết sẽ trỏ tới NULL, tức là không trỏ tới đâu cả. struct node { int data; /* Phần dữ liệu của một node*/ struct node* next; /* Con trỏ tới node kế tiếp */ };Con trỏ head để trỏ tới vị trí đầu tiên của danh sách liên kết. struct node * head; /* Con trỏ tới head node */
Tạo một node mới và trả về con trỏ tới node đó. /* Tạo một node mới và trả về con trỏ tới node đó. */ struct node* NewNode[int x] { struct node* new_node = [struct node*]malloc[sizeof[struct node]]; /* Cấp phát bộ nhớ cho node */ new_node->data = x; new_node->next = NULL; return new_node; }- Chèn một phần tử vào danh sách. /* Chèn node vào vị trí cuối của danh sách liên kết */ void InsertAtTail[int x] { struct node* temp = head; /* Tạo ra một con trỏ tạm, tránh trực tiếp làm thay đổi vị trí trỏ của con trỏ head */ struct node* new_node = NewNode[x]; /* Tạo ra một node mới với phần dữ liệu là tham số được truyền vào */ if[head == NULL] { /* Nếu danh sách rỗng, con trỏ head sẽ trỏ tới node được chèn vào danh sách */ head = new_node; return; } while[temp->next != NULL] temp = temp->next; /* Đi tới vị trí cuối cùng của danh sách */ temp->next = new_node; /* Chèn node mới vào cuối danh sách */ }
- Xóa một phần tử khỏi danh sách. struct node* Delete[struct node *head, int position] { struct node *prev = NULL; /* Con trỏ lưu node ngay trước node cần xóa */ struct node *ptr = head; /* Tạo ra bản sao của con trỏ head, tránh làm thay đổi vị trí trỏ của con trỏ head khi duyệt danh sách*/ int pos = 0; /* Biến lưu vị trí các phần tử trong danh sách */ if[position==0] /* Trường hợp xóa phần tử ở đầu danh sách */ { head=head->next; /* Trả về vị trí của phần tử tiếp theo, vị trí trỏ của head thay đổi */ free[ptr]; /* Thu hồi bộ nhớ của phần tử cần được xóa */ } else { while[position!=pos] /*Duyệt danh sách, lặp cho tới khi tìm thấy vị trí cần xóa */ { ++pos; prev=ptr; ptr=ptr->next; } /* Sau vòng lặp tìm được node cần xóa là ptr, địa chỉ node ngay trước node cần xóa được lưu trữ trong prev */ if[ptr!=NULL] /* Nếu tìm tháy node cần xóa trong danh sách, thực hiện xóa */ { prev->next=ptr->next; free[ptr]; } } return head; }
- Hiển thị tất cả các node trong danh sách. void Display[] { struct node* temp = head; while[temp != NULL] { printf["%d ",temp->data]; temp = temp->next; } printf["\n"]; }
Cấu trúc trên chính là cấu trúc của danh sách liên kết kép.
In danh sách theo vị trí đảo ngược . Phát hiện điểm nối của danh sách liên kết . Xóa các node trùng lặp trong danh sách . - So sánh hai danh sách liên kết
. Kết hợp hai danh sách đã được sắp xếp .