数据结构 - 链表

来源：网络更新时间：2024-10-12 09:31:03

今天我们将开始第二个数据类型-链表的学习，同样我们还是用最原始的方式，自己申请内存管理内存来实现一个链表。

01 、01、定义

什么是链表？链表在物理存储结构上表现为非顺序性和非连续性，因此链表的数据元素物理存储位置是随机的，动态分配的；而在逻辑结构上表现为线性结构的特点，即元素一个连着一个元素串起来像一条线。

节点：其中链表元素又叫节点，一个节点主要包含数据域和指针域，其中数据域主要存放数据元素，而指针域主要存放下一个节点存储位置地址。

头指针 ：一个表示链表第一个节点位置的普通指针，并且永远指向第一个节点位置，方便后面使用链表。

头节点 ：通常表示链表的第一个节点，并且节点内数据域为空，因此也叫空节点，其作用主要用于解决一些特殊问题，因此也可以省略。

首元节点 ：由于头节点数据域为空，因此链表的第一个数据域不为空的节点叫首元节点，只是一个名称，并没有什么实际意义。

02 、02、分类

链表有两种分类方法，其一可以分为静态链表和动态链表，其二可以分为单向链表、双向链表以及循环链表。

单链表只有一个方向，每个节点包含数据域和指向下一个节点的指针域。

双向链表有两个方向，即每个节点包含数据域以及同时指向上一个节点和下一个节点的指针域。

循环链表指链表首尾相连，即最后一个节点的指针域指向第一个节点。循环链表也分单向循环链表和双向循环链表，原理都一样。

03 、03、实现

下面我们一起使用最原始的方式，自己申请内存空间，自己维护，完成链表的实现。

1、ADT定义

我们首先来定义链表的ADT（单链表）。

ADT LinkedList{

数据对象：D 是一个非空的元素集合，D = {a1, a2, ..., an}，其中 ai 表示一个元素即节点，一个节点存储着数据和指向下一个节点的指针。

数据关系：D中的节点通过指针进行连接，每一个节点都包含一个指向下一个节点的指针。

基本操作：[

Init(n) ：初始化一个空链表，即声明一个头指针，如有必要也可以声明一个头节点。

Length：返回链表长度。

HeadNode：返回头节点。

Find(v)：返回数据域v对应的节点。

Update(n,v)：更新n节点的数据域。

InsertAfter(n,v)：在n节点后面添加数据域为v的新节点。

Remove(n)：移除n节点。

Destroy()：销毁链表。

]

}

定义好链表ADT，下面我们就可以开始自己实现一个数据域为string类型的链表。

2、定义类

首先我们需要定义节点，其中包含两个字段一个是存放数据、一个是存放指针,代码如下。

public struct MyselfLinkedListNode
{
    //数据域
    public string Data { get; set; }
    //指针域
    public IntPtr Next { get; set; }
}

然后再定义链表实现类MyselfLinkedList，用来实现链表的相关操作。

因为我们直接管理内存，所以需要一个维护内存的指针字段；

因为我们直接获取链表长度，所以需要一个存储链表长度字段；

因此我们的MyselfLinkedList类初步是这样的：

public sealed class MyselfLinkedList : IDisposable
{
    //申请内存起始位置指针
    private IntPtr _head;
    //链表长度
    private int _length;
}

3、初始化Init

初始化结构主要做几件事。

a.分配内存空间；

b.什么头指针；

c.创建头节点；

d.维护链表长度属性；

具体实现代码如下：

//初始化链表，声明头指针，并创建头节点
public MyselfLinkedListNode Init()
{
    //计算节点的大小
    var size = Marshal.SizeOf(typeof(MyselfLinkedListNode));
    //分配指定字节数的内存空间
    _head = Marshal.AllocHGlobal(size);
    //创建头节点
    var node = new MyselfLinkedListNode
    {
        Data = null,
        Next = IntPtr.Zero
    };
    //将节点实例写入分配的内存
    Marshal.StructureToPtr(node, _head, false);
    //链表长度加1
    _length++;
    //返回头节点
    return node;
}

4、获取链表长度 Length

这个比较简单直接把链表长度私有字段返回即可。

//链表长度
public int Length
{
    get
    {
        return _length;
    }
}

5、获取头节点 HeadNode

获取头节点主要是为了方便数据处理，可以通过头指针直接读取内存地址获取。具体代码如下：

//头节点
public MyselfLinkedListNode? HeadNode
{
    get
    {
        if (_head == IntPtr.Zero)
        {
            return null;
        }
        return GetNode(_head);
    }
}
//获取节点
private MyselfLinkedListNode GetNode(IntPtr pointer)
{
    // 从分配的内存读取实例
    return Marshal.PtrToStructure(pointer);
}

同样我们也可以定义一个尾节点属性，可以方便使用，原理都差不多，这里就不赘述了。

6、在指定节点后插入节点 InsertAfter

通过前面对链表结构的了解，要想再两个节点之间加入一个新节点，只需要把两者之间的线剪断，即前一个节点的指针域需要重新指向新节点，并且新节点的指针域要指向后一个节点，其他保持不变，如下图：

业务逻辑清楚了，我们再来梳理代码逻辑，要想实现这个功能我们大致需要一下几步：

a.获取指定节点的指针；

b.创建一个新的节点；

c.重新调整指定节点及新节点指针域；

d.把指定节点和新节点指针调整后数据更新到内存中；

e.更新链表长度属性；

具体实现如下：

//在指定节点后插入新节点
public MyselfLinkedListNode InsertAfter(MyselfLinkedListNode node, string value)
{
    //获指定取节点对应指针
    var pointer = GetPointer(node);
    //如果指针不为空才处理
    if (pointer != IntPtr.Zero)
    {
        //以新值创建一个节点
        var (newPointer, newNode) = CreateNode(value);
        //把新节点的下一个节点指针指向指定节点的下一个节点
        newNode.Next = node.Next;
        //把指定节点的下一个节点指针指向新节点
        node.Next = newPointer;
        //更新修改后的节点
        Marshal.StructureToPtr(newNode, newPointer, false);
        Marshal.StructureToPtr(node, pointer, false);
        //链表长度加1
        _length++;
        return newNode;
    }
    return default;
}
//获取节点对应指针
private IntPtr GetPointer(MyselfLinkedListNode node)
{
    //从头指针开始查找
    var currentPointer = _head;
    //如果当前指针为空则停止查找
    while (currentPointer != IntPtr.Zero)
    {
        //获取当前指针对应的节点
        var currentNode = GetNode(currentPointer);
        //如果当前节点数据域和指针域与要查找的节点相同则返回当前节点指针
        if (currentNode.Data == node.Data && currentNode.Next == node.Next)
        {
            return currentPointer;
        }
        //否则查找下一个节点
        currentPointer = currentNode.Next;
    }
    return IntPtr.Zero;
}
//创建节点
private (IntPtr Pointer, MyselfLinkedListNode Node) CreateNode(string value)
{
    //计算大小
    var size = Marshal.SizeOf(typeof(MyselfLinkedListNode));
    //分配指定字节数的内存空间
    var pointer = Marshal.AllocHGlobal(size);
    //创建实例并设置值
    var node = new MyselfLinkedListNode
    {
        Data = value,
        Next = IntPtr.Zero
    };
    //将实例写入分配的内存
    Marshal.StructureToPtr(node, pointer, false);
    //返回节点指针和节点
    return (pointer, node);
}

这里只实现了一个在指定节点后插入节点，我们还可以实现在指定节点前插入，在首元节点前插入，在尾节点后添加，都是可以的，感兴趣的可以自己实现试试。

7、根据数据域查找节点 Find

在链表中对查找是不友好的，因为查找一个值，需要从链表头一个一个往后查找，实现逻辑到不复杂，具体实现代码如下：

//根据数据查找节点
public MyselfLinkedListNode Find(string value)
{
    //从头指针开始查找
    var pointer = _head;
    //如果当前指针为空则停止查找
    while (pointer != IntPtr.Zero)
    {
        //获取当前指针对应的节点
        var node = GetNode(pointer);
        //如果当前节点数据域和要查找值相同则返回当前节点
        if (node.Data == value)
        {
            return node;
        }
        //否则查找下一个节点
        pointer = node.Next;
    }
    return default;
}

8、更新指定节点数据域 Update

这个方法逻辑也比较简单，只需要找到节点指针，然后把节点更新，最后把更新后的数据写入内存即可。

//更新节点数据
public void Update(MyselfLinkedListNode node, string value)
{
    //获取节点对应指针
    var pointer = GetPointer(node);
    //当指针不为空，则更新节点数据
    if (pointer != IntPtr.Zero)
    {
        //修改数据
        node.Data = value;
        //将数据写入分配的内存，完成数据更新
        Marshal.StructureToPtr(node, pointer, false);
    }
}

9、移除指定节点 Remove

如果要想移除一个节点，则需要把指定节点与前后节点的连接删除，然后把前后两个节点建立起连接，同时需要手动释放被删除节点内存。如下图。

具体代码实现如下：

//移除节点
public void Remove(MyselfLinkedListNode node)
{
    //从头指针开始查找
    var currentPointer = _head;
    //获取当前节点
    var currentNode = GetNode(_head);
    //查找节点对应的指针
    var pointer = GetPointer(node);
    while (true)
    {
        if (currentNode.Next == IntPtr.Zero)
        {
            //指针为空则返回
            return;
        }
        else if (currentNode.Next == pointer)
        {
            //把要删除节点的上一个节点对应的下一个节点指向要删除节点的下一个节点
            currentNode.Next = node.Next;
            //手动释放被删除节点对应的内存
            Marshal.FreeHGlobal(pointer);
            //更新要删除节点的上一个节点
            Marshal.StructureToPtr(currentNode, currentPointer, false);
            //链表长度减1
            _length--;
            break;
        }
        else
        {
            //查找下一个节点
            currentPointer = currentNode.Next;
            currentNode = GetNode(currentPointer);
        }
    }
}

10、销毁链表 Destroy

销毁链表主要是使用因为是我们自己手动管理内存，用完后要及时清理，放在内存泄漏等意外情况出现。代码也很简单，循环把每个节点内存释放即可，如下代码：

//销毁链表
public void Destroy()
{
    var pointer = _head;
    while (pointer != IntPtr.Zero)
    {
        var value = GetNode(pointer);
        Marshal.FreeHGlobal(pointer);
        _length--;
        pointer = value.Next;
    }
    _head = IntPtr.Zero;
}