CS4L10——LinkedList

本章代码关键字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//链表
LinkedList<>                    //链表类
linkedList<>.AddLast()            //在链表尾部添加元素
linkedList<>.AddFirst()            //在链表头部添加元素
linkedList<>.Find()                //获取指定值的节点
linkedList<>.AddAfter()            //在某个节点后添加节点
linkedList<>.AddBefore()        //在某个节点前添加节点
linkedList<>.RemoveFirst()        //移除头节点
linkedList<>.RemoveLast()        //移除尾节点
linkedList<>.Remove()            //移除指定值的节点
linkedList<>.Clear()            //清空链表
linkedList<>.First                //获取头节点
linkedList<>.Last                //获取尾节点
linkedList<>.Contains()            //检测值是否存在于链表
//链表节点
LinkedListNode<>                //链表节点类
linkedListNode<>.Value            //链表节点存储的值
linkedListNode<>.Next            //节点的下一个节点
linkedListNode<>.Previous        //节点的上一个节点

LinkedList<>

​LinkedList<>​ 是一个C#为我们封装好的类，它的本质是一个可变类型的泛型双向链表

使用 LinkedList<>​ 需要引用 System.Collections.Generic​ 这个命名空间

实例化一个 LinkedList<>​ 必须要指明它要装载什么类型的元素

1
2
3
4
5
6
7
8
9
10
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        LinkedList<int> linkedList = new LinkedList<int>();
        LinkedList<string> linkedList2 = new LinkedList<string>();
    }
}

链表对象 需要掌握两个类，一个是链表本身、一个是链表节点类 LinkedListNode​

增删查改

增

在链表尾部添加元素

1
2
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);

在链表头部添加元素

1
2
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddFirst(20);

在某一个节点后添加一个节点

要指定节点，则需要先得到一个节点

获取指定值的节点
1
LinkedListNode<int> node = linkedList.Find(20);
1
2
3
4
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddFirst(20);
LinkedListNode<int> node = linkedList.Find(20);
linkedList.AddAfter(node, 15);

在某一个节点前添加一个节点

要指定节点，则需要先得到一个节点

1
2
3
4
5
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
LinkedListNode<int> node = linkedList.Find(20);
linkedList.AddBefore(node, 11);

删

移除头节点

1
2
3
4
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
linkedList.RemoveFirst();

移除尾节点

1
2
3
4
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
linkedList.RemoveLast();

移除指定节点

无法通过位置直接移除，只能通过节点的值移除

1
2
3
4
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
linkedList.Remove(20);

清空

1
2
3
4
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
linkedList.Clear();

查

获取头节点

1
2
3
4
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
LinkedListNode<int> firstNode = linkedList.First;

获取尾节点

1
2
3
4
5
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
LinkedListNode<int> firstNode = linkedList.First;
LinkedListNode<int> lastNode = linkedList.Last;

获取指定值的节点

无法通过下标获取中间元素，只能遍历查找指定位置元素，当指定值不存在于链表里时，会返回 null​ (空)

1
2
3
4
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
LinkedListNode<int> node = linkedList.Find(20);

获取节点的值

1
2
3
4
5
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(10);
linkedList.AddFirst(20);
LinkedListNode<int> firstNode = linkedList.First;
Console.WriteLine(firstNode.Value);

输出：

1
20

判断是否存在

1
2
3
4
5
6
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(1);
if (linkedList.Contains(1))
{
    Console.WriteLine("链表中存在1");
}

输出

1
链表中存在1

‍

改

要先得再改，得到需要改的节点，再改变其中的值

1
2
3
4
5
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddFirst(20);
Console.WriteLine(linkedList.First.Value);
linkedList.First.Value = 10;
Console.WriteLine(linkedList.First.Value);

输出：

1
2
20
10

遍历

foreach 遍历

1
2
3
4
5
6
7
8
9
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(3);
linkedList.AddLast(4);
foreach (int value in linkedList)
{
    Console.WriteLine(value);
}

输出：

1
2
3
4
1
2
3
4

通过节点遍历

从头遍历到尾，需要获取下一个节点的属性：

1
2
3
4
5
6
7
8
9
10
11
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(3);
linkedList.AddLast(4);
LinkedListNode<int> nowNode = linkedList.First;
while (nowNode != null)
{
    Console.WriteLine(nowNode.Value);
    nowNode = nowNode.Next;
}

输出：

1
2
3
4
1
2
3
4

从尾到头：

1
2
3
4
5
6
7
8
9
10
11
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddLast(3);
linkedList.AddLast(4);
LinkedListNode<int> nowNode = linkedList.Last;
while (nowNode != null)
{
    Console.WriteLine(nowNode.Value);
    nowNode = nowNode.Previous;
}

输出：

1
2
3
4
4
3
2
1