C#数据结构之单链表(LinkList)实例详解

概述

单链表是一种简单的数据结构，它由一些节点组成，每个节点包含着一个数据元素和一个指向下一个节点的指针。它的特点是可以快速的插入和删除节点，但在查找元素时效率不高。本篇文章将详细讲解单链表的实现过程和相关细节。

实现步骤

定义节点类

首先需要定义一个单链表节点类，包含两个部分：数据和指向下一个节点的指针。代码如下：

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

    public Node(T data)
    {
        this.Data = data;
        this.Next = null;
    }
}

其中，泛型 <T> 表示该节点可以存储任意类型的数据。

定义链表类

链表类是一个包含节点的集合，每个节点都指向下一个节点。需要定义三个部分：链表的头节点、尾节点和链表的长度。代码如下：

public class LinkedList<T>
{
    private Node<T> head;
    private Node<T> tail;
    private int count;

    public LinkedList()
    {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }
}

实现节点的添加功能

链表的添加操作有两种情况：在头部添加和在尾部添加。代码如下：

public void AddFirst(T data)
{
    Node<T> newNode = new Node<T>(data);

    if (count == 0)
    {
        head = newNode;
        tail = newNode;
    }
    else
    {
        newNode.Next = head;
        head = newNode;
    }

    count++;
}

public void AddLast(T data)
{
    Node<T> newNode = new Node<T>(data);

    if (count == 0)
    {
        head = newNode;
        tail = newNode;
    }
    else
    {
        tail.Next = newNode;
        tail = newNode;
    }

    count++;
}

实现节点的删除功能

链表的删除操作也有两种情况：删除头节点和删除尾节点。代码如下：

public void RemoveFirst()
{
    if (count == 0)
    {
        return;
    }

    if (count == 1)
    {
        head = null;
        tail = null;
    }
    else
    {
        head = head.Next;
    }

    count--;
}

public void RemoveLast()
{
    if (count == 0)
    {
        return;
    }

    if (count == 1)
    {
        head = null;
        tail = null;
    }
    else
    {
        Node<T> current = head;
        while (current.Next != tail)
        {
            current = current.Next;
        }
        current.Next = null;
        tail = current;
    }

    count--;
}

实现链表的遍历功能

链表的遍历功能即按顺序访问整个链表并处理节点数据。代码如下：

public void Traverse()
{
    Node<T> current = head;

    while (current != null)
    {
        // 处理每个节点的数据
        Console.WriteLine(current.Data);
        current = current.Next;
    }
}

示例

示例1：从数组中构建链表

int[] arr = new int[] { 1, 3, 5, 7 };
LinkedList<int> list = new LinkedList<int>();

foreach (int num in arr)
{
    list.AddLast(num);
}

list.Traverse();

以上代码创建了一个整型数组，将其逐个添加到链表中，并通过 Traverse() 方法遍历链表并打印每个节点的数据。

输出结果为：

1
3
5
7

示例2：从文件中读取数据并构建链表

LinkedList<string> list = new LinkedList<string>();

string path = "data.txt";
string[] lines = File.ReadAllLines(path);

foreach (string line in lines)
{
    list.AddLast(line);
}

list.Traverse();

以上代码从文件 data.txt 中读取每一行数据，逐个添加到链表中，并通过 Traverse() 方法遍历链表并打印每个节点的数据。

假设 data.txt 文件中的内容为：

apple
banana
cherry

则输出结果为：

apple
banana
cherry

总结

本篇文章详细讲解了单链表的实现过程和相关细节，包括定义节点类、定义链表类、实现节点的添加和删除功能、实现链表的遍历功能。通过两个示例，展示了如何从数组或文件中构建链表，并遍历链表并处理每个节点的数据。