DSLK đôi là gì? Cấu trúc dữ liệu của DSLK đôi

Trong bài viết này, codehow sẽ giới thiệu đến các bạn DSLK đôi là gì? Cấu trúc dữ liệu của DSLK đôi trong C / C++. Đây là một loại danh sách liên kết trong ba loại bao gồm có danh sách liên kết đơn và danh sách liên kết vòng.

Về cơ bản thì DSLK đôi là một DSLK đơn, nếu các bạn đã học qua DSLK đơn ở các bài viết trước của mình thì việc học DLSK đôi khá đơn giản. Còn nếu các bạn chưa xem qua, cũng đừng lo lắng nhé, mình sẽ nhắc lại trong bài nếu có đụng đến nó.

Còn bây giờ chúng ta sẽ bắt đầu tìm hiểu DSLK đổi là gì? Cấu trúc dữ liệu của DSLK đôi. Các thao tác thường sử dụng trong DSLK đôi.

Danh sách liên kết đôi là gì?

Khác với DSLK đơn, chỉ có một mối liên kết tới node phía sau nó mà thôi.

Đối với node đầu trong DSLK đôi sẽ trỏ tới NULL, tương tự như vậy node cuối của DSLK đôi sẽ trỏ tới NULL.

Khi thực hiện thao tác duyệt danh sách thì sẽ thực hiện theo hai chiều đó là từ trước về sau và từ sau lên trước. Khác với DSLK đơn chỉ duyệt danh sách theo một chiều mà thôi.

Đối với một node trong DSLK đôi, ta cũng sẽ cần lưu ý đến hai thông số đó là:

• Giá trị của node (data).
• Mối liên kết tới node sau và node trước (pNext & pPre).

Khác với DSLK đơn, chỉ có một mối liên kết duy nhất tới node sau là pNext. DSLK đôi có tới hai mối liên kết là pNext và pPre.

Cấu trúc dữ liệu của DSLK đôi

Bất kì danh sách liên kết nào cũng cần có cấu trúc dữ liệu để lưu trữ dữ liệu. Vậy nên chúng ta vẫn phải tìm hiểu về cách khai báo và khởi tạo cấu trúc dữ liệu của DSLK đôi.

Về cấu trúc dữ liệu, ta cần quan tâm đến hai cấu trúc đó là:

• Cấu trúc node.
• Cấu trúc DSLK đôi.

Bây giờ chúng ta sẽ đi vào tìm hiểu từng cấu trúc nhé.

Cấu trúc node

Đối với cấu trúc của một node, ta cần quan tâm đến ba thông số đó là: pPre, data, pNext. Như hình dưới đây:

Trong đó:

• pPre: Đây là mối liên kết đến node phía trước nó. Trong trường hợp đây là node đầu thì mối liên kết này sẽ trỏ tới NULL.
• data: Đây là giá trị của node.
• pNext: Đây là mối liên kết đến node phía sau nó. Trong trường hợp đây là node cuối thì nối liên kết này sẽ trỏ tới NULL.

Cấu trúc của node như sau:

struct Node  {
    int data;
    struct Node* next;
    struct Node* prev;
};

Cấu trúc DSLK đôi

Đối với cấu trúc của DSLK đôi, ta cần quan tâm đến hai yếu tố đó là: pHead (node đầu) và pTail (node cuối).

Trong đó:

• pHead: Đây là node đầu tiên trong DSLK đôi, có nhiệm vụ quản lý node đầu.
• pTail: Đây là node cuối cùng trong DSLK đổi, có nhiện vụ quản lý node cuối.
• Node A: Có hai con trỏ trỏ đến node B phía sau và trỏ tới NULL phía trước.
• Node B: Có hai con trỏ trỏ đến node C phía sau và node A phía trước. Tương tự như vậy cho node C.
• Node D: Có hai con trỏ trỏ đến NULL phía sau và trỏ đến node C phía trước.

Khai báo cấu trúc DSLK đôi sử dụng pHead và pTail để cài đặt và quản lý.

/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
  Node *pHead; //Node đầu pHead
  Node *pTail; // Node cuối pTail
};

Khởi tạo giá trị null cho pHead và pTail.

void Initialize(SingleList &list)
{
  list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}

Các thao tác thường gặp trong DSLK đôi

Khi làm việc với DSLK đơn, chúng ta thường gặp các thao tác như thêm, xóa, ... . Đối với DSLK đôi cũng vậy, ta cũng có một số thao tác tương tự cụ thể dưới đây:

• Tạo node mới trong DSLK đôi.
• Chèn node trong DSLK đôi.
  • Chèn vào đầu danh sách.
  • Chèn vào cuối danh sách.
• Xóa node trong DSLK đôi.
  • Xóa node đầu.
  • Xóa node cuối.
• Duyệt danh DSLK đôi.
  • Duyệt từ đầu về cuối.
  • Duyệt từ cuối về đầu.
• Tìm kiếm trong DSLK đôi.
• Sắp xếp trong DSLK đôi.

Bởi vì DSLK đôi có thể duyệt theo hai chiều, vậy nên dựa vào bài toán chúng ta có thể lựa chọn cách duyệt cho phù hợp và tối ưu. Tránh trường hợp phần tử cần lấy ở cuối, mà ta phải duyệt từ đầu danh sách, điều này rất mất thời gian.

Kết luận

Như vậy là chúng ta đã cùng nhau tìm hiểu về danh sách liên kết đôi là gì? Cấu trúc của danh sách liên kết đôi. Qua bài viết này, mình muốn các bạn nắm rõ một số kiến thức sau đây:

• Danh sách liên kết đôi là danh sách liên kết mà mỗi phần tử được liên kết phần tử phía trước và phía sau nó.
• Một node bao gồm 2 thành phần đó là data và mối liên kết (pPre & pNext).
• Cấu trúc dữ liệu của DSLK đôi bao gồm hai cấu trúc đó là cấu trúc node và cấu trúc DSLK đôi. Cần khỏi tạo giá trị NULL cho các node pHead và pTail trong cấu trúc DSLK đôi.
• DSLK đôi có các thao tác như thêm, xóa, sắp xếp, tìm kiếm, ... .

Ở bài tiếp theo, mình sẽ hướng dẫn các bạn cách tạo node mới trong DSLK đôi. Các bạn chú ý theo dõi nhé, cảm ơn các bạn rất nhiều.