Ví dụ thế giới thực khi nào Danh sách được liên kết nên được sử dụng?

Question

Một lập trình viên khác đã đề cập rằng họ đã không tìm thấy trường hợp sử dụng để sử dụng cấu trúc dữ liệu danh sách được liên kết trong bất kỳ phần mềm chuyên nghiệp nào trong sự nghiệp của mình. Tôi không thể nghĩ ra bất kỳ ví dụ tốt nào trên đỉnh đầu của tôi. Ông chủ yếu là nhà phát triển C# và Java

Bất kỳ ai có thể đưa ra một số ví dụ về cấu trúc dữ liệu chính xác để giải quyết một vấn đề thế giới thực cụ thể không?

liên quan:What is a practical, real world example of the Linked List?

Answer 1

Ví dụ thực tế sẽ là hàng đợi FIFO. Một danh sách dựa trên mảng đơn giản là khá xấu vì bạn cần thêm vào một đầu và xóa ở đầu kia, và một trong các hoạt động đó sẽ là O (n) với một danh sách dựa trên mảng (trừ khi bạn thêm logic bổ sung vào làm việc với chỉ mục bắt đầu và kết thúc), trong khi cả hai đều là O (1) với danh sách được liên kết mà không cần nỗ lực thêm.

Answer 2

Ngăn xếp và hàng đợi là ví dụ về danh sách liên kết.

Answer 3

Đối với các sự cố trong đó số lượng nút tối đa bị giới hạn ở 100 hoặc thấp hơn hoặc hơn, danh sách được liên kết là một giải pháp hợp lý. Điều tương tự cũng có thể đúng với những thứ như loại bong bóng và những thứ khác được cho là không tối ưu.

Answer 4

Danh sách được liên kết cung cấp một số lợi thế so với cấu trúc dữ liệu có thể so sánh như mảng tĩnh hoặc mở rộng động.

1. LinkedLists liều không đòi hỏi khối tiếp giáp bộ nhớ và do đó có thể giúp giảm sự phân mảnh bộ nhớ
2. LinkedLists hỗ trợ loại bỏ hiệu quả của các yếu tố (mảng động thường buộc một sự thay đổi trong tất cả các yếu tố).
3. LinkedLists hỗ trợ bổ sung hiệu quả của các yếu tố (mảng động có thể gây ra một tái phân bổ + sao chép nếu một add đặc biệt vượt quá khả năng hiện tại)

Bất cứ nơi đâu những lợi thế này sẽ có giá trị đáng kể vào một chương trình (và bất lợi của một LinkedList là không đáng kể) sẽ là một nơi để sử dụng LinkedList.

Answer 5

Vì daustin777 chỉ ra, danh sách được liên kết là tất cả xung quanh bạn và thậm chí bạn có thể không biết điều đó. Nhưng tính thiết thực của vấn đề là chúng cho phép một số hoạt động khá cơ bản được thực hiện một cách dễ dàng và linh hoạt tương đối. Ví dụ, không phải để sắp xếp, chỉ cần trao đổi con trỏ xung quanh. Cần phải chèn hoặc loại bỏ tại các vị trí tùy ý? Chèn hoặc xóa con trỏ của bạn trong danh sách. Cần lặp lại và chuyển tiếp ... danh sách liên kết. Mặc dù không chính xác là một ví dụ kinh doanh, tôi hy vọng điều này làm rõ nó đủ để bạn áp dụng nó vào trường hợp kinh doanh thế giới thực của riêng bạn.

Answer 6

An bất biến danh sách được liên kết là một cấu trúc rất có giá trị, vì bạn có thể 'chia sẻ cấu trúc' với các danh sách khác có cùng đuôi. Hầu hết các ngôn ngữ chức năng bao gồm một loại danh sách liên kết bất biến là một trong những cấu trúc dữ liệu cơ bản của chúng và các loại này được sử dụng khắp nơi.

Answer 7

ưu danh sách liên kết:

• động lưu trữ làm vô hiệu phân mảnh
• nhanh chèn/loại bỏ
• truy cập nhanh đến phần tử đầu tiên (và kết thúc nếu hai chiều thực hiện)
• sử dụng bộ nhớ hiệu quả

Đối sánh danh sách được liên kết:

• chậm traversing

Out đầu của tôi, tôi muốn thực hiện ngăn xếp, hàng đợi và messagepumps sử dụng danh sách liên kết. Tôi cũng sẽ triển khai một datatree sử dụng các danh sách liên kết đa tham chiếu để chèn/loại bỏ nhanh chóng.

Answer 8

Ngăn xếp và hàng đợi là những ví dụ rất rõ ràng về danh sách liên kết, nhưng khi khác đã đã đề cập đến chúng tôi muốn thêm một vài ví dụ khác: các cửa hàng

DOM node như danh sách liên kết. Một mẫu javascript đơn giản thực sự giống nhau ở bất kỳ ngôn ngữ nào:

for (var node = parent.firstChild; node != null; node = node.nextSibling) { 
    // .. 
} 

Tôi tưởng tượng rằng một nhà phát triển java đã gặp XML tại một thời điểm nào đó.

Cây là một ví dụ hay khác về danh sách được liên kết, mặc dù chúng không phải là các danh sách một chiều đơn giản. Một người nào đó đã thực hiện rất nhiều phát triển java có lẽ đã bắt gặp TreeMaps và TreeSets.

Toàn bộ cuộc thảo luận có vẻ hơi ngớ ngẩn đối với tôi. Danh sách được liên kết là cấu trúc dữ liệu cơ bản được sử dụng ở mọi nơi. Lý do duy nhất mà người ta có thể nghĩ rằng anh ta/cô ấy đã không gặp họ là bạn không thực sự phải lo lắng về việc thực hiện cấu trúc dữ liệu trong các ngôn ngữ cấp cao ngày nay, nhưng tất nhiên họ vẫn còn ở đó.

Answer 9

Chúng xảy ra mọi lúc, mọi nơi mà đối tượng có thuộc tính trỏ đến đối tượng khác cùng loại. Trong CLR, các ngoại lệ tạo thành một danh sách liên kết, do thuộc tính InnerException.

Answer 10

Như đã nói, danh sách được liên kết rất hữu ích khi bạn cần chèn và xóa các phần tử. Ví dụ để giúp gỡ lỗi quản lý bộ nhớ trong mã của tôi Gần đây tôi đã thực hiện một danh sách liên kết giữa tất cả các đối tượng được tính toán của tôi để cuối chương trình (khi tất cả các điện trở đều bị xóa và xóa đối tượng), tôi có thể xem chính xác những gì còn lại, kết quả là tôi có thể tìm thấy một đối tượng duy nhất ở gốc của vấn đề.

CPython thực hiện một thứ gì đó tương tự với một danh sách liên kết lớn giữa gần như mọi khi được tạo bằng gỡ lỗi.

Answer 11

Danh sách liên kết xâm nhập là những con thú thú vị để phát triển trò chơi.Ví dụ, đó là thực hành hơi phổ biến để có một singly- xâm nhập hoặc gấp đôi liên kết "render" danh sách:

 
class Renderable /* or class Object, whatever */ 
{ 
    // ... 
    Renderable * m_pNext; 
    Renderable * m_pPrev; // or not, if singly-linked 
    // ... 
} 

Như Renderables đi vào và ra khỏi sự tồn tại họ có thể đăng ký chính nó với danh sách này - mà không gây ra bất kỳ bộ nhớ phân bổ. Nếu độ sâu hoặc độ ưu tiên hiển thị của chúng bị thay đổi, chúng có thể xóa và tự lắp lại, v.v.

Khi đến lúc kết xuất, tất cả những gì bạn cần làm là tìm đầu danh sách và zip, gọi phương thức thích hợp!

(Có, tất nhiên, nhiều biến thể về chủ đề này, với nhiều danh sách riêng biệt, v.v. Và bạn không cần phải có danh sách xâm nhập để thực hiện công việc này, tôi chỉ tìm những thứ xâm nhập thú vị.)

Answer 12

Danh sách được liên kết (paired with a hashtable) thực sự hữu ích cho LRU Caches.

Mỗi lần Nhận cần phải đưa nút đến trước danh sách, thao tác thực sự rẻ với danh sách được liên kết.

Answer 13

Trả lời thẻ 'Cấu trúc dữ liệu' ở mức thấp như lắp ráp, danh sách được liên kết là một cách lý tưởng để lưu trữ danh sách độ dài biến của cấu trúc dữ liệu khác. Không có phí để duy trì độ dài danh sách hoặc kết thúc và không cần các mục danh sách kích thước cố định. Lý do cuối cùng cũng áp dụng cho các ngôn ngữ cấp cao hơn.

Answer 14

Có lẽ ví dụ thế giới thực tốt nhất trong. Net xem xét MultiCastDelegate.

Danh sách được liên kết được triển khai theo cách này, khi khía cạnh chuỗi danh sách được sao lưu trực tiếp vào loại chứ không phải dưới dạng vùng chứa riêng biệt, có thể cực kỳ mạnh mẽ và hiệu quả. Tuy nhiên, họ đến với một loạt các thương mại.
Một trong những rõ ràng là sao chép mã, bạn phải nướng logic này trong từng loại. Các kỹ thuật như mở rộng một lớp cơ sở cung cấp con trỏ là lộn xộn (bạn bị đánh mạnh mẽ mà không có generics) và thường không thể chấp nhận được từ một quan điểm thực hiện.
Một cách khác là bạn bị giới hạn ở một triển khai cho mỗi loại. Bạn không thể tạo một cấu trúc được liên kết đơn lẻ thành một cấu trúc được liên kết kép mà không chèn thêm một trường bổ sung trong mọi trường hợp và cập nhật tất cả các mã có liên quan.

Answer 15

Tôi đã viết một phần mở rộng BIOS (về cơ bản là một trình điều khiển thiết bị cho một BIOS, được viết trong assembly) cho một bộ điều khiển máy chủ USB. - Việc thực hiện một cấu trúc dữ liệu dường như có vẻ cao cấp như một danh sách liên kết trong hội đồng không khó như âm thanh. - Bộ điều khiển phục vụ các yêu cầu I/O cho bàn phím và đĩa bằng cách sử dụng danh sách các gói được liên kết trong bộ nhớ chính. Tôi đã duy trì một nhóm các gói miễn phí trong một danh sách liên kết khác. Thực hiện I/O về cơ bản lấy một gói miễn phí từ đầu danh sách miễn phí, cấu hình gói, thêm gói vào danh sách thiết bị và thêm lại gói vào đầu hồ bơi miễn phí khi I/O kết thúc. Danh sách liên kết nhanh như chớp để di chuyển xung quanh các đối tượng như thế này, đặc biệt khi các đối tượng lớn, vì các đối tượng không thực sự phải di chuyển. Chỉ con trỏ của họ cần được cập nhật.

Một hàng đợi mảng dựa trên sẽ có yêu cầu:

• sử dụng bắt đầu/kết thúc con trỏ chỉ số, mà là nhanh chóng nhưng đòi hỏi phải sửa chữa các kích thước của hàng đợi để các nhà sản xuất phải đợi khi hàng đợi của người tiêu dùng là đầy đủ và khóa hàng đợi trong khi toàn bộ gói tin được điền nếu có nhiều hơn một nhà sản xuất
• chuyển tất cả các yếu tố trong hàng đợi bất cứ khi nào bạn chèn/xóa, mà là chậm đối với các đối tượng lớn

danh sách vì vậy, liên kết là một cách hay để triển khai n hàng đợi đầu tiên trong các hàng lớn. Một điều khác cần lưu ý là đối với các đối tượng nhỏ hoặc nơi bạn phân bổ các đối tượng từ một đống thông thường thay vì một nhóm tùy chỉnh miễn phí, mảng có thể nhanh hơn vì sao chép không thực sự chậm nếu nó không được thực hiện thường xuyên, và phân bổ lặp đi lặp lại từ heap mà một danh sách liên kết sẽ yêu cầu mỗi lần một phần tử mới được thêm vào là chậm.

Tất nhiên, bạn có thể muốn mô phỏng và đo lường kịch bản cụ thể của bạn với một số mã kiểm tra throwaway để tìm câu trả lời. Tôi thích chạy vòng một vài triệu lần với danh sách liên kết và mảng, với các đối tượng nhỏ và lớn, và thời gian mỗi lần mất trong thời gian thực. Đôi khi bạn sẽ ngạc nhiên.

Answer 16

danh sách liên kết là cấu trúc cơ bản dữ liệu cho Dancing Links, mà là kỹ thuật sử dụng để thực hiện một cách hiệu quả Algorithm X, mà là một thuật toán quay lui để tìm tất cả các giải pháp cho vấn đề NP-đầy đủ exact cover, mà nhiều vấn đề khó khăn là một cách tự nhiên rút gọn về .

Answer 17

Nếu tôi có thể trả lời câu hỏi này theo cách hơi khác so với những người khác, gần đây tôi đã sử dụng danh sách được liên kết để sắp xếp danh sách nhạc. Danh sách cung cấp một cách tuyệt vời để lưu trữ và sắp xếp thông qua âm nhạc của nghệ sĩ, bài hát, album, thậm chí xếp hạng hoặc độ dài bài hát. Mỏ là một danh sách liên kết kép, nhưng tôi có thể thấy nó được áp dụng với một danh sách liên kết đơn lẻ. Danh sách mua sắm sẽ phù hợp là tốt, và nếu bạn là OCD như mẹ tôi, bạn có thể dễ dàng tổ chức nó là lối đi và thực phẩm đông lạnh cuối cùng!

Nếu chúng tôi bao gồm ngăn xếp và hàng đợi, hiển nhiên đối với hàng đợi là hàng đợi in hoặc danh sách phát nhạc (danh sách theo bất kỳ nghĩa nào rõ ràng là tốt).

Answer 18

Một số ví dụ về danh sách được liên kết duy nhất.

1. Nút hoàn tác của bất kỳ ứng dụng nào như Microsoft Word, Paint, v.v ...: Danh sách các trạng thái được liên kết.
2. Điều hướng GPS: Danh sách dữ liệu bản đồ được liên kết. Di chuyển từ nguồn gốc đến đích là ví dụ về truyền tải qua tất cả các nút. Định tuyến lại bằng GPS là ví dụ về thao tác Thêm và Xóa dữ liệu bản đồ.

Một số ví dụ về danh sách được liên kết kép.

1. Trình duyệt của Next và nút Previous: một danh sách liên kết URL Microsoft
2. Image Viewer của Next và nút Previous: một danh sách liên kết các hình ảnh
3. Undo và nút của Photoshop, một danh sách liên kết của các quốc gia Redo.