定义：

数组：是一种线性的数据结构，用一组连续的内存空间来存储的具有相同数据类型的数据；
链表：跟数组一样也是也是一种线性的数据结构，链表的内存结构不是连续性，是将一组零散的内存块串联起来，从而进行数据存储的结构；链表中的每一个内存块被称为节点Node，节点除了存储数据外，还需要记录下一个节点的地址。（单链表、循环链表、双向链表）

1.png

时间复杂度：

数组：插入、删除的时间复杂度为O(n),因为需要保持数组内存空间的连续性，需要插入（删除）的数据往后（前）移动；查找的的时间复杂度为O(1),根据下标能直接找到数据；
链表：插入、删除的时间复杂度为O(1)；查找的的时间复杂度为O(n)：因为链表的存储空间是不连续性的（数据并非联系存储的），只能通过指针一个个的往下遍历

452e943788bdeea462d364389bd08a17.jpg

缺点：

数组：1）需要连续的内存空间；2）大小固定，如果存储空间不足，需要进行扩容就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非耗时的；
链表：对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片

    public class LinkedList<T>
    {
        public Node<T> Head { get; set; }

        public LinkedList()
        {
            this.Head = null;
        }


        /// <summary>
        /// 节点插入到最后
        /// </summary>
        /// <param name="item"></param>
        public void Insert(T item)
        {
            Node<T> operNode = new Node<T>(item);
            Node<T> current = new Node<T>();

            if (Head == null)
            {
                Head = operNode;
                return;
            }

            current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }

            current.Next = operNode;
        }

        /// <summary>
        /// 删除第i个节点
        /// </summary>
        /// <param name="i"></param>
        public void Delete(int i)
        {
            Node<T> temp = new Node<T>();
            Node<T> p = new Node<T>();

            if (i == 1)
            {
                Head = Head.Next;
                return;
            }

            temp = Head;

            int j = 1;
            while (temp.Next != null && j < i)
            {
                j++;
                p = temp;
                temp = temp.Next;
            }

            if (j == i)
            {
                p.Next = temp.Next;
            }
        }
    }

    public class Node<T>
    {
        public Node(T item)
        {
            this.Data = item;
            this.Next = null;
        }
        public Node()
        {
            this.Data = default(T);
            this.Next = null;
        }


        public T Data { get; set; }

        public Node<T> Next { set; get; }
    }