C#实现单链表(线性表)完整实例

为了更好的阐述“C#实现单链表(线性表)完整实例”这一主题，在下面的回答中我们将会涉及以下两个方面：

• 单链表的原理以及相关概念；
• C#语言实现单链表的完整攻略。

单链表的原理及概念

单链表是常用的一种链式存储结构，因为其结构形式极其简单，便于操作和改变长度，所以经常用作链表的头结点。简单的来说，单链表由若干个结点组成，每个结点包括一个存放元素的数据域（可以为空），和一个指向下一个元素的指针域（可为null）。

在单链表中，为了能够方便的使用链表，通常会对单链表进行封装，包括但不限于：该链表中数据元素个数、获取某个位置的元素、添加元素、删除元素等等。

C#语言实现单链表

下面我们通过一些示例来阐述如何使用C#语言实现一个单链表。

示例一：封装单链表

在单链表中，一般会定义一个节点Node来表示链表中每个数据的元素，一个单链表则需要封装一个类LinkedList。考虑到该链表的长度需要变化，则LinkedList应该拥有一个字段size来记录链表元素的数量。此外，还需要拥有以下方法：

• GetElement(int index)，根据索引（下标）获取链表中指定位置的元素；
• Add(T value)，向链表末端添加元素value；
• Insert(int index, T value)，向链表的指定位置插入元素value；
• Remove(int index)，删除链表中指定位置上的元素；
• IndexOf(T value)，查找元素在链表中的位置。

下面是封装好的C#代码，实现了上述需求：

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

public class LinkedList<T>
{
    public int Size { get; private set; }
    private Node<T> _head;

    public T GetElement(int index)
    {
        if (index < 0 || index >= Size)
        {
            throw new IndexOutOfRangeException();
        }
        Node<T> current = _head;
        for (int i = 0; i < index; i++)
        {
            current = current.Next;
        }
        return current.Data;
    }

    public void Add(T data)
    {
        Node<T> newNode = new Node<T>
        {
            Data = data
        };
        if (_head == null)
        {
            _head = newNode;
        }
        else
        {
            Node<T> current = _head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
        Size++;
    }

    public void Insert(int index, T data)
    {
        if (index < 0 || index > Size)
        {
            throw new IndexOutOfRangeException();
        }
        Node<T> newNode = new Node<T>
        {
            Data = data
        };
        if (index == 0)
        {
            newNode.Next = _head;
            _head = newNode;
        }
        else
        {
            Node<T> current = _head;
            for (int i = 0; i < index - 1; i++)
            {
                current = current.Next;
            }
            newNode.Next = current.Next;
            current.Next = newNode;
        }
        Size++;
    }

    public void Remove(int index)
    {
        if (index < 0 || index >= Size)
        {
            throw new IndexOutOfRangeException();
        }
        if (index == 0)
        {
            _head = _head.Next;
        }
        else
        {
            Node<T> current = _head;
            for (int i = 0; i < index - 1; i++)
            {
                current = current.Next;
            }
            current.Next = current.Next.Next;
        }
        Size--;
    }

    public int IndexOf(T data)
    {
        Node<T> current = _head;
        for (int i = 0; i < Size; i++)
        {
            if (current.Data.Equals(data))
            {
                return i;
            }
            current = current.Next;
        }
        return -1;
    }
}

示例二：使用单链表

在知道了如何封装单链表之后，就可以直接使用已经封装好的单链表了。下面是一些使用示例。

var linkedList = new LinkedList<int>();
linkedList.Add(1);
linkedList.Add(2);
int value = linkedList.GetElement(1); // value = 2
linkedList.Insert(1, -1);
int index = linkedList.IndexOf(1); // index = 0
linkedList.Remove(2);
int size = linkedList.Size; // size = 2

总之，本文提供了关于C#实现单链表的完整攻略，通过上面的介绍和示例，相信读者已经掌握了如何使用C#语言实现一个完备的单链表。