C++ Data Structure: Linked List

Hi. Chào mừng các bạn đến với chủ đề:

Data Structure C++ tai blog: Phattrienphanmem123az.com

Bài đầu tiên chúng ta sẽ cùng tìm hiểu về thuật toán Linked List, còn được gọi là Danh sách liên kết.

1. Lý thuyết cơ bản về Linked list.

Là một dạng cấu trúc dữ liệu tuyến tính.

Mỗi phần tử trong danh sách được liên kết bởi việc sử dụng một con trỏ.

Hãy nhìn hình minh họa sau đây.

Mỗi phần tử của linked list sẽ gồm 2 phần cơ bản.

+ Một phần chứa dữ liệu.

+ Và một con trỏ next để chưa địa chỉ của phần tử tiếp theo.

Như vậy next của A sẽ lưu trữ địa chỉ của B, next của B sẽ lưu trữ địa chỉ của C và cứ thế cho đến phần tử cuối cùng, next của D sẽ trỏ tới NULL.

– Nó khác hoàn toàn so với cơ chế lưu trữ dữ liệu của mảng. Link list không thể truy xuất từng phần tử theo chỉ số như mảng.

– Khá linh hoạt trong việc lưu trữ một tập hợp các phần tử, vì có thể viết các hàm thêm mới phần tử và loại bỏ phần tử.

2. Triển khai linked list trên C++ với dữ liệu cơ bản: int.

 

Sử dụng linked list trong hàm main.

 

3. Sử dụng template xây dựng linked list tổng quát nhất.

Khi làm demo hay các ví dụ minh họa, chúng ta thường sử dụng dữ liệu thuần như int, float, để minh họa cho linked list.

Nhưng khi đưa linked list vào sử dụng cho các dữ liệu án, dữ liệu không còn là dữ liệu thuần, mà nó có thể là một kiểu dữ liệu đối tượng bất kỳ.

Do đó chúng ta phải xây dựng được linked list một cách tổng quát.

Và template là kỹ thuật giúp chúng ta thực hiện được điều này.

a. Sử dụng class thay cho struct để xây dựng dữ liệu NodeData.

(Node data gồm 2 phần, dữ liệu và con trỏ next)

 

b. Xây dựng class linked list mà mỗi phần tử của nó là một NodeData.

c. Bắt đầu triển khai sử dụng linked list.

Ví dụ tôi sẽ không sử dụng với kiểu dữ liệu thuần như dạng int hay float. Tôi sẽ xây dựng 1 kiểu dữ liệu trừu tượng.

Ví dụ dữ liệu là một lớp thông tin của một cá nhân bao gồm: Tên, tuổi, giới tính.

Như vậy linked list của tôi sẽ là một tập hợp lưu trữ các đối tượng con người.

Mỗi thành phần của linked list sẽ có dữ liệu T là kiểu person, và một con trỏ next trỏ sang phần tử tiếp theo.

 

Như vậy việc sử dụng template giúp ta tổng quát được cấu trúc linked list.

Bạn có thể sử dụng linked list với bất cứ kiểu dữ liệu nào.

 

d. Bắt đầu sử dụng linked list với kiểu dữ liệu person.

 

Kết quả.

 

Như vậy vể cở bản Linked  list là một danh sách liên kết giữa các phần tử. Phần tử trước trỏ được đến phần tử sau.

Với 1 con trỏ p head trong ví dụ trên, có thể coi đây là một dạng singly linked list. Nghĩa là danh sách liên kết đơn.

Chúng ta có thể phát triển và mở rộng hơn với nhiều loại hình khác về cấu trúc dữ liệu như double linked list, stack, queue.

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.