从零开始实现链表数据结构

从零开始实现链表数据结构

链表是计算机科学中一种重要的数据结构，广泛应用于各种编程场景。本文将从链表的基本概念出发，详细讲解链表的定义、分类，并通过实际代码演示链表的实现过程，包括初始化、插入、查找、更新、删除等操作。

一、链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据元素，指针域用于存储下一个节点的地址。

• 节点：链表的基本组成单位，包含数据域和指针域。
• 头指针：指向链表第一个节点的指针。
• 头节点：链表的第一个节点，数据域可以为空，主要用于简化链表操作。
• 首元节点：链表中第一个数据域不为空的节点。

二、链表的分类

链表主要可以分为以下几类：

1. 静态链表和动态链表：根据内存分配方式区分。
2. 单向链表、双向链表和循环链表：根据节点连接方式区分。

• 单链表：每个节点包含一个指向下一个节点的指针。
  

• 双向链表：每个节点包含两个指针，分别指向前后两个节点。
  

• 循环链表：链表首尾相连，形成闭环。可以是单向循环链表或双向循环链表。
  

三、链表的实现

下面将通过代码实现一个简单的单链表。我们将使用C#语言，通过手动管理内存来实现链表的基本操作。

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()：销毁链表。
    ]
}

2. 定义类

定义节点结构体：

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

定义链表实现类：

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

3. 初始化链表

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);
    _length++;
    return node;
}

4. 获取链表长度

public int Length
{
    get
    {
        return _length;
    }
}

5. 获取头节点

public MyselfLinkedListNode? HeadNode
{
    get
    {
        if (_head == IntPtr.Zero)
        {
            return null;
        }
        return GetNode(_head);
    }
}
private MyselfLinkedListNode GetNode(IntPtr pointer)
{
    return Marshal.PtrToStructure<MyselfLinkedListNode>(pointer);
}

6. 插入节点

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);
        _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. 查找节点

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. 更新节点

public void Update(MyselfLinkedListNode node, string value)
{
    var pointer = GetPointer(node);
    if (pointer != IntPtr.Zero)
    {
        node.Data = value;
        Marshal.StructureToPtr(node, pointer, false);
    }
}

9. 删除节点

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);
            _length--;
            break;
        }
        else
        {
            currentPointer = currentNode.Next;
            currentNode = GetNode(currentPointer);
        }
    }
}

10. 销毁链表

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

11. 释放内存

由于实现了IDisposable接口，需要在Dispose方法中调用上面的Destroy方法。

注：完整的测试代码和示例源码可以参考以下仓库：https://gitee.com/hugogoos/Planner