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

Hướng dẫn AOP Spring

Lập trình hướng đối tượng (AOP) khen ngợi OOP theo nghĩa là nó cũng cung cấp tính mô đun. Nhưng đơn vị chính của...

Bộ sưu tập cho người mới bắt đầu Java

Set là một Khung bộ sưu tập Java. Set là một Giao diện trong gói java.util . Nó thực hiện Bộ sưu tập Giao diện.

URI tùy chỉnh trong thẻ tùy chỉnh JSP

Chúng ta có thể sử dụng URI tùy chỉnh, để báo cho bộ chứa web về tệp tld. Trong trường hợp như vậy,...

Tiêm phụ thuộc với phương pháp nhà máy vào Spring

Spring framework cung cấp cơ sở để tiêm đậu bằng phương pháp nhà máy. Để làm như vậy, chúng ta có thể sử...

Sưu tập bản đồ cho người mới bắt đầu Java

Bản đồ là một Giao diện đi theo khung Bộ sưu tập Java. Map Collection Tutorial for...

Lặp lại bằng cách sử dụng thẻ tùy chỉnh JSP

Chúng ta có thể lặp lại nội dung thân của bất kỳ thẻ nào bằng phương thức doAfterBody () của giao diện IterationTag .

Leave a reply

Please enter your comment!
Please enter your name here