Cách cài đặt danh sách liên kết đơn trong c++

0
7

Bài viết hôm này mình sẽ hướng dẫn các bạn cách cài đặt danh sách liên kết đơn sử dụng code c++.

Danh sách liên kết đơn là gì ? Danh sách liên kết đơn là một cấu trúc dữ liệu thường dùng trong các ngôn ngữ lập trình.

Các bạn có thể xem hình dưới đây biểu diễn cho một danh sách liên kết đơn

Danh-sach-lien-ket-don
Danh sách liên kết đơn

Ở mỗi khối trên ta gọi là một nút ( node ), mỗi node sẽ chứa data để lưu trữ dữ liệu và một thuộc tính next dùng để tham chiếu tới phần tử tiếp theo. Đặc biệt sẽ không có khối nào tham chiếu đến node đầu ( gọi là head ), và node cuối cùng sẽ tham chiếu đến vùng NULL.

 

Các hoạt động cơ bản

Một danh sách liên kết ( link list ) sẽ có các thuộc tính cơ bản sau:

  • Hoạt động isEmpty(): Kiểm tra có rỗng hay không.
  • Hoạt động length(): Đếm số lượng node của link list.
  • Hoạt động insertFirst(): Chèn phần tử vào đầu link list.
  • Hoạt động deleteFirst(): Xóa phần tử đầu tiên của link list.
  • Hoạt động insert(int position, type Item): Chèn một node vào vị trí position.
  • Hoạt động Delete(int position): Xóa node tại vị trí position.
  • Hoạt động show(): Hiển thị tất cả dữ liệu trong link list.

Cài đặt danh sách liên kết đơn

Một danh sách liên kết đơn giản sẽ gồm hai thuộc tính:

  • Data dùng để chứa dữ liệu.
  • Next là con trỏ tham chiếu đến phần tử sau nó.

Tạo một node head ( Tức là node đầu ) với giá trị NULL.

Cài đặt hoạt động isEmpty()

Cài đặt hoạt động show()

Ở đây mình dùng một con trỏ ptr để duyệt các node trong link list.

Cài đặt hoạt động length()

Hoạt động length() sẽ trả về một giá trị kiểu int là kích thước của link list.

Cài đặt hoạt động insertFirst()

Danh-sach-lien-ket-don
Cách chèn một phần tử vào đầu Link list.

Đầu tiên ta sẽ tạo một node để chứa data, sau đó ta sẽ cho next tham chiếu đến head. Sau khi chèn xong thì ta cũng phải thay đổi con trỏ head, giờ đây nó sẽ trỏ đến node vừa chèn.

Cài đặt hoạt động deleteFirst()

Danh-sach-lien-ket-don
Cách xóa phần tử đầu.

Ta đơn giản chỉ tham chiếu head đến node thứ hai mà thôi.

Hoạt động này sẽ trả về node vừa xóa.

Cài đặt hoạt động insert()

Danh-sach-lien-ket-don
Chèn một phần tử vào vị trí.

Đầu tiên ta cần duyệt đến phần tử position - 1 sau đó tiến hành tham chiếu next phần tử node cần chèn. Phần tử vừa chèn cũng tham chiếu đến phần tử node position.

Cài đặt hoạt động Delete()

Danh-sach-lien-ket-don
Cách xóa một phần tử.

Ta sẽ duyệt đến phần tử thứ position - 1 , sau đó lấy con trỏ next tham chiếu đến phần tử thứ position + 1.

Chạy thử link list

Ở phần dưới mình chỉ copy lại các đoạn code trong hàm main mà thôi. Các bạn có thể xem full code tại đây.

Bài viết mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !

 

 

 

ĐỂ LẠI BÌNH LUẬN

Vui lòng nhập nội dung bình luận
Vui lòng nhập tên