c# 高级编程 10章214页 【集合】【链表LinkedL

发表于

LinkedList<T>

  • 双向链表。通过移动到下一个元素，可以正向遍历整个链表。通过移动到前一个元素，可以反向遍历整个链表
  • 插入元素，效率很高。只需要修改前一个元素的Next和后一个元素的Previous。相比之下，List<T>插入元素，需要移动后面所有元素。
  • 要访问链表位于中间的元素，效率较低。只能从头或者从尾一个一个找过去。
  • 元素为LinkedListNode<T>
成员 说明
First 第一个元素
Last 最后一个元素
AddAfter() 指定位置后，插入
AddBefore() 指定位置前，插入
AddFirst() 插入到最前面
AddLast() 插入到最后面
Remove() 指定位置，删除
RemoveFirst() 删除第一个
RemoveLast() 删除最后一个
Find() 从链表头，开始找
FindLast() 从链表尾，开始找

LinkedListNode<T>

成员 说明
List 与此Node，相关的LinkedList<T>对象
Next 下一个Node
Previous 前一个Node
Value 此Node中，T类型的值

示例

  • 动态插入Document的过程中，需要保持一种秩序
  • 这种秩序是：
    • Priority高的，排在前面
    • Priority相同时，先插入的排在前面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
js复制代码    class Program
    {
        static void Main()
        {
            var pdm = new PriorityDocumentManager();
            pdm.AddDocument(new Document("one", "Sample", 8));
            pdm.AddDocument(new Document("two", "Sample", 3));
            pdm.AddDocument(new Document("three", "Sample", 4));
            pdm.AddDocument(new Document("four", "Sample", 8));
            pdm.AddDocument(new Document("five", "Sample", 1));
            pdm.AddDocument(new Document("six", "Sample", 9));
            pdm.AddDocument(new Document("seven", "Sample", 1));
            pdm.AddDocument(new Document("eight", "Sample", 1));

            pdm.DisplayAllNodes();
        }
    }
    
  public class Document
  {
       public Document(string title, string content, byte priority)
       {
           Title = title;
           Content = content;
           Priority = priority;
       }

       public string Title { get;  }
       public string Content { get; }
       public byte Priority { get; }
  }

输出：

1
2
3
4
5
6
7
8
js复制代码priority: 9, title six
priority: 8, title one
priority: 8, title four
priority: 4, title three
priority: 3, title two
priority: 1, title five
priority: 1, title seven
priority: 1, title eight

实现：

  • List<LinkedListNode<Document>> _priorityNodes用来存储，在每一个Priority上，已经插入了的，最新的，Document。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
js复制代码    public class PriorityDocumentManager
    {
        private readonly LinkedList<Document> _documentList;

        // priorities 0.9
        private readonly List<LinkedListNode<Document>> _priorityNodes;

        public PriorityDocumentManager()
        {
            _documentList = new LinkedList<Document>();

            _priorityNodes = new List<LinkedListNode<Document>>(10);
            for (int i = 0; i < 10; i++)
            {
                _priorityNodes.Add(new LinkedListNode<Document>(null));
            }
        }

        public void AddDocument(Document d)
        {
            if (d is null) throw new ArgumentNullException(nameof(d));

            AddDocumentToPriorityNode(d, d.Priority);
        }

        private void AddDocumentToPriorityNode(Document doc, int priority)
        {
            if (priority > 9 || priority < 0)
                throw new ArgumentException("Priority must be between 0 and 9");

            if (_priorityNodes[priority].Value == null)
            {
                --priority;
                if (priority >= 0)
                {
                    // check for the next lower priority
                    AddDocumentToPriorityNode(doc, priority);
                }
                else // now no priority node exists with the same priority or lower
                     // add the new document to the end
                {
                    _documentList.AddLast(doc);
                    _priorityNodes[doc.Priority] = _documentList.Last;
                }
                return;
            }
            else // a priority node exists
            {
                LinkedListNode<Document> prioNode = _priorityNodes[priority];
                if (priority == doc.Priority)
                // priority node with the same priority exists
                {
                    _documentList.AddAfter(prioNode, doc);

                    // set the priority node to the last document with the same priority
                    _priorityNodes[doc.Priority] = prioNode.Next;
                }
                else // only priority node with a lower priority exists
                {
                    // get the first node of the lower priority
                    LinkedListNode<Document> firstPrioNode = prioNode;

                    while (firstPrioNode.Previous != null &&
                       firstPrioNode.Previous.Value.Priority == prioNode.Value.Priority)
                    {
                        firstPrioNode = prioNode.Previous;
                        prioNode = firstPrioNode;
                    }

                    _documentList.AddBefore(firstPrioNode, doc);

                    // set the priority node to the new value
                    _priorityNodes[doc.Priority] = firstPrioNode.Previous;
                }
            }
        }

        public void DisplayAllNodes()
        {
            foreach (Document doc in _documentList)
            {
                Console.WriteLine($"priority: {doc.Priority}, title {doc.Title}");
            }
        }

        // returns the document with the highest priority
        // (that's first in the linked list)
        public Document GetDocument()
        {
            Document doc = _documentList.First.Value;
            _documentList.RemoveFirst();
            return doc;
        }
    }

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%