Danh sách liên kết và một số thao tác trên danh sách liên kết

0
219

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

Danh sách liên kết là một cấu trúc dữ liệu bao gồm một tập, trong đó mỗi phần tử là một phần của một nút có chứa một liên kết tới một nút.

14054033_951575464964991_2732335057458852967_n

Để khai báo danh sách liên kết trong C, ta có thể dùng cấu trúc con trỏ.

Ví dụ khai báo một danh sách liên kết mà mỗi nút là một phần tử số nguyên:

Đầu tiên ta khai báo cấu trúc Node bao gồm 2 thành phần:

  • Biến chứa dữ liệu
  • Con trỏ chứa dữ liệu nút kế tiếp.

Tiếp theo ta định nghĩa một kiểu dữ liệu con trỏ tới nút có tên là listnode.

Đối với danh sách liên kết có kiểu dữ liệu phức tạp hơn, ta khái báo cấu trúc của phần tử này trước (xstruct), sau đó đưa kiểu cấu trúc đó vào kiểu phần tử trong cấu trúc node.

Các thao tác cơ bản trên danh sách liên kết

1.Tạo và cấp phát bộ nhớ cho một nút

2. Chèn 1 nút vào đầu danh sách liên kết

  • Tạo và cấp phát bộ nhớ cho nút mới
  • Sau khi gán giá trị thích hợp cho phần tử của nút mới, cho con trỏ của nút mới trỏ đến nút đầu tiên của danh sách.
  • Cuối cùng, để p vẫn trỏ đến nút đầu danh sách, ta cần cho p trỏ đến nút mới tạo.

Chú ý: Cần phải làm đúng trình tự, nếu không sẽ dẫn đến mất dữ liệu. Chẳng hạn, nếu ta cho con trỏ p trỏ đến nút mới tạo trước, thì khi đó nút mới tạo sẽ không trỏ được tới đầu danh sách liên kết cũ, vì không còn biến nào lưu trữ vị trí này.

Ta tạo ra cấu trúc của 1 List như sau, việc này sẽ dễ dàng hơn cho các thao tác.

3. Chèn một nút vào cuối danh sách

  • Tạo và cấp phát bộ nhớ cho 1 nút mới
  • Dịch chuyển con trỏ đến cuối danh sách
  • Cho con trỏ của nút cuối trỏ đến nút vừa tạo, và con trỏ nút vừa tạo trỏ đến null.

Trên đây là định nghĩa về danh sách liên kết và một số thao tác cơ bản, còn rất nhiều thao tác trên danh sách liên kết sẽ được gửi đến các bạn trong các bài viết tiếp theo. Chúc các bạn thành công!

LEAVE A REPLY