Danh sách liên kết

Danh sách liên kết là một cấu trúc dữ liệu khác và cũng là cấu trúc dữ liệu phổ biến bao gồm một nhóm các nút theo trình tự được chia thành hai phần và mỗi nút bao gồm dữ liệu và phần địa chỉ của nút tiếp theo và tạo thành một chuỗi. Nó được sử dụng để tạo một cây và đồ thị.

lap-trinh-java
Linked Lists

Bằng khen

  • Đó là bản chất động và nó phân bổ bộ nhớ theo yêu cầu.
  • Có hai thao tác có thể được thực hiện dễ dàng trong các danh sách được, đó là Chèn và Xóa.
  • Nó làm giảm thời gian truy cập.

Yêu cầu

  • Bộ nhớ bị lãng phí vì con trỏ yêu cầu thêm bộ nhớ để lưu trữ.
  • Phần tử không thể được truy cập ngẫu nhiên, nó có thể được truy cập tuần tự.
  • Trong danh sách liên kết ngược lại là khó khăn.

Danh sách liên kết được sử dụng ở đâu?

1. Chúng được sử dụng để thực hiện ngăn xếp, hàng đợi, đồ thị, v.v.

2. Họ cho phép bạn chèn các phần tử ở đầu và cuối danh sách.

3. Trong trường hợp này, nó không đòi hỏi phải biết kích thước trước.

Các loại danh sách liên kết

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

Loại danh sách này chứa các nút có một phần dữ liệu cũng như một phần địa chỉ, tức là tiếp theo và nó trỏ đến nút tiếp theo trong chuỗi các nút đã cho. 

Các hoạt động chúng ta có thể thực hiện trên các danh sách liên kết đơn được chèn, xóa và truyền tải.

Danh sách liên kết đôi

Trong loại danh sách này, mỗi nút chứa hai liên kết, liên kết đầu tiên sẽ trỏ đến nút trước đó và liên kết tiếp theo sẽ trỏ đến nút tiếp theo trong chuỗi.

  • Danh sách liên kết tròn – Trong loại danh sách này, nút cuối cùng của danh sách chứa địa chỉ của nút đầu tiên và sẽ tạo thành một chuỗi vòng tròn.

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

Danh sách liên kết đơn là trong đó mỗi nút chỉ chứa một trường liên kết trỏ đến nút tiếp theo. Trong phần này, nút được chia thành hai phần, phần đầu tiên là phần dữ liệu và phần còn lại là phần liên kết chứa địa chỉ của nút tiếp theo. 

Nút đầu tiên là nút tiêu đề chứa dữ liệu và địa chỉ của nút tiếp theo, v.v. Danh sách liên kết đơn cũng được gọi là danh sách một chiều vì nó chỉ có thể đi qua từ trái sang phải, cách khác là không thể.

Trường hợp danh sách liên kết đơn được sử dụng?

Danh sách liên kết đơn có thể được sử dụng trong các ngăn xếp sử dụng khái niệm cuối cùng, trước hết. D

Danh sách liên kết đôi

Danh sách liên kết đôi cũng được gọi là danh sách hai chiều hoặc chuỗi hai chiều. Trong danh sách liên kết đôi, hai trường liên kết được duy trì thay vì một như trong danh sách liên kết đơn.

Trường hợp danh sách liên kết đôi được sử dụng?

  1. Nó được sử dụng để đại diện cho bộ bài trong trò chơi.
  2. Nó được sử dụng trong các ứng dụng có danh sách được sử dụng gần đây nhất.
  3. Nó được sử dụng như một chức năng hoàn tác trong Word hoặc Photoshop.
  4. Nó được sử dụng trong bộ đệm của trình duyệt cho phép chúng ta nhấn nút BACK.

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

Danh sách liên kết tròn là cấu trúc dữ liệu được liên kết phức tạp một chút. Trong danh sách này, chúng ta có thể chèn các phần tử vào bất kỳ vị trí nào trong danh sách trong khi trong mảng chúng ta không thể chèn các phần tử vào bất kỳ vị trí nào trong danh sách vì nó nằm trong bộ nhớ liền kề. 

Trong danh sách này, phần tử trước lưu địa chỉ của phần tử tiếp theo và phần tử cuối cùng lưu địa chỉ của phần tử đầu tiên. Các yếu tố trong danh sách chỉ vào nhau theo cách vòng tròn tạo thành chuỗi vòng tròn. Danh sách này có kích thước động có nghĩa là bộ nhớ có thể được phân bổ theo và khi nào được yêu cầu.

Trường hợp danh sách liên kết tròn được sử dụng?

Ứng dụng thực tế nơi danh sách này được sử dụng là PC nơi có nhiều ứng dụng chạy trên nó. 

Danh sách liên kết vòng tròn là phổ biến trong hệ điều hành vì nó đưa các ứng dụng đang chạy vào danh sách và hệ điều hành dễ dàng sử dụng danh sách liên kết vòng tròn như khi danh sách sắp đến cuối hệ điều hành có thể quay vòng phía trước danh sách Khe thời gian được cung cấp cho từng ứng dụng trong danh sách.

Danh sách liên kết tuyến tính

Trong danh sách được liên kết, chúng ta có thể chèn các phần tử theo ba cách:

  • Chèn vào đầu danh sách.
  • Chèn vào giữa danh sách.
  • Chèn vào cuối danh sách.

Bài viết gần đây

So sánh JAVA vs C++

Hôm nay trong bài viết này mình sẽ so sánh Java vs C++. Còn nếu bạn muốn đọc thêm về so sánh Java vs PHP hay Java với C# thì xem thêm tại đây:

Tính năng của Java

11 tính năng chính đóng một vai trò quan trọng trong sự phổ biến của ngôn ngữ Java. Các tính năng của Java còn được gọi là Java buzzwords.

Lịch Sử của JAVA – Ngôn ngữ Lập trình Phổ biến nhất thế giới

Java đã đi qua gần 25 năm lịch sử hình thành và phát triển. Theo chỉ số TOIBE Index thì Java hiện tại vẫn đang là ngôn ngữ Lập trình phổ biến nhất thế giới.

JAVA là gì? | JAVA DEV

Java là một ngôn ngữ lập trình và là một nền tảng mạnh mẽ. Cùng tìm hiểu kỹ hơn về Java với Java DEV

Tại sao xử lý một mảng được sắp xếp nhanh hơn xử lý một mảng chưa sắp xếp?

Tại sao xử lý một mảng được sắp xếp nhanh hơn xử lý một mảng chưa sắp xếp | Lập trình viên Java, Java DEV

Hướng dẫn chủ đề Java

Một Instance of Thread là một đối tượng giống như bất kỳ đối tượng nào khác trong Java và nó chứa các biến và...

Leave a reply

Please enter your comment!
Please enter your name here