C#의 LinkedList <T>에 LinkedList <T>을 추가하는 방법은 무엇입니까?

Question

하나는

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

먼저 C#의 LinkedList의, 마지막으로 그러나 분명히 작동합니다 간단한 코드를 생각하고, 그 속성은 얻을 수 있습니다. llist2의 첫 번째 노드가 링크 된 목록에 이미 있기 때문에 실패 - 내가 생각할 수

다른 방법은

llist1.AddLast(llist2.First); 

그러나,이 중 하나가 작동하지 않습니다이었다.

이렇게하면 llist1의 각 노드를 AddLast의 AddLast에 수동으로 추가해야한다는 루프가 필요합니까? 링크드리스트의 효율성을 떨어 뜨리지 않습니까 ??

Answer 1

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

이 두 목록을 연결합니다 (.NET 3.5 필요).

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

Answer 2

예, 당신은 루프를 가지고, 불행히도 : 단점은 당신이 대신 같은 것을 할 수 ... 당신이 원하는 것을하지 않을 수 있습니다 LinkedList의 새로운 인스턴스를 생성한다는 것이다. 이것은 추가 된 각 항목에 대해 O (n) 연산 - O (1) 연산입니다.

는

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); 
     } 
    } 
} 

편집 : 에리히의 의견은 제안 당신이 생각하는 이유는 물론 쓰레기 수거 당신도 편리 확장 방법을 쓸 수 :) 것을 대략 할 수도 있지만 - 버퍼를 요구하는 위험이 등이 크기를 조정하지 않고 복사 할 것 이것은 비효율적입니다 - 왜 그냥 첫 번째 목록의 꼬리의 "다음"포인터와 두 번째 머리의 "이전"포인터를 업데이 트하여 두 목록을 함께 가입하지? 글쎄, 두 번째 목록에 무슨 일이 일어날 지 생각해 ... 도 변경되었을 것입니다.

뿐만 아니라 노드의 소유권은 어떻게됩니까? 각각은 본질적으로 두 가지 목록의 일부입니다 ... 그러나 LinkedListNode<T>.List 속성은 그 중 하나에 대해서만 말할 수 있습니다.

어떤 경우에이 작업을 수행해야하는 이유는 알 수 있지만 .NET LinkedList<T> 형식이 기본적으로 빌드 된 방식은 기본적으로 금지되어 있습니다. 나는이 다큐 멘 테이션 코멘트는 가장 잘 설명 생각 :

는 LinkedList<T>) 클래스는 이 일관성 상태 목록을 남길 수 있습니다 분할, 주기, 또는 다른 기능을 체인 지원하지 않습니다.

Answer 3

여기서 O (1) 연결 및 분할 시간을 사용하여 연결된 목록 구현을 찾을 수 있습니다.

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

짧은 요약

장점 대.NET LinkedList의 :

• 적은 메모리 사용, 따라서 모든 노드 SimpleLinkedListNode는 세 가지 포인터가 있습니다 (이전, 다음, 값) 대신 원래 .NET 구현 달리 네 (다음 이전, 목록, 값).

• 가 O에서 CONCAT 및 분할 작업을 지원 (1)

• 는에 IEnumarable 역() 열거 지원 O (1) - 나는 그것이 기본적으로에 를 제공하지 왜 어떤 이유가 표시되지 않는 방법으로 .NET LinkedList. 적절한 확장 방법 에는 O (n)이 필요합니다.

단점 :

• 이 카운트를 지원하지 않습니다.
• Concat 작업은 두 번째 목록을 일관성없는 상태로 둡니다.
• 분할 작업으로 원본 목록의 일관성이 유지됩니다.
• 목록간에 노드를 공유 할 수 있습니다. 다른

: 나는 오히려 더 자세한 순수하게 읽을 수있는 원래의 구현보다, 열거를 구현 및 운영을 찾기위한 대안 전략을 선택한

• . 부정적 성능 영향이 미미한 상태로 유지되기를 바랍니다.