[collection] [list LinkedList<T>]

LinkedList<T>

• Bidirectional linked lists. You can traverse the list forward by moving to the next element. By moving to the previous element, you can traverse the entire list in reverse
• Insert elements, very efficient. You only need to modify Next of the Previous element and Previous of the Next element.By contrast.List<T>To insert an element, you need to move all the following elements.
• It is inefficient to access the elements in the middle of the list. One by one, either from the beginning or the end.
• Elements forLinkedListNode<T>

LinkedListNode<T>

The sample

• When inserting a Document dynamically, you need to keep order
• This kind ofOrder is:
  • Priority is high
  • With the same Priority, the first to be inserted takes precedence

    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; }}Copy the code

Output:

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
Copy the code

Implementation:

• List<LinkedListNode<Document>> _priorityNodesFor storage,On each Priority.It’s already inserted.The latestAnd the Document.

    public class PriorityDocumentManager
    {
        private readonly LinkedList<Document> _documentList;

        / / 0.9 priorities
        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();
            returndoc; }}Copy the code