线性表的定义：零个或多个数据元素的有限序列

线性表元素的个数n(n>=0)定义为**线性表的长度，**当n=0时，称为空表

线性表的中的元素的相邻的前一个元素称为直接前驱元素，后一个元素称为直接后继元素

线性表的顺序存储结构

定义：线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

线性表长度：线性表中数据元素的个数
数组长度：存放线性表的存储空间的长度

1. 获得线性表的元素

通过数组的下标直接获得

  int[] array = new int[] { 1,2,3,4,5 };
  Console.WriteLine(array[1]);
  Console.ReadLine();

更改元素，直接通过数组下标直接修改就行了

  int[] array = new int[] { 1,2,3,4,5 };
  array[1] = 3;
  Console.WriteLine(array[1]);
  Console.ReadLine();

2. 顺序存储结构的插入

插入元素有三种方式
尾部插入
对于顺序表来说，如果插入元素在数组尾部，那么传入的下标参数index等于size。比如说：一个只有5个元素的顺序表，在尾部插入就是相当于添加一个下标等于原来顺序表的size的元素

这里的size为线性表中实际拥有的元素个数

如果插入元素在数组的中间或者头部，那么index一定会小于size

中间插入

  class SeqList
    {
        private int[] array;
        private int size;
        public SeqList(int MaxN)
        {
            array = new int[MaxN];
            size = MaxN;
        }
        public void insert(int index, int element)
        {
            if (index < 0 || index > size)
            {
                throw new IndexOutOfRangeException("超出数组实际元素范围！");
            }
            for (int i = size - 1; i <= index; i--)
            {
                array[i + 1] = array[i];
                
            }
            array[index] = element;
            size++;
        }
        public void print()
        {
            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine(array[i]);
            }
        }
         
      
            
    }
    class Program
    {

        static void Main(string[] args)
        {
            SeqList seqList = new SeqList(10);
            seqList.insert(0, 1);
            seqList.insert(1, 2);
            seqList.insert(2, 3);
            seqList.insert(3, 4);
            seqList.insert(4, 5);
            seqList.print();
            Console.ReadLine();
        }
    }

如果传入的下标参数index大于size或小于0，则认为是非法输入，会直接抛出异常。

超范围插入
超范围插入就是在已经装满元素的线性表之中，再插入一个新元素。
这里就要涉及扩容
扩容的方法

       public void resize()
        {
            int[] arrayNew = new int[array.Length * 2];
            System.Array.Copy(array, 0, arrayNew, 0, array.Length);
            array = arrayNew;
        }

 if (size >= array.Length)
            {
                resize();
            }

扩容的本质：创建一个新数组，然后将旧数组中的元素复制到新的数组当中

一般情况之下，是不会使用扩容的。遇到数组满的情况下，直接判断为false。

插入算法的本质
1、传入一个下标和元素
2、从线性表的后面向前遍历
3、以传入的下标为极限进行限制
4、然后以相邻的大的数取代前一个数，以完成空出插入位置的目的
5、最后将元素赋值给这个空位置

3. 顺序存储结构的删除

  public void delete(int index)
        {
            if (index < 0 || index >= size)
            {
                throw new IndexOutOfRangeException("超出数组实际元素范围");
            }
           
            for (int i = index; i < size - 1; i++)
            {
                array[i] = array[i + 1];
            }
            size--;
         
        }

删除的本质就是传入下标，从该下标遍历完数组，将后一个元素覆盖前一个元素，直到null赋值给最后一个元素

顺序表的优劣
对于元素的查找，顺序表的时间复杂度为O(1)
对于元素的删除与插入，顺序表的时间复杂度为O(n)

线性表链式存储结构

定义：对于数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。
将存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素的存储映像，称为结点(Node)。

n个结点链结成一个链表，即为线性表的链式存储结构，叫做单链表。

特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的

C#中顺序表为List<>,链表为LiskedList<>
在C#当中标准库中标的链表是双向带环、首尾相接的链表

链表的分类
C语言当中链表分为：单链表、静态链表、循环链表、双向链表。
链表分类的标准：
1、按结点方向：单链表，双向链表
2、按照是否循环：普通链表、循环链表
3、按照是否带头结点
4、按照头结点在链表表首：头结点在链表表首，头结点在链表表尾。

链表的使用
在这里C语言当中，使用结构和指针来描述链表。而C#使用类和引用来描述链表
对于C#来说，链表直接可以调用类库当中的。而C语言没有相应的类库，只能自己手撸。

链表的实例化与调用方法

  LinkedList<int> ll = new LinkedList<int>();//实例化一个链表，这个链表是C#类库中自带的，是双向链表
            LinkedListNode<int> node0= ll.AddFirst(1);//添加链表的头结点,LinkedListNode<int>是链表结点的类型
            LinkedListNode<int> node1 = ll.AddAfter(node0, 1);//在node0的后面添加一个结点

            LinkedListNode<int> node2 = ll.AddLast(4);//添加链表的尾结点

            LinkedListNode<int> node4 = ll.AddLast(4);//添加链表的尾结点

            LinkedListNode<int> node3 = ll.AddLast(2);//添加node4的前一个结点
            ll.Remove(node3);//删除node3结点

链表的遍历

 foreach (int nodeData in ll)//遍历链表
            {
                Console.WriteLine(nodeData);
            }

  for (LinkedListNode<int> node = ll.First; node != null; node = node.Next)
            {
                Console.WriteLine(node.Value);
            }

C#直接调用链表很方便，但是在大多数的情况之下，需要自己写出链表

手撸版链表的定义

  class Node
    {
        public string data;//数据域
        public Node next;//指针域
    }
    class Program
    {
        static void Main(string[] args)
        {
            Node n0 = new Node();//实例一个结点
            n0.data = "a";//给结点的数据赋值

            Node n1 = new Node();
            n1.data = "b";

            Node n2 = new Node();
            n2.data = "c";

            n0.next = n1;//将n0指针指向n1
            n1.next = n2;//将n1指针指向n2
            Node head = n0;//head为头结点
            Console.WriteLine(head.next.next.data);//这是指向n2

            for (Node node = head; node != null; node = node.next)
            {
                Console.WriteLine(node.data);
            }
            Console.ReadLine();
        }

一个链表只有一个头结点的引用(head)
链表的使用步骤
1、新建结点
2、将他们串起来

链表遍历的原理：生成一个动态指针p，在链表中结点不为空，一直向后遍历。

我们无法给链表每个元素起一个变量名，所以设置一个头结点，该结点永远指向链表首元素，这样的链表才有意义。

链表的插入和删除

链表的插入和删除在进行时需要进行查找元素的过程，因此时间复杂度为O(n),但是如果只考虑到插入与删除操作，时间复杂度都是O(1)。

链表的插入方法
链表的创建操作，实际上就是往链表里面插入新的链表结点
插入操作可以分为以下几种情况
1、插入位置为0(不管头结点是否为空)
2、插入位置在链表的中部或末尾
3、插入位置无效(<0，或者在末尾值后)：静止操作，返回false
头插法

 if (index == 0)//头插法
            {
                insertedNode.next = head;
                head = insertedNode;
            }

尾插法

if (index == size)//尾插法
            {
                last.next = insertedNode;
                last = insertedNode;
            }

中间插入

 int cnt = 0;
                for (Node p = head; p != null; p = p.next)
                {
                    if (cnt == index - 1)
                    {
                        insertedNode.next = p.next;
                        p.next = insertedNode;
                        return;
                    }
                }

链表的删除

   if (index == 0)//删除头结点
            {
                head = head.next;
            }

在这里插入代码片

  int cnt = 0;//删除中间
                for (Node p = head; p != null; p = p.next)
                {
                    if (cnt == index-1)
                    {
                        p.next = p.next.next;
                        return;
                    }
                }
                cnt++;

  int cnt = 0;
                for (Node p = head; p != null; p = p.next)
                {
                    if (cnt ==index-1 )
                    {
                        p.next = null;
                       
                        return;
                    }
                    cnt++;

顺序表与链表的比较

随机访问：顺序表可以直接定位一条语句内完成
链表顺序访问下一个元素

插入、删除：顺序表需要移动大量元素，且移动次数与元素个数，元素插入删除的位置关系都较大
链表在固定的常数时间内可以完成

内存使用：顺序表固定大小的一块连接内存块，如果需要扩容则需要拷贝大量元素
链表容易造成内存碎片

头指针与头结点的异同
头指针：
1、头指针是指链表指向第一个节点的指针，若链表有头·节点，则是指向头结点的指针
2、头指针具有标识作业，所以常用头指针冠以链表的名字
3、无论链表是否为空，头指针均不为空。头指针是链表的必要元素

头结点
1、头结点是为了操作的统一和方便设立的，放在第一元素的结点之前，其数据域一般无意义
2、有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
3、头结点不一定是链表必须要素