C ＃ custom bidirectional linked list

Realize a two-way linked list by yourself , Performance follow C# The self-contained ones are better

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;
using System.Text;
using System.Threading.Tasks;

namespace LKZ.DataStruct
{
    
    /// <summary>
    ///  Double linked list 
    /// </summary>
    [Serializable]
    public class LinkedList2<T> : ICollection<T>, ICollection, IReadOnlyCollection<T> , ISerializable, IDeserializationCallback, IEnumerable<T>, IEnumerable, IEnumerator, IEnumerator<T>
    {
    
        #region LinkedListNode  List nodes 
        /// <summary>
        ///  List nodes 
        /// </summary>
        public class LinkedListNode
        {
    
            /// <summary>
            ///  Last node 
            /// </summary>
            public LinkedListNode Pre {
     get; internal set; }

            /// <summary>
            ///  next 
            /// </summary>
            public LinkedListNode Next {
     get; internal set; }

            /// <summary>
            ///  Now the value is 
            /// </summary>
            public T Value {
     get; internal set; }

            internal LinkedListNode(T t)
            {
    
                Value = t;
            }

            internal LinkedListNode(T t, LinkedListNode pre, LinkedListNode next)
                : this(t)
            {
    
                this.Pre = pre;
                this.Next = next;
            }

            internal void Invalidate()
            {
    
                Value = default(T);
                Next = null;
                Pre = null;
            }
        } 
        #endregion

        #region  structure 
        public LinkedList2() {
     }

        /// <summary>
        ///  structure 
        /// </summary>
        /// <param name="ienumerable"> Values added to the linked list </param>
        public LinkedList2(IEnumerable<T> ienumerable)
        {
    
            foreach (T item in ienumerable)
            {
    
                this.AddLast(item);
            }
        }

        /// <summary>
        ///  Deserialization calls this 
        ///  Will pass two parameters 
        /// </summary>
        /// <param name="info"> The deserialized parameters are inside , Read Ali from the stream and store it in this class </param>
        /// <param name="context"></param>
        protected LinkedList2(SerializationInfo info, StreamingContext context)
        {
    
            siInfo = info;
        } 
        #endregion

        /// <summary>
        ///  How many 
        /// </summary>
        public int Count {
     get; private set; }

        public bool IsReadOnly => false;

        /// <summary>
        ///  I don't know how to use this 
        /// </summary>
        public object SyncRoot => throw new NotImplementedException();

        public bool IsSynchronized => false;

        /// <summary>
        ///  Head 
        /// </summary>
        public LinkedListNode Head {
     get; private set; }

        /// <summary>
        ///  The tail 
        /// </summary>
        public LinkedListNode Last {
     get; private set; }

        public T Current
        {
    
            get
            {
    
                T temp = positionNode.Value;
                positionNode = positionNode.Next;
                return temp;
            }
        }

        object IEnumerator.Current => Current;

        /// <summary>
        ///  For deserialization 
        ///  Used to store the deserialization of zero time 
        /// </summary>
        private SerializationInfo siInfo=null;

        /// <summary>
        ///  The current node position of the iterator 
        /// </summary>
        private LinkedListNode positionNode = null;

        /// <summary>
        ///  Add an element at the end 
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public LinkedListNode AddLast(T t)
        {
    
            Count++;
            if (Head == null)
            {
    
                return Last = Head = new LinkedListNode(t);
            }
            else
            {
    
                var newNode = new LinkedListNode(t, Last, null);
                Last.Next = newNode;
                return Last = newNode;
            }
        }


        /// <summary>
        ///  Add an element to the header 
        /// </summary>
        /// <param name="t"></param>
        /// <returns></returns>
        public LinkedListNode AddFirst(T t)
        {
    
            Count++;

            if (Head == null)
            {
    
                return Last = Head = new LinkedListNode(t);
            }
            else
            {
    
                var newNode = new LinkedListNode(t, null, Head);
                Head.Pre = newNode;
                return Head = newNode;
            }
        }

        /// <summary>
        ///  Add before this node 
        /// </summary>
        /// <param name="linedListNode"> Add an element before this node </param>
        /// <param name="t"> Value to add </param>
        public LinkedListNode AddBefore(LinkedListNode linedListNode, T t)
        {
    
            if (linedListNode == null)
                ThrowError("linedListNode It's empty ");

            if (linedListNode == Head)
                return this.AddFirst(t);
            else
            {
    
                var newNode = new LinkedListNode(t, linedListNode.Pre, linedListNode);
                linedListNode.Pre.Next = newNode;
                linedListNode.Pre = newNode;
                Count++;
                return newNode;
            }
            /* 1,5,3,16,4  For example, adding an element is ,50  Decide which element to add in front of  linedListNode  Add in front of this element , Determine whether this element is a header element   Instead of the header element, execute the following  else Code   For example, add in 16 In front of the element   Create a new element , Specify that this element is preceded by 16 In front of  3  And then 16 This element of   Then set the 3 The following element of is 50  Set up 16 The previous element is 50 That's it  */
        }

        /// <summary>
        ///  Add an element after this element 
        /// </summary>
        /// <param name="linedListNode"> Add an element before this node </param>
        /// <param name="t"> Value to add </param>
        /// <returns></returns>
        public LinkedListNode AddAfter(LinkedListNode linedListNode, T t)
        {
    
            if (linedListNode == null)
                ThrowError("linedListNode It's empty ");


            if (linedListNode == Last)
                return this.AddLast(t);
            else
            {
    
                var newNode = new LinkedListNode(t, linedListNode, linedListNode.Next);
                linedListNode.Next.Pre = newNode;
                linedListNode.Next = newNode;
                Count++;
                return newNode;
            }
            /* 1,5,3,16,4  For example, adding an element is ,50  Decide which element to add after  linedListNode  Add in front of this element , Judge whether this element is a tail element   Instead of the header element, execute the following  else Code   such as   Add in 16 After the element   Create a new element , Specify that this element is preceded by 16  And then 16 The last element of   Then set the 16 The following element of is 50  Set up 4 The previous element is 50 That's it  */
        }



        /// <summary>
        ///  Serialization calls this method 
        /// </summary>
        /// <param name="info"> Store the serialized data in this class </param>
        /// <param name="context"></param>
        void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
        {
    
            if (info == null)
            {
    
                throw new ArgumentNullException("info It's empty ");
            }

            info.AddValue(nameof(Count), Count);
            if (Count != 0)
            {
    
                T[] array = new T[Count];
                CopyTo(array, Count);
                info.AddValue("data", array, array.GetType());
            }
        }

        void ICollection<T>.Add(T item)
        {
    
            this.AddLast(item);
        }

        public void Clear()
        {
    
            LinkedListNode currentNode = Head;
            while (currentNode!=null)
            {
    
                var temp= currentNode;
                currentNode=currentNode.Next;
                temp.Invalidate();
            }
            Count = 0;
            Head = Last = null;
        }

        public bool Contains(T item)
        {
    
            return !object.ReferenceEquals(null, Find(item));
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
    
            if (array == null)
                this.ThrowError(" Array is empty ");
            else if (arrayIndex < 0 || arrayIndex > array.Length)
                this.ThrowError("arrayIndex illegal , Out of range ");
            else if (arrayIndex > Count)
                this.ThrowError("arrayIndex illegal , It exceeds the size in the linked list ");

            LinkedListNode currentNode = Head;
            for (int i = 0; i < arrayIndex; i++)
            {
    
                array[i] = currentNode.Value;
                currentNode = currentNode.Next;
            }
        }

        public bool Remove(T item)
        {
    
            LinkedListNode linkedListNode = Find(item);
            bool isNotNull = linkedListNode != null;
            if (isNotNull)
            {
    
                linkedListNode.Next.Pre = linkedListNode.Pre;
                linkedListNode.Pre.Next = linkedListNode.Next;
                Count--;
            }
            return isNotNull;
        }

        public IEnumerator<T> GetEnumerator()
        {
    
            Reset();
            return this;
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
    
            Reset();
            return this;
        }

        public void CopyTo(Array array, int index)
        {
    
            if (array == null)
                this.ThrowError(" Array is empty ");
            else if (!(array is T[]))
                this.ThrowError(" Array and generic types are inconsistent ");

            int length = array.Length - index;
            if (length > Count)
                length = Count;

            CopyTo(array as T[], length);
        }

        void IDeserializationCallback.OnDeserialization(object sender)
        {
    
            if (siInfo.GetInt32(nameof(Count)) != 0)
            {
    
                T[] array = (T[])siInfo.GetValue("data", typeof(T[]));
                for (int i = 0; i < array.Length; i++)
                {
    
                    AddLast(array[i]);
                }
            }
            siInfo = null;
        }

        public void Dispose()
        {
    
            Reset();
        }

        public bool MoveNext()
        {
    
            return positionNode != null;
        }

        public void Reset()
        {
    
            positionNode = Head;
        }

        /// <summary>
        ///  Throw an exception 
        /// </summary>
        /// <param name="message"></param>
        private void ThrowError(string message)
        {
    
            throw new ArgumentException(message);
        }

        private LinkedListNode Find(T item)
        {
    
            LinkedListNode currentLinkend = Head;
            while (currentLinkend != null)
            {
    
                if (!object.Equals(currentLinkend.Value, item))
                    currentLinkend = currentLinkend.Next;
                else
                    return currentLinkend;
            }
            return null;
        }
    }
}

• Have shortcomings

advantage

This solves the problem of inserting and deleting elements in dynamic arrays , Later data shift , High performance consumption
The performance of inserting and deleting elements in this linked list is better than that of dynamic array 10 times

shortcoming

The linked list is disordered , If you find an element in the linked list , This performance is quite poor , Because we need to search one by one

resolvent

Use binary lookup tree
Look forward to my next chapter ！

Pay attention to WeChat public number 【 Prodigal monologue 】 Get more ！