Danh Sách Liên Kết Đơn

Cập nhật thông tin chi tiết về Danh Sách Liên Kết Đơn mới nhất ngày 25/11/2020 trên website Zdungk.com. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Cho đến thời điểm hiện tại, bài viết này đã đạt được 12,375 lượt xem.

Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và đơn giản nhất về cấu trúc dữ liệu động sử dụng con trỏ để cài đặt. Do đó, kiến thức con trỏ là rất quan trọng để hiểu cách danh sách liên kết hoạt động, vì vậy nếu bạn chưa có kiến thức về con trỏ thì bạn nên học về con trỏ trước. Bạn cũng cần hiểu một chút về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần nội dung cài đặt danh sách liên kết của bài viết này sẽ chỉ trình bày về danh sách liên kết đơn.

1. Lý thuyết về danh sách liên kết

Về bản chất, danh sách liên kết có chức năng như một mảng, có thể thêm và xóa các phần tử ở bất kỳ vị trí nào khi cần thiết. Một số sự khác nhau giữa danh sách liên kết và mảng:

Lưu ý: Ở bảng phía trên, các phần in nghiêng thể hiện đó là ưu điểm so với đối thủ còn lại.

2. Danh sách liên kết là gì?

Danh sách liên kết đơn là một tập hợp các Node được phân bố động, được sắp xếp theo cách sao cho mỗi Node chứa ” một giá trị”(Data) và ” một con trỏ”(Next). Con trỏ sẽ trỏ đến phần tử kế tiếp của danh sách liên kết đó. Nếu con trỏ mà trỏ tới NULL, nghĩa là đó là phần tử cuối cùng của linked list.

Hình ảnh mô tả cho một Node trong danh sách liên kết đơn:

Và đây là hình ảnh mô phỏng một danh sách liên đơn kết đầy đủ:

Danh sách các kiểu danh sách liên kết:

  • Danh sách liên kết đơn(Single linked list): Chỉ có sự kết nối từ phần tử phía trước tới phần tử phía sau.
  • Danh sách liên kết đôi(Double linked list): Có sự kết nối 2 chiều giữa phần tử phía trước với phần tử phía sau
  • Danh sách liên kết vòng(Circular Linked List): Có thêm sự kết nối giữa 2 phần tử đầu tiên và phần tử cuối cùng để tạo thành vòng khép kín.

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

3.1. Khai báo linked list

Để đơn giản hóa, data của chúng ta sẽ là số nguyên(int). Bạn cũng có thể sử dụng các kiểu nguyên thủy khác(float, char,…) hay kiểu dữ liệu struct(SinhVien, CanBo,…) tự tạo.

Khai báo trên sẽ được sử dụng cho mọi Node trong linked list. Trường data sẽ lưu giữa giá trị và next sẽ là con trỏ để trỏ đến thằng kế tiếp của nó.

Tại sao next lại là kiểu LinkedList của chính nó? Bởi vì nó là con trỏ trỏ của chính bản thân nó, và nó trỏ tới một thằng Node kế tiếp cũng có kiểu LinkedList.

3.2. Tạo mới 1 Node

Hãy tạo một kiểu dữ liệu của struct LinkedList để code clear hơn:

Mỗi một Node khi được khởi tạo, chúng ta cần cấp phát bộ nhớ cho nó, và mặc định cho con trỏ next trỏ tới NULL. Giá trị của Node sẽ được cung cấp khi thêm Node vào linked list.

  • typedef được dùng để định nghĩa một kiểu dữ liệu trong C. VD: typeder long long LL;
  • malloc là hàm cấp phát bộ nhớ của C. Với C++ chúng ta dùng new
  • sizeof là hàm trả về kích thước của kiểu dữ liệu, dùng làm tham số cho hàm malloc

Lưu ý: Không giống với mảng, cần khai báo arr[size]. Trong linked list, vì mỗi Node sẽ có con trỏ liên kết đến Node tiếp theo. Do đó, với danh sách liên kết đơn, bạn chỉ cần lưu giữ Node đầu tiên(HEAD). Có head rồi bạn có thể đi tới bất cứ Node nào.

3.3. Thêm Node vào danh sách liên kết

Thêm vào đầu

Việc thêm vào đầu chính là việc cập nhật lại thằng head. Ta gọi Node mới(temp), ta có:

  • Nếu head đang trỏ tới NULL, nghĩa là linked list đang trống, Node mới thêm vào sẽ làm head luôn
  • Ngược lại, ta phải thay thế thằng head cũ bằng head mới. Việc này phải làm theo thứ tự như sau:
    • Cho next của temp trỏ tới head hiện hành
    • Đặt temp làm head mới

Thêm vào cuối

Chúng ta sẽ cần Node đầu tiên, và giá trị muốn thêm. Khi đó, ta sẽ:

  1. Tạo một Node mới với giá trị value
  2. Nếu head = NULL, tức là danh sách liên kết đang trống. Khi đó Node mới(temp) sẽ là head luôn.
  3. Ngược lại, ta sẽ duyệt tới Node cuối cùng(Node có next = NULL), và trỏ next của thằng cuối tới Node mới(temp).

Thêm vào vị trí bất kỳ

Để làm được việc này, ta phải duyệt từ đầu để tìm tới vị trí của Node cần chèn, giả sử là Node Q, khi đó ta cần làm theo thứ tự sau:

  • Cho next của Node mới trỏ tới Node mà Q đang trỏ tới
  • Cho Node Q trỏ tới Node mới

3.4. Xóa Node khỏi danh sách liên kết

Xóa đầu

Xóa cuối

Xóa cuối mới nhọc nè, nhọc ở chỗ phải duyệt đến thằng cuối – 1, cho next của cuối – 1 đó bằng NULL.

Xóa ở vị trí bất kỳ

Việc xóa ở vị trí bất kỳ cũng khá giống xóa ở cuối kia. Đơn giản là chúng ta bỏ qua một phần tử, như ảnh sau:

3.5. Lấy giá trị ở vị trí bất kỳ

3.6. Tìm kiếm trong danh sách liên kết

Hàm tìm kiếm này sẽ trả về chỉ số của Node đầu tiên có giá trị bằng với giá trị cần tìm. Nếu không tìm thấy, chúng ta trả về -1.

Chúng ta có thể sử dụng hàm này để xóa tất cả các Node trong danh sách liên kết có giá trị chỉ định như sau:

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

Việc duyệt danh sách liên kết cực đơn giản. Khởi tạo từ Node head, bạn cứ thế đi theo con trỏ next cho tới trước khi Node đó NULL.

3.8. Một số hàm bổ trợ khác

Hàm khởi tạo Node head

Đơn giản là cho con trỏ head = NULL thôi. Nếu bạn để ý, chúng ta vẫn check head = NULL để biết rằng danh sách liên kết chưa có phần tử nào ở các hàm phía trên.

Hàm lấy số phần tử của DSLK

Duyệt và đếm chừng nào các Node chưa NULL. Sau cùng, trả về giá trị đếm được.

Hàm nhập danh sách liên kết

?Tham khảo ngay: Khóa học Cấu trúc dữ liệu và giải thuật C++

4. Code hoàn chỉnh của danh sách liên kết đơn

Kết quả chạy thử:

Bạn đang xem bài viết Danh Sách Liên Kết Đơn trên website Zdungk.com. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!