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

0
This entry is part 7 of 10 in the series Cấu trúc dữ liệu

Ở bài viết trước, tôi đã hướng dẫn bạn cách cài đặt danh sách liên kết đơn và các kiến thức về danh sách liên kết. Bài viết này, mình sẽ hướng dẫn bạn cài đặt danh sách liên kết đôi nhé. Danh sách liên kết đôi có sự liên kết 2 chiều giữa 2 phần tử liền kề nhau trong khi danh sách liên kết đơn chỉ có liên kết 1 chiều.

1. Lý thuyết về Danh sách liên kết đôi

Một Node của danh sách liên kết đôi sẽ có dạng như sau:

Và hình dưới đây so sanh sự khác nhau giữ dslk đôi và dslk đơn:

Khác biệt giữa danh sách liên kết đơn với danh sách liên kết đôi
Khác biệt giữa danh sách liên kết đơn với danh sách liên kết đôi

2. Cài đặt danh sách liên kết đôi

2.1. Khai báo & khởi tạo

Khác một chút với dslk đơn, ngoài con trỏ next, chúng ta sẽ có thêm con trỏ prev để liên kết với Node trước nó. Chúng ta vẫn sẽ để data có kiểu int để đơn giản và dễ hiểu nhé.

Ngay sau khai báo, chúng ta sẽ khởi tạo Node đầu tiên của danh sách liên kết đôi.

2.2. Tạo mới 1 Node

Thay vì chỉ cho next = NULL và gán giá trị cho Node mới, chúng ta cũng phải cho con trỏ prev = NULL.

2.3. Thêm Node

Thêm vào đầu

  • Nếu head = NULL, ta sẽ cho cả head và tail = newNode.
  • Nếu head != NULL, ta sẽ cập nhật lại head mới là newNode. Ta cần tạo liên kết giữa head hiện tại với newNode trước khi cho newNode làm head mới.

Về cơ bản, ý tưởng thêm Node vào đầu/ cuối vẫn giống với thêm vào đầu trong danh sách liên kết đơn.

Thêm vào cuối

  • Nếu head = NULL, newNode sẽ là head và tail luôn
  • Nếu head != NULL, cập nhật lại tail mới là newNode. Ta cần tạo liên kết thằng tail hiện tại với newNode trước khi để newNode làm tail mới.

2.4. Xóa Node

Xóa ở đầu

  • Nếu head = NULL, chẳng có gì để xóa
  • Nếu head != NULL, cho head mới bằng phần tử tiếp theo và sửa prev của nó = NULL(ngắt liên kết với thằng head cũ).

Xóa ở cuối

  • Nếu head = NULL, chẳng có gì để xóa
  • Nếu head != NULL, cho tail mới bằng phần tử trước nó và sửa next của nó = NULL(ngắt liên kết với thằng tail cũ).

2.5. Duyệt danh sách liên kết

Duyệt từ đầu tới cuối

Ta sẽ duyệt bắt đầu từ Node head cho tới trước khi gặp Node NULL bằng cách dùng con trỏ next.

Duyệt từ cuối về đầu

Lần này, ta sẽ duyệt bắt đầu từ Node tailcho tới trước khi gặp Node NULL bằng cách dùng con trỏ prev.

3. Full code danh sách liên kết đôi

Kết quả chạy:

Series Navigation<< Danh sách liên kết đơn – Single linked listDanh sách liên kết vòng – Circular Linked List >>

ĐỂ 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