Chương 3: DANH SÁCH ĐƯỢC LIÊN KẾT – 3. Danh sách được liên kết kép

Tram Ho

3.7 Doubly Linked Lists

Ưu điểm của doubly linked list – danh sách liên kết kép (còn được gọi là danh sách liên kết hai chiều) là với một nút trong danh sách, chúng ta có thể điều hướng theo cả hai hướng.
Không thể xóa một nút trong singly linked list trừ khi chúng ta có con trỏ tới nút phía trước của nó.
Nhưng trong danh sách được liên kết kép, chúng ta có thể xóa một nút ngay cả khi chúng ta không có địa chỉ của nút trước đó (vì mỗi nút có một con trỏ bên trái trỏ đến nút trước đó và có thể di chuyển ngược lại).
Những nhược điểm chính của danh sách được liên kết kép là:

  • Mỗi nút yêu cầu thêm một con trỏ, đòi hỏi nhiều không gian bộ nhớ hơn.
  • Việc chèn hoặc xóa một nút mất nhiều thời gian hơn (nhiều thao tác tới con trỏ hơn).

Tương tự như một danh sách được liên kết đơn, chúng ta triển khai các hoạt động của một danh sách được liên kết kép.
Nếu bạn hiểu các thao tác danh sách liên kết đơn, thì các thao tác danh sách liên kết kép sẽ rất rõ ràng.

Doubly Linked List Insertion

Insert vào danh sách được liên kết kép có ba trường hợp (giống như danh sách được liên kết đơn).

  • Chèn một nút mới trước đầu.
  • Chèn một nút mới sau đuôi (ở cuối danh sách).
  • Chèn một nút mới vào giữa danh sách.

Inserting a Node in Doubly Linked List at the Beginning

Trong trường hợp này, nút mới được chèn trước nút đầu. Con trỏ trước đó và con trỏ tiếp theo cần được sửa đổi và có thể thực hiện theo hai bước:

  • Cập nhật con trỏ bên phải của nút mới để trỏ đến nút đầu hiện tại (liên kết chấm trong hình bên dưới) và cũng tạo con trỏ bên trái của nút mới là NULL.

image.png

  • Cập nhật con trỏ bên trái của nút đầu để trỏ đến nút mới và đặt nút mới làm phần đầu.

image.png

Inserting a Node in Doubly Linked List at the Ending

Trong trường hợp này, lướt qua danh sách cho đến cuối và chèn nút mới.

  • Con trỏ bên phải của nút mới trỏ đến NULL và con trỏ bên trái trỏ đến cuối danh sách.

image.png

  • Cập nhật con trỏ bên phải của nút cuối cùng để trỏ đến nút mới.

image.png

Inserting a Node in Doubly Linked List in the Middle

Như đã thảo luận trong các danh sách được liên kết đơn lẻ, hãy duyệt danh sách đến Position Node và chèn nút mới.

  • Con trỏ bên phải của nút mới trỏ đến nút tiếp theo của nút vị trí mà chúng ta muốn chèn nút mới. Ngoài ra, con trỏ bên trái của nút mới trỏ đến Position Node.

image.png

  • Con trỏ bên phải Position Node trỏ đến nút mới và con trỏ trái của nút tiếp theo của Position Node trỏ đến nút mới.

image.png

Time Complexity:

O(n)O(n). Trong trường hợp xấu nhất, chúng ta có thể phải chèn nút vào cuối danh sách.
Space Complexity:

O(1)O(1), để tạo một biến tạm thời.

Doubly Linked List Deletion

Tương tự như danh sách được liên kết đơn, ở đây chúng ta có 3 trường hợp có thể xảy ra:

  • Xóa nút ở đầu.
  • Xóa nút đuôi (ở cuối danh sách).
  • Xóa nút vào giữa danh sách.

Deleting the First Node in Doubly Linked List

Trong trường hợp này, nút đầu tiên bị xóa khỏi danh sách. Nó có thể được thực hiện trong hai bước

  • Tạo một nút tạm thời sẽ trỏ đến cùng một nút với nút của phần đầu.

image.png

  • Bây giờ, di chuyển head node sang nút tiếp theo, con trỏ trái thành null và loại bỏ nút tạm thời.

image.png

Deleting the Last Node in Doubly Linked List

Thao tác này phức tạp hơn một chút so với việc loại bỏ nút đầu tiên, bởi vì thuật toán sẽ tìm một nút, nút này nằm ở phía trước của đuôi. Điều này có thể được thực hiện trong ba bước:

  • Duyệt qua danh sách và trong khi duyệt cũng duy trì địa chỉ nút trước đó. Khi đến cuối danh sách, chúng ta sẽ có hai con trỏ, một trỏ tới đuôi và một trỏ đến nút phía trước của đuôi.

image.png

  • Cập nhật con trỏ phải của nút trước đó thành nút đuôi với NULL.

image.png

  • Loại bỏ nút đuôi.

image.png

Deleting an Intermediate Node in Doubly Linked List

Trong trường hợp này, nút bị xóa luôn nằm giữa hai nút.
Việc loại bỏ có thể được thực hiện theo hai bước:

  • Tương tự như trường hợp trước, duy trì nút trước trong khi cũng duyệt qua danh sách. Khi định vị nút sẽ bị xóa, hãy thay đổi con trỏ next của nút trước thành nút phía sau của nút sẽ bị xóa.

image.png

  • Loại bỏ nút hiện tại

image.png

Time Complexity:

O(n)O(n). Trong trường hợp xấu nhất, chúng ta có thể phải chèn nút vào cuối danh sách.
Space Complexity:

O(1)O(1), để tạo một biến tạm thời.

Implementation

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo