C++ Data Structure: Doubly Linked List.

Hi, xin chào các bạn. 

Trong bài trước chúng ta đã tìm hiểu về linked list cơ bản, và đó được coi như là một singly linked list.

Khi đã hiểu được nguyên lý của single linked list, chúng ta hoàn toàn có thể phát triển và mở rộng hơn.

Bài hôm nay chúng ta cùng tìm hiểu và xây dựng douby linked list.

1. LÝ THUYẾT CƠ BẢN VỀ DOUBLY LINKED LIST.

Là một dạng mở rộng hơn so với singly linked list. Và nó có nhiều ưu điểm hơn.

– Một phần tử có thể được liên kết theo hai chiều, trước và sau. 

Nghĩa là từ một phần từ bạn có thể tìm được phần tử kế tiếp nó, và trước nó.

– Việc xóa bỏ node cũng hiệu quả hơn.

– Có thể chèn một node mới trước một node cố định, và có 4 kiểu chèn cơ bản trong doubly linked list.

+ Chèn trước danh sách.

+ Chèn sau danh sách.

+ Chèn trước một node xác định.

+ Chèn sau một node xác định.

 

Chúng ta hãy cùng xem hình minh họa cho doubly linked list.

 

2. TRIỂN KHAI DOUBLY LINKED LIST VỚI CODE C++

a. Xây dựng class NodeData theo template tổng quát.

 

b. Xây dựng class Doubly Linked List với 4 phương thức chèn.

 

c. Sử dụng doubly linked list với kiểu dữ liệu Person.

Chúng ta sẽ thấy như sau.

  • A sẽ được chèn vào đâu tiên => danh sách là A
  • B sẽ được chèn tiếp vào đầu => danh sách là B A
  • C sẽ được chèn vào cuối => Danh sách là B A C
  • Sau đó tìm phần tử head là B. => next phần từ head là A.

pMid là A.

  • Chèn MID_BE  và trước của A => danh sách sẽ là  B  MID_BE A C
  • Sau đó chèn MID_AF  vào sau của A => danh sách là B MID_BE A MID_AF C.

Kết quả chương trình chạy như sau:

Như vậy doubly linked link có sự linh hoạt hơn trong việc kiểm soát danh sách liên kết.

Chúng ta có thể dễ dàng chèn được các phần tử mới theo 4 cách.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.