顺序存储和链式存储

常用的顺序存储结构

1. 数组（Array）

数组是最基本的顺序存储结构，用于存储固定数量的同类型元素。

int[] numbers = new int[5];
numbers[0] = 1;
numbers[1] = 2;

优点：

• 通过索引可以快速访问元素，时间复杂度为 O(1)。

• 内存利用率高，数据连续存储。

缺点：

• 插入和删除操作效率低，时间复杂度为 O(n)。

• 数组大小固定，无法动态调整。

2. 动态数组（Dynamic Array）

动态数组是数组的扩展版本，可以根据需要动态调整大小。C# 中的 List<T> 就是一个常用的动态数组。

List<int> numbers = new List<int>();
numbers.Add(1);
numbers.Add(2);

优点：

• 支持动态调整大小。

• 提供了丰富的方法，操作方便。

缺点：

• 在扩展数组时可能会有性能开销。

• 插入和删除操作效率低，时间复杂度为 O(n)。

3. 字符串（String）

字符串本质上是一个字符数组，用于存储和操作文本。

string text = "Hello, World!";
char firstChar = text[0];

优点：

• 提供了丰富的字符串操作方法。

• 可以通过索引快速访问字符。

缺点：

• 不可变，一旦创建就不能修改。

• 对于大量的字符串操作，可能会导致性能问题。

常用的链式存储结构

1. 单链表（Singly Linked List）

单链表是链表的一种，每个节点包含数据和指向下一个节点的指针。

public class Node
{
    public int Data;
    public Node Next;

    public Node(int data)
    {
        Data = data;
        Next = null;
    }
}

public class SinglyLinkedList
{
    public Node Head;

    public void Add(int data)
    {
        Node newNode = new Node(data);
        if (Head == null)
        {
            Head = newNode;
        }
        else
        {
            Node current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }
}

优点：

• 插入和删除操作效率高，时间复杂度为 O(1)。

• 内存利用率高，不需要连续的内存空间。

缺点：

• 访问效率低，时间复杂度为 O(n)。

• 需要额外的内存来存储指针。

2. 双链表（Doubly Linked List）

双链表是一种链表，每个节点包含数据、指向下一个节点和前一个节点的指针。

public class DoublyNode
{
    public int Data;
    public DoublyNode Next;
    public DoublyNode Prev;

    public DoublyNode(int data)
    {
        Data = data;
        Next = null;
        Prev = null;
    }
}

public class DoublyLinkedList
{
    public DoublyNode Head;

    public void Add(int data)
    {
        DoublyNode newNode = new DoublyNode(data);
        if (Head == null)
        {
            Head = newNode;
        }
        else
        {
            DoublyNode current = Head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
            newNode.Prev = current;
        }
    }
}

优点：

• 支持双向遍历。

• 插入和删除操作效率高，时间复杂度为 O(1)。

缺点：

• 访问效率低，时间复杂度为 O(n)。

• 需要更多的内存来存储前后指针。

3. 循环链表（Circular Linked List）

循环链表是一种链表，最后一个节点指向第一个节点，形成一个环状结构。

public class CircularNode
{
    public int Data;
    public CircularNode Next;

    public CircularNode(int data)
    {
        Data = data;
        Next = null;
    }
}

public class CircularLinkedList
{
    public CircularNode Head;

    public void Add(int data)
    {
        CircularNode newNode = new CircularNode(data);
        if (Head == null)
        {
            Head = newNode;
            Head.Next = Head;
        }
        else
        {
            CircularNode current = Head;
            while (current.Next != Head)
            {
                current = current.Next;
            }
            current.Next = newNode;
            newNode.Next = Head;
        }
    }
}

优点：

• 支持循环遍历。

• 插入和删除操作效率高，时间复杂度为 O(1)。

缺点：

• 访问效率低，时间复杂度为 O(n)。

• 需要额外的内存来存储指针。

4. 跳表（Skip List）

跳表是一种链表，每个节点除了指向下一个节点外，还包含多个层级的指针，用于跳跃访问，提高查找效率。

csharp

Copy

// 跳表的实现较为复杂，这里简单介绍其概念
public class SkipListNode
{
    public int Value;
    public SkipListNode[] Forward;

    public SkipListNode(int level, int value)
    {
        Forward = new SkipListNode[level + 1];
        Value = value;
    }
}

public class SkipList
{
    private readonly int _maxLevel;
    private readonly SkipListNode _header;

    public SkipList(int maxLevel)
    {
        _maxLevel = maxLevel;
        _header = new SkipListNode(maxLevel, 0);
    }

    // 其他方法如插入、删除、查找等略
}

优点：

• 提供了更快的查找效率，平均时间复杂度为 O(log n)。

• 插入和删除操作也比较高效。

缺点：

• 实现较为复杂。

• 需要额外的内存来存储多层级指针。