【转载】每天5分钟用C#学习数据结构（3）单链表 Part 1

2021-11-09 21:04:13

在上一篇中，我们学习了线性表最基础的表现形式-顺序表，但是其存在一定缺点：必须占用一整块事先分配好的存储空间，在插入和删除操作上需要移动大量元素（即操作不方便），于是不受固定存储空间限制并且可以进行比较快捷地插入和删除操作的链表横空出世，所以我们就来复习一下链表，这一篇主要会集中在单链表。

1. 认识单链表

单链表的节点结构

在链表中，每个节点由两部分组成：数据域和指针域。

单链表的总体结构

链表就是由N个节点链接而成的线性表，如果其中每个节点只包含一个指针域那么就称为单链表，如果含有两个指针域那么就称为双链表。

PS：在线性表的链式存储结构中，为了便于插入和删除操作的实现，每个链表都带有一个头指针（或尾指针），通过头指针可以唯一标识该链表。从头指针所指向的节点出发，沿着节点的链可以访问到每个节点。

2. 单链表的实现

多说无益，现在我们直接动手用C#来实现一个单链表吧！

节点定义

public class Node<T>
{
    // 数据域
    public T Item { get; set; }
    // 指针域
    public Node<T> Next { get; set; }
    public Node() {}
    public Node(T item)
    {
        this.Item = item;
    }
}

此处定义Node类为单链表的节点，其中包括了一个数据域Item与一个指针域Next（指向后继节点的位置）。

节点的新增

① 默认在尾节点后插入新节点

public void Add(T value)
{
    Node<T> newNode = new Node<T>(value);
    if (this.head == null)
    {
        // 如果链表当前为空则置为头结点
        this.head = newNode;
    }
    else
    {
        Node<T> prevNode = this.GetNodeByIndex(this.count - 1);
        prevNode.Next = newNode;
    }

    this.count++;
}

首先判断头结点是否为空，其次依次遍历各节点找到尾节点的前驱节点，然后更改前驱节点的Next指针指向新节点即可。

② 指定在某个节点后插入新节点

public void Insert(int index, T value)
{
    Node<T> tempNode = null;
    if (index < 0 || index > this.count)
    {
        throw new ArgumentOutOfRangeException("index", "索引超出范围");
    }
    else if (index == 0)
    {
        if (this.head == null)
        {
            tempNode = new Node<T>(value);
            this.head = tempNode;
        }
        else
        {
            tempNode = new Node<T>(value);
            tempNode.Next = this.head;
            this.head = tempNode;
        }
    }
    else
    {
        Node<T> prevNode = GetNodeByIndex(index - 1);
        tempNode = new Node<T>(value);
        tempNode.Next = prevNode.Next;
        prevNode.Next = tempNode;
    }

    this.count++;
}

这里需要判断是否是在第一个节点进行插入，如果是则再次判断头结点是否为空。

3. 小结

本文介绍了另一种线性表：单链表，学习了单链表的基础知识及如何定义节点及如何通过两种方式来新增单链表的节点。下一篇我们会学习如何移除节点以及做一个完整的示例来演示单链表的操作。

[转载：每天5分钟用C#学习数据结构（3）单链表 Part 1](Edison Zhou)

码农公寓