Microbubu的迷你实验室

单向链表

C# 数据结构与算法
字数统计: 667阅读时长: 2 min
2018/11/13 Share

前言

今天在网上闲逛的时候看到了一个网友提问的删除链表节点相关问题，于是随手写了点操作链表的代码，包括生成链表、删除节点以及遍历整个链表，温故而知新，在这里记录一下。

链表作为一个最基本的数据结构，在计算机系统中被广泛使用。很多数据结构都是从链表衍生而来，比如栈、队列等，所以深入理解链表非常重要。

节点定义

1
2
3
4
5
6
public class Node<T>
{
    public T Value { get; set; }

    internal Node<T> Next { get; set; }
}

单向链表结构定义

在链表结构中增加一个Count计数器，可以方便快速获取链表长度，但是在增加节点或者删除节点的时候须确保Count的正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class LinkList<T>
{
    //首节点
    private Node<T> firstNode;
    public Node<T> FirstNode { get => firstNode; }

    //节点总数
    private int count = 0;
    public int Count { get => count; }

    //当前节点标志位
    private Node<T> currentNode = null;
}

链表的操作方法

新增节点

使用一个标志位表示当前节点(currentNode)，可以很方便的实现将新节点插入到链表的末尾，插入完成之后更改标志位为新的末节点即可，所以要确保currentNode标志位总是指向末节点，这一点在删除链表节点的时候需要尤其注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void AppendNode(T value)
{
    var newNode = new Node<T>() { Value = value };
    if (firstNode == null)
    {
        firstNode = newNode;
        currentNode = firstNode;
    }
    else
    {
        currentNode.Next = newNode;
        currentNode = newNode;
    }
    count++;
}

删除符合条件的第一个节点

删除操作中一定要确保currentNode标志位指向末节点，不然在删除操作完成后再进行添加操作会出现问题，而要改变currentNode标志位的情况只有一种，那就是删除的是链表的末节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public bool RemoveFirst(T value)
{
    var node = firstNode;
    Node<T> previousNode = null;
    while(node != null)
    {
        if(!node.Value.Equals(value))
        {
            previousNode = node;
            node = node.Next;
            continue;
        }
        if (node.Next == null)          //删除的是末节点，需要更改当前节点标志位
            currentNode = previousNode;
        if (previousNode == null)       //删除的是首节点
        {
            var oldFirst = firstNode;
            oldFirst = null;
            firstNode = firstNode.Next;
        }
        else
        {
            previousNode.Next = node.Next;
            node = null;
        }
        count--;
        return true;
    }
    return false;
}

遍历获取所有节点

1
2
3
4
5
6
7
8
9
10
11
public List<T> GetAllNodeValues()
{
    var node = firstNode;
    var resList = new List<T>();
    while (node != null)
    {
        resList.Add(node.Value);
        node = node.Next;
    }
    return resList;
}

测试

1
2
3
4
5
6
7
var links = new LinkList<int>();
for (int i = 0; i < 10; i++)
    links.AppendNode(i);
links.RemoveFirst(9);
links.AppendNode(10);
links.GetAllNodeValues().ForEach(v => Console.WriteLine(v));
Console.ReadKey();

结果：

1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
10

原文作者：Microbubu Groner

原文链接：https://microbubu.github.io/2018/11/13/单向链表/

发表日期：November 13th 2018, 7:39:06 pm

更新日期：November 13th 2018, 7:45:46 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 前言
  2. 2. 节点定义
  3. 3. 单向链表结构定义
  4. 4. 链表的操作方法
    1. 4.1. 新增节点
    2. 4.2. 删除符合条件的第一个节点
    3. 4.3. 遍历获取所有节点
    4. 4.4. 测试
Total : 11
2019
2018
PLC Markdown C# 数据结构与算法 OneDrive 图床 .NetCore WebApi PetaPoco 面试题 Python Map Reduce Kotlin 集合 Linux