Danh sách liên kết đơn là gì?
Một danh sách được liên kết đơn lẻ là một cấu trúc dữ liệu động là một danh sách mà mỗi phần tử được liên kết với phần tử chính xác sau nó trong danh sách. Mỗi phần tử (được gọi là nút hoặc nút) trong danh sách được liên kết đơn lẻ là một cấu trúc có hai thành phần:
- Phần tử dữ liệu: Lưu trữ thông tin về chính phần tử đó.
- Phần tử liên kết: lưu trữ địa chỉ của phần tử tiếp theo trong danh sách, nếu phần tử là một phần thì phần tử cuối cùng là null.
li>
Tham khảo thêm: Công việc lập trình C ++ lương cao của Topdev
Minh họa danh sách liên kết đơn
Đặc điểm của danh sách được liên kết đơn lẻ
Vì danh sách được liên kết đơn lẻ là cấu trúc dữ liệu động được tạo bằng cách phân bổ động, nên nó có các đặc điểm sau:
- Bộ nhớ được cấp phát trong thời gian chạy
- Thay đổi kích thước bằng cách thêm và bớt các phần tử
- Kích thước tối đa phụ thuộc vào bộ nhớ khả dụng trong bộ nhớ
- Phần tử lưu trữ ngẫu nhiên (không liên tục ) trong bộ nhớ
Và do sự liên kết giữa phần tử đầu tiên trong danh sách được liên kết đơn lẻ và các phần tử sau nó, nó có các đặc điểm sau:
- Chỉ cần biết phần tử đầu tiên và phần tử cuối cùng để quản lý danh sách
- Để truy cập các phần tử ngẫu nhiên, người ta phải truy cập vào vị trí đó ngay từ đầu
- Chỉ một phần tử có thể được tìm kiếm tuyến tính
Cài đặt danh sách liên kết đơn
Trước khi bắt đầu triển khai danh sách được liên kết đơn lẻ, hãy đảm bảo bạn đã nắm được các con trỏ và phân bổ động trong c ++. Vì một danh sách được liên kết đơn lẻ là một cấu trúc dữ liệu động, bạn sẽ khó hiểu được bài viết này nếu bạn không nắm vững con trỏ và phân bổ động. Nếu bạn chưa tự tin thì hãy bớt chút thời gian đọc bài viết này của tôi nhé. Hãy bắt đầu ngay bây giờ!
Tạo nút
Một danh sách được liên kết đơn lẻ được tạo thành từ nhiều nút, vì vậy hãy bắt đầu với các nút. Một nút bao gồm hai thành phần, một thành phần dữ liệu và một thành phần liên kết. Phần tử dữ liệu có thể là kiểu dữ liệu có sẵn hoặc bạn có thể tự định nghĩa (cấu trúc hoặc lớp …), trong bài viết này, để đơn giản, tôi sẽ sử dụng dữ liệu kiểu int. Phần tử liên kết là một địa chỉ, tự nhiên là một con trỏ và con trỏ này trỏ đến nút tiếp theo, vì vậy con trỏ này là một con trỏ tới một nút.
Để tạo một nút mới, chúng tôi tự động cấp phát nút mới, khởi tạo nó thành giá trị ban đầu và trả về địa chỉ của nút mới được cấp phát.
Tạo một danh sách được liên kết riêng
Chúng tôi có các nút tạo thành một danh sách được liên kết đơn lẻ, tiếp theo, chúng tôi cần quản lý chúng bằng cách biết phần tử đầu tiên và cuối cùng. Vì mỗi phần tử được liên kết với phần tử tiếp theo, mô tả chỉ cần biết phần tử đầu tiên và cuối cùng để quản lý danh sách này. Rất đơn giản, chúng ta cần tạo một cấu trúc để lưu trữ địa chỉ của phần tử đầu tiên (phần đầu) và phần tử cuối cùng (hoặc phần đuôi).
Khi chúng tôi tạo danh sách lần đầu tiên, danh sách sẽ không có phần tử nào, vì vậy phần đầu và phần đuôi không trỏ đến bất kỳ đâu, chúng tôi đặt chúng thành trống. Chúng tôi xây dựng hàm tạo danh sách như sau:
Bây giờ để tạo một danh sách, chúng ta thực hiện như sau:
Thêm phần tử vào danh sách
Thêm vào đầu
Để thêm một nút vào đầu danh sách, trước tiên chúng ta cần kiểm tra xem danh sách có trống không, nếu danh sách trống chúng ta chỉ cần gán phần đầu và phần đuôi của danh sách cho nút. Ngược lại, nếu danh sách không trống, chúng tôi trỏ phần tử được liên kết với phần đầu và sau đó gán lại phần đầu với nút mới.
Thêm phần tử vào đầu danh sách liên kết đơn
Như được hiển thị ở trên, chúng tôi thêm các nút không có dữ liệu vào danh sách. Chúng tôi trỏ nút bên cạnh phần đầu của danh sách (là nút đầu tiên trong danh sách có dữ liệu bằng 1), và sau đó chúng tôi trỏ phần đầu đến nút vừa thêm dữ liệu 0. Vì vậy, phần tử đã ở đầu danh sách.
Thêm
vào cuối
Tương tự như vậy, để thêm một nút vào cuối danh sách được liên kết, trước tiên, chúng tôi kiểm tra xem danh sách được liên kết có trống không và nếu có, hãy gán phần đầu và phần đuôi cho nút mới. Nếu không trống, ta trỏ tail-> bên cạnh nút mới, sau đó gán lại tail cho nút mới (vì bây giờ nút mới thêm là tail).
Thêm phần tử vào cuối danh sách liên kết đơn
Trong hình ảnh trên, chúng tôi đã thêm các nút có dữ liệu bằng 6 vào danh sách. tail hiện là nút có dữ liệu 5, gán đuôi-> tiếp theo một nút mới để nối nó vào đuôi danh sách, lúc này nút mới trở thành phần tử cuối cùng của danh sách, vì vậy chúng ta gán lại đuôi một nút mới.
Thêm vào sau bất kỳ nút nào
Để thêm nút p sau bất kỳ nút q nào, trước tiên chúng ta cần kiểm tra xem nút q có trống không, nếu nút q trống tức là danh sách trống, sau đó thêm nó vào đầu danh sách. Nếu nút q không trống, tức là tồn tại trong danh sách, chúng ta thực hiện con trỏ p-> next = q-> next, sau đó q-> next = p. Tiếp theo ta kiểm tra xem nút q trước đó có phải là nút cuối cùng hay không, nếu nút q là nút cuối cùng thì thêm p, p sẽ là nút cuối cùng nên ta gán lại tail = p.
Thêm phần tử vào sau nút Q trong danh sách liên kết đơn
Trong sơ đồ trên, chúng tôi đã thêm một nút có dữ liệu bằng 4 (nút p) sau nút có dữ liệu bằng 3 (nút q). Chúng tôi trỏ phần tiếp theo của nút p tới phần tiếp theo của nút q, tức là dữ liệu của nút bằng 5, và sau đó trỏ phần tiếp theo của nút q tới nút p, vì vậy nút p đã được thêm vào danh sách.
Xóa phần tử khỏi danh sách
Xóa ở đầu
Để xóa phần tử ở đầu danh sách, ta kiểm tra xem danh sách có trống không, nếu trống thì không cần xóa và trả về kết quả là 0. Nếu danh sách không trống, chúng ta lưu node.head một lần nữa, sau đó đặt head thành phần đầu tiếp theo của nút đầu, sau đó xóa nút đầu. Tiếp theo chúng ta cần kiểm tra xem đầu nút danh sách vừa xóa có trống không, nếu trống chúng ta gán lại tail thành null và trả về kết quả 1.
Lưu ý rằng trước khi xóa nút đầu, chúng ta sử dụng biến tham chiếu x để lưu giá trị của nút bị hủy để sử dụng.
Xóa phần tử đầu danh sách liên kết đơn
Trong hình trên, tôi đã loại bỏ nút đầu tiên có dữ liệu bằng 0. Tôi trỏ đầu đến nút tiếp theo (đầu hiện tại) của nút 0, khi đó đầu bây giờ sẽ là nút 1, sau đó tôi xóa nút 0 là được.
Xóa sau bất kỳ nút nào
Để xóa nút p sau một nút q bất kỳ, chúng ta kiểm tra xem nút q có rỗng không, nếu nút q là null thì nó không tồn tại trong danh sách nên trả về 0, không xóa. Nếu nút q không rỗng mà nút tiếp theo của q là null, nghĩa là p là null, không bị xóa, trả về 0 (vì không có nút nào sau q, q là đuôi). Nếu nút p tồn tại, chúng ta kiểm tra xem nút p có phải là đuôi hay không, và nếu nút p là đuôi thì gán lại đuôi cho q, tức là nút trước đó sẽ xóa nút p.
Trong sơ đồ trên, chúng tôi đã loại bỏ nút có dữ liệu 3 (nút p) sau nút có dữ liệu 2 (nút q). Ta trỏ nút tiếp theo của nút q tới nút tiếp theo của nút p, tức là nút có dữ liệu 4, và sau đó xóa nút p để hoàn thành.
Duyệt danh sách và in
Sau khi thêm và bớt các thao tác, chúng tôi có thể in ra danh sách để kiểm tra xem các thao tác có chính xác hay không. Để in danh sách, chúng tôi lặp lại danh sách từ đầu đến cuối và in khi chúng tôi duyệt qua. Chúng tôi gán một nút đầu tiên, sau đó kiểm tra xem nút đó có trống không, sau đó in ra dữ liệu cho nút đó, sau đó gán cho nút đó nút tiếp theo của chính nó, bây giờ là nút tiếp theo, v.v. cho đến khi kết thúc.
Lấy bất kỳ giá trị nút nào
Để nhận giá trị phần tử trong danh sách, chúng tôi thực hiện thao tác duyệt giống như khi in phần tử. Chúng ta sẽ tạo một biến đếm để biết vị trí hiện tại, đi ngang qua nút cho đến khi nút trống hoặc bộ đếm bằng vị trí nút để lấy. Kiểm tra nếu nút không trống và bộ đếm bằng vị trí cần lấy thì ta sẽ trả về địa chỉ của nút đó, ngược lại là null (danh sách trống hoặc vị trí cần lấy nằm ngoài phạm vi của danh sách).
Phần tử tìm kiếm trong danh sách
Ý tưởng của việc tìm một phần tử là duyệt qua danh sách, nếu không tìm thấy, hãy tiếp tục duyệt. Sau khi duyệt xong, chúng ta chỉ cần kiểm tra xem nút duyệt có trống không, nếu không có nghĩa là đã tìm thấy, chúng ta sẽ trả về địa chỉ của nút đó.
Đếm số phần tử trong danh sách
Việc tính toán số lượng phần tử cũng tương tự, chúng tôi áp dụng tính năng duyệt từ đầu đến cuối để tính số nút.
Xóa danh sách
Để xóa danh sách, chúng ta cần hủy tất cả các nút, tức là đi qua và hủy từng nút. Ở đây tôi sẽ sử dụng lại hàm removehead. Đầu tiên, chúng ta gán head cho một nút, kiểm tra xem nút đó có phải là null không, sau đó gọi removehead và gán lại head cho nút một lần nữa, và cứ tiếp tục như vậy cho đến khi nút là null. Sau khi loại bỏ tất cả các phần tử, hãy gán lại đuôi bằng null.
Tóm tắt
Vì vậy, trong bài viết này, tôi đã giới thiệu cho bạn một số thao tác cơ bản trên danh sách liên kết đơn và danh sách. Bạn không nhất thiết phải làm theo cách của mình, có nhiều cách khác nhau để thực hiện, miễn là bạn nắm rõ về con trỏ và phân bổ động trong c ++. Nếu bạn thấy hay thì đừng quên chia sẻ cho bạn bè của mình nhé. Cảm ơn đã xem!