Tạo danh sách được liên kết vòng tròn trong C#?

Question

Điều gì sẽ là cách tốt nhất để tạo danh sách được liên kết vòng tròn trong C#. Tôi có nên lấy nó từ bộ sưu tập LinkedList < T> không? Tôi đang lập kế hoạch tạo một sổ địa chỉ đơn giản bằng cách sử dụng Danh sách liên kết này để lưu trữ các liên hệ của tôi (nó sẽ là một sổ địa chỉ hút, nhưng tôi không quan tâm vì tôi sẽ là người duy nhất sử dụng nó). Tôi chủ yếu chỉ muốn tạo danh sách liên kết quan trọng để tôi có thể sử dụng lại nó trong các dự án khác.

Nếu bạn không nghĩ Danh sách được liên kết là đúng cách, hãy cho tôi biết cách nào sẽ tốt hơn.

Answer 1

Như hầu hết các câu trả lời không thực sự có được ở các nội dung của câu hỏi, chỉ đơn thuần là ý định, có lẽ điều này sẽ giúp:

Theo như tôi có thể biết sự khác biệt duy nhất giữa một danh sách liên kết và một Thông tư Danh sách được liên kết là hành vi của các trình vòng lặp khi đạt đến cuối hoặc đầu danh sách. Một cách rất dễ dàng để hỗ trợ hành vi của một Danh sách Liên kết Thông tư là viết một phương thức mở rộng cho một LinkedListNode trả về nút tiếp theo trong danh sách hoặc nút đầu tiên nếu không có nút đó, và tương tự để lấy nút trước đó hoặc cuối cùng nếu không có nút nào tồn tại. Đoạn mã sau nên thực hiện điều đó, mặc dù tôi chưa thử nghiệm nó:

static class CircularLinkedList { 
    public static LinkedListNode<T> NextOrFirst<T>(this LinkedListNode<T> current) 
    { 
     return current.Next ?? current.List.First; 
    } 

    public static LinkedListNode<T> PreviousOrLast<T>(this LinkedListNode<T> current) 
    { 
     return current.Previous ?? current.List.Last; 
    } 
} 

Bây giờ bạn chỉ có thể gọi myNode.NextOrFirst() thay vì myNode.Tiếp theo và bạn sẽ có tất cả các hành vi của một danh sách liên kết vòng tròn. Bạn vẫn có thể thực hiện các lần xóa liên tục và chèn trước và sau tất cả các nút trong danh sách và các nút tương tự. Nếu có một số bit quan trọng khác của một danh sách liên kết vòng tròn tôi đang mất tích, hãy cho tôi biết.

Answer 2

Tôi không nghĩ danh sách được liên kết vòng tròn là cấu trúc dữ liệu phù hợp cho danh sách liên hệ. Một danh sách đơn giản <> hoặc Bộ sưu tập <> là đủ.

Answer 3

Có thể là một ý tưởng tồi khi bắt nguồn từ lớp BCL LinkedList. Lớp đó được thiết kế để trở thành một danh sách không tròn. Cố gắng làm cho nó tròn sẽ chỉ gây ra vấn đề cho bạn.

Bạn có thể viết tốt hơn cho chính mình.

Answer 4

Bạn có yêu cầu cụ thể nào để sử dụng danh sách được liên kết vòng tròn (ví dụ: bài tập về nhà) không? Nếu không, tôi khuyên bạn nên sử dụng lớp đơn giản List<T> để lưu trữ danh bạ của bạn.

Answer 5

Làm thế nào về điều này CList based circular list.

Answer 6

Danh sách liên kết thông thường thường được triển khai bằng cách sử dụng các mảng làm cho chúng rất nhanh và bản chất của chúng không yêu cầu thay đổi kích thước động. Bạn chỉ cần kiểm tra nhanh đọc và ghi các chỉ mục để xem liệu chúng có bị mất kết thúc không và nếu có, hãy đặt lại thành 0 (hoặc một, bất kỳ thứ gì).

Tuy nhiên, chúng thường được sử dụng cho những thứ như bộ đệm đầu vào, nơi dữ liệu không có giá trị thực khi đọc. Danh sách liên hệ có giá trị lâu dài và địa chỉ liên hệ mới sẽ ghi đè địa chỉ liên hệ cũ khi danh sách đầy, điều này có thể được chấp nhận trừ khi bạn ghi đè lên người bạn đang để lại cho bạn một khoản tiền trong ý muốn.

---

Tôi không nghĩ rằng danh sách được liên kết là cách hiệu quả nhất để thực hiện bộ đệm tròn (câu hỏi gốc).

Mục đích của bộ đệm tròn là tốc độ và một mảng đơn giản không thể bị đánh bại với tốc độ trong bối cảnh của bộ đệm tròn. Ngay cả khi bạn giữ một con trỏ đến mục danh sách được liên kết được truy cập gần đây nhất của bạn, một mảng sẽ vẫn hiệu quả hơn. Danh sách có khả năng thay đổi kích thước động (trên không) mà không cần thiết cho bộ đệm tròn. Có nói rằng, tôi nghĩ rằng một bộ đệm tròn có lẽ không phải là cấu trúc đúng cho ứng dụng (danh sách liên lạc) bạn đề cập đến.

Answer 7

Tôi nghĩ rằng cấu trúc dữ liệu chính xác nhất cho vấn đề này là danh sách được liên kết hai vòng tròn. Với cấu trúc dữ liệu này, bạn có thể tự do lên xuống qua danh sách địa chỉ liên lạc

Answer 8

class CircularArray<T> : IEnumerator<T> 
{ 
    private readonly T[] array; 
    private int index = -1; 
    public T Current { get; private set; } 

    public CircularArray(T[] array) 
    { 
     Current = default(T); 
     this.array = array; 
    } 

    object IEnumerator.Current 
    { 
     get { return Current; } 
    } 

    public bool MoveNext() 
    { 
     if (++index >= array.Length) 
      index = 0; 
     Current = array[index]; 
     return true; 
    } 

    public void Reset() 
    { 
     index = -1; 
    } 

    public void Dispose() { } 
} 

Answer 9

class Program 
{ 
    static void Main(string[] args) 
    { 
     int[] numbers = { 1, 2, 3, 4, 5, 6, 7 }; 

     IEnumerable<int> circularNumbers = numbers.AsCircular(); 

     IEnumerable<int> firstFourNumbers = circularNumbers.Take(4); // 1 2 3 4 
     IEnumerable<int> nextSevenNumbersfromfourth = circularNumbers 
      .Skip(4).Take(7); // 4 5 6 7 1 2 3 
    } 
} 

public static class CircularEnumerable 
{ 
    public static IEnumerable<T> AsCircular<T>(this IEnumerable<T> source) 
    { 
     if (source == null) 
      yield break; // be a gentleman 

     IEnumerator<T> enumerator = source.GetEnumerator(); 

     iterateAllAndBackToStart: 
     while (enumerator.MoveNext()) 
      yield return enumerator.Current; 

     enumerator.Reset(); 
     if(!enumerator.MoveNext()) 
      yield break; 
     else 
      yield return enumerator.Current; 
goto iterateAllAndBackToStart; 
    } 
} 

Nếu bạn muốn đi xa hơn, làm cho một CircularList và giữ các điều tra viên cùng bỏ qua Skip() khi quay giống như trong mẫu của bạn.

Answer 10

Giải pháp dựa trên mô đun.

Nếu bộ đệm tròn được thực hiện như một mảng nguyên (hoặc bất kỳ loại khác của bộ sưu tập cho những gì nó quan trọng)

T[] array; 

và chúng tôi lưu trữ vào int current_index chỉ số của mặt hàng đó hiện nay, chúng ta có thể chu kỳ tăng và xuống đệm như sau:

T NextOrFirst() 
{ 
    return array[(current_index + 1) % array.Length]; 
} 

T PreviousOrLast() 
{ 
    return array[(current_index + array.Length - 1) % array.Length]; 
} 

cách tiếp cận tương tự có thể được sử dụng với bất kỳ bộ sưu tập ràng buộc XAML.