静态数组 Static Array

1. 优点：
   通过索引就可以直接访问任意元素。

2. 缺点：
   初始化时，就要知道元素数量。估大了空间浪费，估小了，空间不够用。

3. 解决方案：
   动态数组 Dynamic Array，能自动调节空间大小，但依然不能充分利用全部空间。

4. 进一步的解决方案：
   链表 Lined List，能充分利用空间，并实现灵活的动态内存管理。
   
   

链表 Lined List:

1. 链表由一个个节点构成
2. 每一个节点存储了两个信息，即： 实际存储的元素，和，下一个节点的引用（指针），用于将两个节点进行挂接
3. 将一个又一个节点，进行链接，就形成了链表。

4. 链表中，只能通过前一个节点，找到后一个节点。 如：要找 2节点 的值，必须要先找到 1节点，因为 1节点 包含了 2节点 的引用。 要找 1节点 的值，必须要先找到 0节点，因为 0节点 包含了 1节点 的引用。

5. 为了找到 0节点，必须要记录链表的 头节点的引用 head。

6. 节点的末尾，没有其他的节点，就指向 null。 0 --> 1 --> 2 --> 3 --> 4 --> null

链表的缺点：

在数组或列表中，数据是连续存储的，所以通过索引访问元素是非常快的（时间复杂度为 O(1)），因为可以直接计算出元素的存储位置。

链表（Linked List）本质上是一种线性数据结构，由一系列节点组成，其中每个节点包含数据本身和一个指向下一个节点的引用。

在链表中，数据是分散存储的，每个元素（节点）只包含其后继节点的引用。因此，为了通过索引找到一个特定的元素，你需要从链表的头部开始，沿着节点的链接一直遍历到达所需的索引位置。这意味着时间复杂度为 O(n)，其中 n 是链表的长度，因为最坏的情况下你可能需要遍历整个链表。

以下是在链表中通过索引查找元素的基本步骤：

1. 从链表的头节点开始。
2. 遍历链表，同时维护一个计数器来跟踪当前节点的索引。
3. 当计数器与所需的索引匹配时，返回当前节点。
4. 这种索引访问方式在链表中是不高效的，尤其是当链表很长或需要频繁访问不同索引时。这也是为什么在需要频繁索引访问的场景中，通常会推荐使用数组或动态数组（如 ArrayList 或 List）而不是链表。
5. 链表的优势在于节点的插入和删除操作（特别是在链表的开头或中间），在这些操作中，它可以提供比数组更好的性能。因为数组在进行这类操作时，需要移动整个数组。而链表只需要遍历到相应的节点，重新挂接就可以了。

案例：封装一个节点

    private class Node
    {
        public E e;         // 节点存储的元素
        public Node next;   // 下一个节点的引用（指针）
    } 

    private Node head；     // 链表的头节点的引用

案例：创建一个私有内部类 Node，作为链表的一部分

// 创建一个 私有内部类 Node，作为链表的节点。
// 一个链表节点包含两个因素：数据元素 E，和 对下一个节点的引用
// private class 里定义的 E 和 Node 是 public 的，因为需要在 private class 以外被调用。
private class Node
{
    public E e;         // 节点包含的元素
    public Node next;   // 下一个节点的引用

    // 两种 链表节点：
    // 1）非末尾节点：包括对下一个节点的引用 this.next = next;
    public Node(E e, Node next)
    {
        this.e = e;
        this.next = next;
    }

    // 2）末尾节点：只包含元素 e 而没有指向下一个节点的引用（即 next 是 null）
    public Node(E e)
    {
        this.e = e;
        this.next = null;
    }

    // ToString() 打印输出
    public override string ToString()
    {
        return e.ToString();
    }
}

C# 提供了 链表类

1. LinkedList<>，是一个双向链表类。
2. LinkedListNode<>, 双向链表的节点类

双向链表 不常用。常用的是 单向链表。

案例：创建一个 链表 MyLinkedList，实现 CRUD

internal class MyLinkedList<E>
{
    // 创建一个 私有内部类 Node，作为链表的节点。
    // 一个链表节点包含两个因素：数据元素 E，和 对下一个节点的引用
    // private class 里定义的 E 和 Node 是 public 的，因为需要在 private class 以外被调用。
    private class Node
    {
        public E e;         // 节点包含的元素
        public Node next;   // 下一个节点的引用

        // 两种 链表节点：
        // 1）非末尾节点：包括对下一个节点的引用 this.next = next;
        public Node(E e, Node next)
        {
            this.e = e;
            this.next = next;
        }

        // 2）末尾节点：只包含元素 e 而没有指向下一个节点的引用（即 next 是 null）
        public Node(E e)
        {
            this.e = e;
            this.next = null;
        }

        // ToString() 打印输出
        public override string ToString()
        {
            return e.ToString();
        }
    }

    // 记录 链表的 头节点
    private Node head;

    // 链表中存储的 元素数量
    private int N;

    // 初始化构造函数
    public MyLinkedList()
    {
        head = null;
        N = 0;
    }

    // 判断链表是否为 空
    public bool IsEmpty
    {
        get { return N == 0; }
    }

    // ToString() 打印输出
    public override string ToString()
    {
        StringBuilder res = new StringBuilder();
        Node current = head;
        while (current != null)
        { 
            res.Append(current + " -> " );
            current = current.next;
        }
        res.Append("Null");

        return res.ToString();
    }


    // 添加：
    public void Add(int index, E e)
    {
        if(index<0 || index>N)
            throw new IndexOutOfRangeException("非法索引");

        // 1) 往链表的头部添加元素

        if (index == 0)
        {
            /*
            Node node = new Node(e);
            node.next = head;
            head = node;*/

            // 优雅的写法
            head = new Node(e, head);
        }

        // 2）往链表的中部 或 尾部 添加元素
        else
        {
            // 插入数值到特定节点 index 时，需要先找到 它的前一个节点 preIndex，从头部开始找
            Node preIndex = head;

            // 找到 index 的前一个节点， index-1
            for(int i = 0; i < index-1; i++)
                // 从头部开始查找，依次往后移动指针，直到找到 index 的前一个节点为止
                preIndex = preIndex.next;

            /*
            // 为 数值 e 创建一个新的节点 node
            Node node = new Node(e);

            // 将 node 和 preIndex 挂接
            node.next = preIndex.next;
            preIndex.next = node;*/

            // 优雅的写法
            preIndex.next = new Node(e, preIndex.next);
        }

        N++;
    }

    public void AddFirst(E e)
    {
        Add(0, e);
    }

    public void AddLast(E e)
    {
        Add(N, e);
    }

    // 查找
    public E Get(int index)
    {
        if (index < 0 || index >= N)
            throw new IndexOutOfRangeException("非法索引");

        Node current = head;
        for (int i = 0;i < index;i++)
            current = current.next;

        return current.e;
    }

    public E GetFirst()
    {
        return Get(0);
    }

    public E GetLast()
    {
        return Get(N-1);
    }

    // 修改
    public void Set(int index, E newE)
    {
        if (index < 0 || index >= N)
            throw new IndexOutOfRangeException("非法索引");

        Node current = head;
        for (int i = 0; i < index; i++)
            current = current.next;

        current.e = newE;
    }

    // 查询
    public bool Contains(E e)
    {
        Node current = head;
        while(current != null)
        {
            if(current.e.Equals(e))
                return true;

            current = current.next;
        }

        return false;
    }

    // 删除
    public E RemoveAt(int index)
    {
        if (index < 0 || index >= N)
            throw new IndexOutOfRangeException("非法索引");

        if(index == 0)
        {
            Node delNode = head;
            head = head.next;
            N--;
            return delNode.e;
        }
        else
        {
            Node preIndex = head;
            for(int i = 0; i< index-1; i++)
                preIndex = preIndex.next;

            Node delNode = preIndex.next;
            preIndex.next = delNode.next;
            N--;
            return delNode.e;
        }
    }

    public E RemoveFirst()
    {
        return RemoveAt(0);
    }

    public E RemoveLast()
    {
        return RemoveAt(N-1);
    }

    public void Remove(E e)
    {
        if (head == null)
            return;

        if (head.e.Equals(e))
        {
            head = head.next;
            N--;
        }

        else
        {
            Node current = head;
            Node preIndex = null;

            while(current != null)
            {
                if (current.e.Equals(e))
                    break;

                preIndex = current;
                current = current.next;
            }

            if (current != null)
            {
                preIndex.next = preIndex.next.next;
                N--;
            }
        }
    }
}

测试执行结果

MyLinkedList<int> linkedList = new MyLinkedList<int>();
for (int i = 0;i<5; i++)
{
    linkedList.AddFirst(i);
    Console.WriteLine(linkedList);  // 4 -> 3 -> 2 -> 1 -> 0 -> Null
}

Console.WriteLine();

linkedList.AddLast(88);
Console.WriteLine(linkedList);   // 4 -> 3 -> 2 -> 1 -> 0 -> 88 -> Null
Console.WriteLine();

linkedList.Add(2, 999);
Console.WriteLine(linkedList);   // 4 -> 3 -> 999 -> 2 -> 1 -> 0 -> 88 -> Null
Console.WriteLine();

linkedList.Set(2, 1000);
Console.WriteLine(linkedList);   // 4 -> 3 -> 1000 -> 2 -> 1 -> 0 -> 88 -> Null
Console.WriteLine();

Console.WriteLine(linkedList.Get(2));    // 1000
Console.WriteLine();

Console.WriteLine(linkedList.Contains(100));    // False
Console.WriteLine(linkedList.Contains(1000));   // True
Console.WriteLine();

linkedList.RemoveAt(2);
Console.WriteLine(linkedList);   // 4 -> 3 -> 2 -> 1 -> 0 -> 88 -> Null

linkedList.RemoveFirst();
Console.WriteLine(linkedList);   // 3 -> 2 -> 1 -> 0 -> 88 -> Null

linkedList.RemoveLast();
Console.WriteLine(linkedList);   // 3 -> 2 -> 1 -> 0 -> Null

linkedList.Remove(0);
Console.WriteLine(linkedList);   // 3 -> 2 -> 1 -> Null

Console.Read();