• Trang Chủ
  • Top Source
  • Source miễn phí
  • Source Tham Khảo
  • Kiến Thức
  • Thư Viện
  • Trang Chủ
  • Top Source
  • Source miễn phí
  • Source Tham Khảo
  • Kiến Thức
  • Thư Viện

Chi tiết bài học danh sách liên kết đơn

ContentATP Bởi ContentATP
01/09/2020
Trong Kiến Thức
0
Maxresdefault (4)

Danh sách liên kết đơn(Single linked list) là ví dụ tốt nhất và cơ bản nhất về cấu trúc dữ liệu động dùng con trỏ để thiết lập. Vì thế, kiến thức con trỏ là cực kì quan trọng để biết cách danh sách liên kết công việc, vì lẽ đó nếu như bạn chưa có chuyên môn 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 tí về cấp phát bộ nhớ động. Để đơn giản và dễ hiểu, phần thông tin cài đặt danh sách liên kết của bài viết này sẽ chỉ giải thích về danh sách liên kết đơn.

Mục lục

  • Lý thuyết về danh sách liên kết
  • Danh sách liên kết là gì?
    • Danh sách các kiểu danh sách liên kết:
      • Điểm mạnh:
      • Điểm yếu:
    • Xây dựng danh sách liên kết đơn với C/C++
    • Các thành phần của danh sách liên kết đơn bao gồm:
  • Ứng dụng của danh sách liên kết đơn trong thực tế:

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

Danh sách liên kết
Danh sách liên kết

Về bản chất, danh sách liên kết có công dụ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 không thể thiếu. Một vài sự khác nhau giữa danh sách liên kết và mảng:

Nội dung Mảng Danh sách liên kết
Kích thước
  • Kích thước cố định
  • Cần chỉ rõ kích thước trong khi khai báo
  • Kích thước thay đổi trong lúc thêm/ xóa phần tử
  • Kích thước tối ưu dựa vào bộ nhớ
Cấp phát bộ nhớ
  • Tĩnh: Bộ nhớ được cấp phát trong quá trình biên dịch
  • Động: Bộ nhớ được cấp phát trong lúc chạy
Thứ tự & sắp đặt
  • Được lưu trữ trên một dãy ô nhớ liên tục
  • Được lưu trữ trên các ô nhớ ngẫu nhiên
Truy xuất
  • Truy cập tới phần tử ngẫu nhiên trực tiếp bằng việc dùng thông số mảng: O(1)
  • Truy xuất tới phần tử ngẫu nhiên luôn phải duyệt từ đầu/cuối đến phần tử đó: O(n)
Tìm kiếm
  • Tìm kiếm tuyến tính hoặc tìm kiếm nhị phân
  • Chỉ có thể tìm kiếm tuyến tính

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

>>>Xem thêm: Mã nguồn mở là gì? Tổng hợp các mã nguồn mở tốt nhất hiện nay

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

Danh sách liên kết
Danh sách liên kết

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 bí quyết 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ử tiếp theo của danh sách liên kết đấy. Nếu con trỏ mà trỏ tới NULL, có nghĩa là đó là phần tử cuối cùng của linked list.

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ó mối quan hệ 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): Kết hợp thêm sự kết nối giữa 2 phần tử trước tiên và phần tử cuối cùng để hình thành vòng khép kín.

Các vấn đề mạnh và điểm yếu của danh sách liên kết so sánh với mảng:

Cả danh sách liên kết và mảng đều có thể được sử dụng để chứa các dữ liệu cùng kiểu. Nhưng chúng lại có nhiều đặc điểm riêng, và điểm tốt nhất của thứ này lại là nhược điểm của cái còn lại.

Điểm mạnh:

  • Danh sách liên kết có kích thước động, có thể mở rộng hay thu hẹp cực kì dễ ràng.
  • Việc chèn hay xóa một phần tử trong danh sách liên kết là rất giản đơn, ta chỉ cần điều chỉnh vị trí trỏ của các con trỏ thay vì phải dịch tất cả phần dữ liệu còn lại. Coi ví dụ sau khi ta mong muốn chèn node C vào giữa node A và B:

Điểm yếu:

  • Danh sách liên kết mang yếu điểm của cấp phát động về hiệu suất. Điều này cũng dễ hiểu vì mảng có vị trí bộ đệm vượt trội hơn (là các khối các ô nhớ liên tiếp) so sánh với danh sách liên kết.
  • Ta không thể truy cập ngẫu nhiên một phần tử trong danh sách liên kết ngay tức thì, mà phải hành động duyệt từ đầu danh sách cho tới khi gặp phần tử đấy. Do vậy ta không thể hành động tìm kiếm nhị phân với các danh sách liên kết.
  • Cần thêm không gian bộ nhớ cho con trỏ trong mỗi phần tử của danh sách liên kết.

Xây dựng danh sách liên kết đơn với C/C++

Để tạo ra một danh sách sách liên kết trước hết ta cần hiểu được danh sách liên kết cần gồm có những thành phần nào và các thực hành các bước mà ta có khả năng thực hiện với danh sách liên kết:

Các thành phần của danh sách liên kết đơn bao gồm:

  • Các node: Mỗi node bao gồm hai thành phần: phần dữ liệu và phần liên kết là một con trỏ để trỏ tới vị trí của node kế tiếp, Theo một cách khác, con trỏ này có giá trị là địa chỉ của node tiếp theo. Node cuối cùng của danh sách liên kết sẽ trỏ tới NULL, tức là không trỏ tới đâu cả.
  • Con trỏ head để trỏ tới vị trí đầu tiên của danh sách liên kết.

>>>Xem thêm: Mã UTM code là gì? Cách đo lường hiệu quả chiến dịch quảng cáo

Ứng dụng của danh sách liên kết đơn trong thực tế:

Danh sách liên kết
Danh sách liên kết

Danh sách liên kết đơn chủ yếu được dùng để xây dựng các loại cấu trúc dữ liệu khác như ngăn xếp hoặc hàng đợi hoặc đồ thị …

Đôi lúc ta cần biết node ở vị trí trước. Nhưng với danh sách liên kết đơn thì không làm được. Để biết được vị trí của cả các node trước và sau node hiện tại, ta phải lưu cả vị trí của node trước và node sau. Lúc này cấu trúc của một node sẽ có dạng như sau.

Bài viết trên, mình đã chia sẻ tới các bạn chi tiết bài học danh sách liên kết đơn. Cảm ơn các bạn đã theo dõi bài viết nhé!

>>Xem thêm: Tổng hợp các loại mã nguồn làm web phổ biến nhất hiện nay

Mỹ Phượng-Tổng hợp

Tham khảo: (nguyenvanhieu, stdio,…)

Tags: Bài tập danh sách liên kết đơnCode danh sách liên kết đơn sinh viên C++Nhập xuất danh sách liên kết đơnSắp xếp danh sách liên kết đơnTìm kiếm trong danh sách liên kết đơnXóa phần tử trong danh sách liên kết đơn
Bài Viết Trước

Top những ngôn ngữ lập trình ứng dụng Android bạn không nên bỏ lỡ

Bài Viết Tiếp Theo

Cấu trúc dữ liệu và giải thuật – Cây nhị phân tìm kiếm

Bài Viết Tiếp Theo
Img 5f44e1ce36002 1

Cấu trúc dữ liệu và giải thuật - Cây nhị phân tìm kiếm

Bài Viết Mới

Lập trình hướng đối tượng OOP là gì? 5 ngôn ngữ OOP phổ biến nhất

Lập trình hướng đối tượng OOP là gì? 5 ngôn ngữ OOP phổ biến nhất

02/02/2023
Tại sao Python phổ biến trong giới công nghệ hiện nay

Tại sao Python phổ biến trong giới công nghệ hiện nay

23/01/2023

OpenCv là gì? Mã nguồn mở OpenCV đem lại những ích lợi gì?

18/01/2023
Blockchain là gì? Ưu điểm của Blockchain trong cuộc sống

Blockchain là gì? Ưu điểm của Blockchain trong cuộc sống

08/01/2023
8 phần mềm chỉnh sửa ảnh miễn phí tốt nhất hiện nay

8 phần mềm chỉnh sửa ảnh miễn phí tốt nhất hiện nay

03/01/2023
10 phần mềm diệt virus miễn phí tốt nhất hiện nay

10 phần mềm diệt virus miễn phí tốt nhất hiện nay

29/12/2022

Về Chúng Tôi

Source.vn là website download source code free website, phần mềm, đồ án môn học, luận văn tốt nghiệp, tổng hợp các mã nguồn, kiến thức lập trình chuyên nghành công nghệ thông tin.

Chuyên Mục

  • Chưa được phân loại
  • Kiến Thức
  • Source miễn phí
  • Source Tham Khảo
  • Thư Viện
  • Top Source

Bài Viết Mới

  • Lập trình hướng đối tượng OOP là gì? 5 ngôn ngữ OOP phổ biến nhất
  • Tại sao Python phổ biến trong giới công nghệ hiện nay
  • OpenCv là gì? Mã nguồn mở OpenCV đem lại những ích lợi gì?
  • Trang Chủ
  • Top Source
  • Source miễn phí
  • Source Tham Khảo
  • Kiến Thức
  • Thư Viện

© 2023 JNews - Premium WordPress news & magazine theme by Jegtheme.