Chương 3: DANH SÁCH LIÊN KẾT – 2. Danh sách liên kết đơn

Tram Ho

3.6 Singly Linked Lists

Thông thường, khi ta nói tới “linked list” sẽ mang nghĩa là một “singly linked list” ~ Danh sách liên kết đơn.
Danh sách này bao gồm một số node trong đó mỗi node có một con trỏ tiếp theo đến phần tử sau.
Liên kết của node cuối cùng trong danh sách là NULL, cho biết điểm kết thúc của danh sách.

image.png

Sau đây là một khai báo kiểu linked list:

Basic Operations on a List

  • Duyệt qua list
  • Chèn một phần tử vào list
  • Xóa một phần tử trong list

Traversing the Linked List

Giả sử rằng Head trỏ đến nút đầu tiên của danh sách. Để xem qua danh sách, chúng tôi làm như sau.

  • Đi theo con trỏ
  • Hiển thị nội dung của các nút (hoặc số lượng) khi chúng được duyệt qua.
  • Dừng khi con trỏ tiếp theo trỏ đến NULL.

image.png

Hàm

ListLength()ListLength() nhận một linked list làm đầu vào và đếm số lượng các nút trong list.
Hàm này có thể được sử dụng để in dữ liệu danh sách với chức năng in bổ sung.

Time Complexity:

O(n)O (n), để quét danh sách kích thước n. Space Complexity:

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


Singly Linked List Insertion

Thêm một phần tử vào một singly-linked list có ba trường hợp:

  • Thêm một nút mới ở đầu
  • Thêm một nút mới ở cuối
  • Thêm một nút mới ở giữa của list(vị trí bất kỳ)

Note: Để thêm một phần tử trong danh sách liên kết ở vị trí p nào đó, giả sử rằng sau khi thêm, vị trí của nút mới này là p.

Thêm một nút mới ở đầu Singly Linked List

Trong trường hợp này, một nút mới được thêm vào trước nút đầu hiện tại. Chỉ một con trỏ tiếp theo cần được sửa đổi (con trỏ tiếp theo của nút mới) và nó có thể được thực hiện theo hai bước:

  • Cập nhật con trỏ tiếp theo của nút mới, để trỏ đến phần đầu hiện tại.

image.png

  • Cập nhật head trỏ đến nút mới.

image.png

Thêm một nút mới ở cuối Singly Linked List

Trong trường hợp này, chúng ta cần sửa đổi 2 con trỏ ở 2 nút cuối cùng và nút mới thêm vào.

  • Con trỏ của nút mới trỏ tới NULL

image.png

  • Con trỏ ở nút cuối cùng trỏ tới nút mới

image.png

Thêm một nút mới ở giữa Singly Linked List

Trong trường hợp này, chúng ta sẽ cần phải sửa con trỏ ở 2 nút

  • Nếu chúng ta muốn thêm một phần tử ở vị trí position 3 thì chúng ta dừng lại ở vị trí position 2.
    Điều đó có nghĩa là chúng ta đi qua 2 nút và chèn nút mới.
    Chúng ta hãy giả sử rằng nút thứ hai được gọi là position node.
    Nút mới trỏ đến nút tiếp theo của vị trí mà chúng ta muốn thêm nút này.

image.png

  • Con trỏ của Position node sẽ trỏ tới nút mới thêm vào.

image.png

Lưu ý: Chúng ta có thể triển khai ba biến thể của thao tác chèn riêng biệt.

Time Complexity:

O(n)O(n), vì trong trường hợp xấu nhất, chúng ta có thể cần 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.


Singly Linked List Deletion

Tương tự như thêm nút mới, thao tác xoá chúng ta cũng có 3 trường hợp

  • Xóa một nút ở đầu
  • Xóa một nút ở cuối
  • Xóa một nút ở giữa của list(vị trí bất kỳ)

Xóa một nút ở đầu Singly Linked List

Xóa nút đầu khỏi danh sách có thể thực hiện trong 2 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 con trỏ các nút đầu đến nút tiếp theo và loại bỏ nút.

image.png

Xóa một nút ở cuối Singly Linked List

Trong trường hợp này, nút cuối cùng bị xóa khỏi danh sách.
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ằm trước nút cuối cùng.
Nó 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 nút đuôi và một trỏ đến nút trước nút đuôi.

image.png

  • Cập nhật con trỏ tiếp theo của nút cạnh nút cuối với NULL.

image.png

  • Loại bỏ nút cuối.

image.png

Xóa một nút ở giữa Singly Linked List

Trong trường hợp này, nút cần loại bỏ luôn nằm giữa hai nút. Việc loại bỏ như vậy 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 duyệt qua danh sách. Khi chúng tôi thấy nút cần xóa, hãy thay đổi con trỏ của previos node thành con trỏ tiếp theo 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ể cần xóa nút ở cuối danh sách.
Space Complexity:

O(1)O(1). Vì chúng tôi chỉ tạo một biến tạm thời.

Deleting Singly Linked List

Điều này hoạt động bằng cách lưu trữ nút hiện tại trong một số biến tạm thời và giải phóng nút hiện tại.
Sau khi giải phóng nút hiện tại, hãy chuyển đến nút tiếp theo với một biến tạm thời và lặp lại quá trình này cho tất cả các nút.
Time Complexity:

O(n)O(n), để quét toàn bộ danh sách kích thước n.
Space Complexity:

O(1)O(1), cho biến tạm thời.

Implementation

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo