Làm thế nào để thêm một LinkedList <T> vào một LinkedList <T> trong C#?

Question

Chúng tôi từng nghĩ mã đơn giản

llist1.Last.Next = llist2.First; 
llist2.First.Previous = llist1.Last; 

sẽ làm việc, tuy nhiên dường như trong C# 's LinkedList, Thứ nhất, năm ngoái, và tài sản của họ là Get chỉ.

Phương pháp khác mà tôi có thể nghĩ là

llist1.AddLast(llist2.First); 

Tuy nhiên, điều này không làm việc, hoặc - nó không thành công vì nút đầu tiên của llist2 là đã có trong danh sách liên kết.

Điều này có nghĩa là tôi phải có vòng lặp cho mỗi nút của danh sách llist2 theo cách thủ công để llist1? Điều này không đánh bại hiệu quả của các danh sách được liên kết ????

Answer 1

llist1 = new LinkedList<T>(llist1.Concat(llist2)); 

kết hợp hai danh sách này (yêu cầu .NET 3.5). Nhược điểm là nó tạo ra một thể hiện mới của LinkedList, mà có thể không phải là những gì bạn muốn ... Bạn có thể làm một cái gì đó như thế thay vào đó:

foreach(var item in llist2) 
{ 
    llist1.AddLast(item); 
} 

Answer 2

Có, bạn phải lặp lại, thật không may. Đây là một hoạt động O (n) - O (1) cho mỗi mục nhập được thêm vào. Không có nguy cơ đòi hỏi một bộ đệm được thay đổi kích cỡ và sao chép, vv - mặc dù tất nhiên thu gom rác thải có thể làm khoảng đó :) Bạn thậm chí có thể viết phương pháp khuyến nông có ích:

public static class LinkedListExtensions 
{ 
    public static void AppendRange<T>(this LinkedList<T> source, 
             IEnumerable<T> items) 
    { 
     foreach (T item in items) 
     { 
      source.AddLast(item); 
     } 
    } 

    public static void PrependRange<T>(this LinkedList<T> source, 
             IEnumerable<T> items) 
    { 
     LinkedListNode<T> first = source.First; 
     foreach (T item in items) 
     { 
      source.AddBefore(first, item); 
     } 
    } 
} 

EDIT: Cảm nhận Erich của cho thấy lý do tại sao bạn có thể nghĩ điều này là không hiệu quả - tại sao không chỉ tham gia hai danh sách với nhau bằng cách cập nhật con trỏ "tiếp theo" của đuôi của danh sách đầu tiên và con trỏ "trước" của người đứng đầu thứ hai? Hãy suy nghĩ về những gì sẽ xảy ra với danh sách thứ hai ... nó cũng sẽ thay đổi.

Không chỉ vậy, nhưng điều gì sẽ xảy ra với quyền sở hữu của các nút đó? Mỗi phần cơ bản là một phần của hai danh sách bây giờ ... nhưng thuộc tính LinkedListNode<T>.List chỉ có thể nói về một trong số chúng.

Trong khi tôi có thể thấy lý do tại sao bạn có thể muốn thực hiện việc này trong một số trường hợp, cách kiểu .NET LinkedList<T> đã được xây dựng cơ bản nghiêm cấm nó. Tôi nghĩ rằng bình luận doc điều này giải thích nó tốt nhất:

Lớp LinkedList<T>) không không hỗ trợ chaining, tách, chu kỳ, hoặc các tính năng khác có thể rời khỏi danh sách trong một không ổn định.

Answer 3

Ở đây bạn có thể tìm thấy việc triển khai danh sách được liên kết với O (1) thời gian trùng lặp và chia nhỏ.

Why .NET LinkedList does not support Concat and Split operations?

tóm tắt ngắn

Ưu vs.NET LinkedList:

• Ít tiêu thụ bộ nhớ, do đó mỗi SimpleLinkedListNode nút có ba con trỏ (trước, sau, giá trị) thay vì bốn (trước, sau, danh sách, giá trị) không giống như thực hiện NET gốc.

• Hỗ trợ concat và Split hoạt động trong thời gian O (1)

• Hỗ trợ IEnumarable Xếp() Enumerator trong O (1) - bằng cách này tôi không thấy bất kỳ lý do tại sao nó không được cung cấp natively trên .NET LinkedList. Phương pháp khuyến nông thích hợp yêu cầu O (n).

Nhược điểm:

• Không hỗ trợ Count.
• Hoạt động liên kết để lại danh sách thứ hai ở trạng thái không nhất quán.
• Hoạt động tách rời khỏi danh sách gốc ở trạng thái không nhất quán.
• Bạn có thể chia sẻ các nút giữa các danh sách.

khác:

• tôi đã chọn một chiến lược thay thế cho việc thực hiện kê khai, tìm hoạt động, chứ không phải là thực hiện ban đầu tiết hơn và hoàn toàn có thể đọc được. Tôi hy vọng tác động hiệu suất tiêu cực vẫn không đáng kể.