简介

链表（LinkedList）是一种物理存储结构上非连续的线性表结构，数据元素的逻辑顺序通过链表中的指针链接次序来实现。实际上，链表就是线性表的链式存储结构。链表是由一系列结点组成，链表中每一个数据元素表示一个节点，节点可以在运行时动态生成。

链表中每一个节点包括两部分：一个是存储数据元素的数据域data，另一个是存储下一个节点的指针域next。指针是一个变量，存放值的内存地址，而不是值本身。链表分为单向链表（单链表）、双向链表（双链表）和循环链表。最简单的是单链表，其结构示意图如下：

上图为带头结点的单链表，头结点的指针域为head头指针。链表中的头结点通常不包含数据域，只有指针域。如果不带头结点，head头指针就直接指向第一个节点p1。不管有没有头结点，头指针head始终指向链表中的第一个节点。链表节点中的数据域data存有该节点的数据，指针域next存有下一个节点的内存地址，即上一个节点的指针域指向下一个节点。非循环链表尾结点的指针域next为NULL，表示已经到了链表的尾部。

优点

由于链表的存储结构不要求必须是连续的，因此避免了内存碎片的产生，提高了内存空间的利用率。此外，链表支持动态增加加或删除节点，即动态增加或删除数据元素。因此，使用链表时不需要像数组一样在声明时指定数组的长度大小。

链表增加或删除数据元素的操作本身时间复杂度为O(1)，直接更改指针域的链接次序即可。但增加或删除时需要先定位，定位时必须从头结点开始依次查找对应位置，定位操作时间复杂度为O(n)。所以链表增加或删除数据元素操作总的时间复杂度为O(n)。

尽管而数组增加或删除数据元素的时间复杂度也为O(n)，但数组中增加或删除数据元素时需要移动该数据元素之后的其他所有元素，移动比定位查找更消耗性能，因此链表增加或删除数据元素的效率仍然比数组高。

缺点

由于链表中每一个节点都包含指针域，这会带来一定的内存开销。此外，由于链表的存储结构不要求必须是连续的，因此不支持像数组一样通过下标索引随机存取数据元素。每次访问元素时都需要从头结点开始从前往后依次查找对应的元素。链表查找数据元素的时间复杂度为O(n)，而数组对应的时间复杂度为O(1)。

应用场景

链表一般用于元素数量不确定，需要频繁增加或删除元素时的情况。综合对比数组和链表的优缺点发现，链表擅长增加或删除元素，数组擅长访问元素。

基本操作

1、在C#中定义一个链表节点类型，C#中没有指针概念，因此我们用引用变量来代替。

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// 定义一个链表节点类型
public class Node<T>
{
    private T data; // 数据域，存储当前节点的数据
    private Node<T> next; // 引用域，存储下一个节点的内存地址
    
    public T Data
    {
        get
        {
            return data;
        }

        set
        {
            data = value;
        }
    }

    public Node<T> Next
    {
        get
        {
            return next;
        }

        set
        {
            next = value;
        }
    }
    
    // 链表节点构造函数
    public Node(T data, Node<T> next)
    {
        this.data = data;
        this.next = next;
    }
    
    // 链表节点构造函数
    public Node(Node<T> next)
    {
        this.next = next;
    }
    
    // 链表节点构造函数
    public Node(T data)
    {
        this.data = data;
    }
    
    // 链表尾节点的构造函数
    public Node()
    {
        data = default(T);
        next = null;
    }
}

2、定义一个单链表类型，以及获取长度和判空等基本函数。

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public class SingleLinkedList<T>
{
    // 头引用（头指针）head
    private Node<T> head;

    public Node<T> Head
    {
        get
        {
            return head;
        }
        
        set
        {
            head = value;
        }
    }
    
    // 构造函数初始化一个空表
    public SingleLinkedList()
    {
        head = null;
    }

    public int GetLength()
    {
        // 获取链表的头引用（头指针）
        Node<T> p = head;
        int len = 0;
        // 当引用不为空，则表示下一个节点存在。
        while (p != null)
        {
            len++;
            p = p.Next;
        }
        return len;
    }
    
    public void Clear()
    {
        // 头引用head为空，其余节点对象依然会存储在内存中，不会立刻销毁。
        // 但当其他节点对象不再使用时，CLR中的GC会回收并销毁这些节点对象。
        head = null;
    }
    
    // 单链表是否为空只需要判断其head头引用是否为null。
    public bool isEmpty()
    {
        if (head == null)
        {
            return true;
        }
        return false;
    }
}

3、为上面的单链表类型定义增加元素方法。

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// 在单链表末尾添加元素
public void Append(T item)
{
    // 待添加的元素节点
    Node<T> q = new Node<T>(item);
    // 单链表的尾节点，引用域为null。
    Node<T> p = new Node<T>();
  
    if (head == null)
    {
        // 如果链表为空，直接添加新元素，将新元素节点赋值给head头引用即可。
        head = q;
    }
    else
    {
        // 由于链表不支持顺序存储，因此添加定位时必须从头开始遍历。
        p = head;
        while (p.Next != null)
        {
            p = p.Next;
        }
        // 当p.Next为空时，表示该节点为链表的尾节点，直接赋值添加即可。
        p.Next = q;
    }
}

// 在单链表某个元素位置之后添加元素
public void InsertPost(T item, int i)
{
    // 头引用（头指针）
    Node<T> p = head;
    // 待添加的节点
    Node<T> q = new Node<T>(item);
    // 索引计数器 
    int j = 1;
    
    // 线性表的索引是从1开始而不是0，并且头结点一般不作为链表的第一个节点。
    if (isEmpty() || i < 1)
    {
        Console.WriteLine("List is empty or index is error");
        return;
    }

    while (p.Next != null && j < i)
    {
        p = p.Next;
        j++;
    }
  
    if (j == i)
    {
        // 先把插入位置处已存在元素p的引用域，赋给待添加元素q的引用域
        // 即先让q的引用域指向p引用域所指向的节点
        q.Next = p.Next;
        // 再让p的引用域指向q节点
        p.Next = q;
        // 在链表中插入或删除元素时，必须先更改引用域（指针域），再断开链表，不然链表节点将会丢失。
    }
    else
    {
        Console.WriteLine("Index is out of range.");
    }
}

4、为上面的单链表类型定义删除元素方法。

 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

// 删除单链表某个位置的元素
public void Delete(int i)
{
    Node<T> p = head;
    int j = 0;
    
    // 如果链表为空，则不能删除元素。
    if (head == null)
    {
        Console.WriteLine("List is empty.");
        return;
    }
  
    // 获取到要删除元素的前一个元素p
    while (p.Next != null && j < i-1)
    {
        p = p.Next;
        j++;
    }
    if (j == i-1)
    {
        // 通过p.Next.Next获取到待删除元素的下一个元素，然后将p的引用域直接指向这个元素即可。
        p.Next = p.Next.Next;
    }
    else
    {
        Console.WriteLine("Index is out of range.");
    }
}

5、为上面的单链表类型定义获取元素方法。

 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

// 获取某个元素
public T GetElement(int i)
{
    Node<T> p = head;
    int j = 0;

    if (head == null)
    {
        Console.WriteLine("List is empty.");
    }

    while(p.Next != null && j < i)
    {
        p = p.Next;
        j++;
    }
    if (j == i)
    {
        // 返回节点的值
        return p.Data;
    }
    else
    {
        Console.WriteLine("Index is out of range.");
        return default(T); // 找不到时，就直接返回泛型的默认值。
    }
}

6、使用该单链表类型。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Client
{
    public static void Main(string[] args)
    {
        // 新建一个单链表
        SingleLinkedList<int> sgl = new SingleLinkedList<int>();
        // 添加元素
        sgl.Append(1);
        sgl.Append(2);
        // 在索引1处添加元素2
        sgl.InsertPost(2, 1);
        // 删除索引2处的元素
        sgl.Delete(2);
        // 获取单链表长度
        Console.WriteLine(sgl.GetLength());
        // 判断链表是否为空
        Console.WriteLine(sgl.isEmpty());
        // 获取索引1处的元素
        Console.WriteLine(sgl.GetElement(1));
    }
}

拓展

双向链表

在单链表中没有指向直接前驱的指针域，因此访问前驱节点时只能从前往后依次遍历，时间复杂度为O(n)。为了克服这个缺点，双链表应运而生。双向链表又称双链表，它的每个节点除了一个数据域data之外，还有两个指针域，分别指向该节点的直接前驱prior和直接后继next。

正是因为这个两个指针域，双链表可以直接访问某个元素的前驱节点和后继节点，时间复杂度均为O(1)。但双链表查找定位元素依然要从头开始遍历，时间复杂度和单链表一样为O(n)。C#中内置了一个双向链表LinkedList类型，相关操作如下：

 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

using System;
using System.Collections.Generic;

namespace LinkedListExample
{
    class Client
    {
        public static void Main(string[] args)
        {
            // 声明并初始化双向链表
            LinkedList<int> numbers = new LinkedList<int>();
            // 声明并初始化节点
            LinkedListNode<int> node1 = new LinkedListNode<int>(1);
            LinkedListNode<int> node2 = new LinkedListNode<int>(2);
            LinkedListNode<int> node3 = new LinkedListNode<int>(3);
            LinkedListNode<int> node4 = new LinkedListNode<int>(4);

            // 添加节点，添加后的最终顺序为1、6、3、2、5、4
            numbers.AddFirst(node1);
            numbers.AddAfter(node1, node2);
            numbers.AddBefore(node2, node3);
            // 可以直接添加对应的值
            numbers.AddAfter(node2, 5);
            numbers.AddBefore(node3, 6);
            numbers.AddLast(node4);

            // 删除节点，直接删除对应的值，而不是该索引位置上的元素。
            numbers.Remove(5);
            numbers.RemoveLast();
            numbers.RemoveFirst();

            // 获取双向链表的长度
            Console.WriteLine(numbers.Count);

            // 输出双向链表的值
            // 从双向链表的第一个节点（不是头结点）开始遍历
            LinkedListNode<int> p = numbers.First;
            while (p != null)
            {
                Console.Write(p.Value);
                p = p.Next;
            }
            Console.WriteLine();

            // 查找元素，直接查找对应的值，而不是该索引位置上的元素。
            Console.WriteLine(numbers.Find(2).Value);
        }
    }
}
循环链表

循环链表和单链表的区别在于，循环链表中最后一个节点的指针域next不是NULL，而是指向头结点，从而使整个链表形成一个环。循环链表往往和双向链表一同使用组合成双向循环链表，但这同时也增加了链表的复杂度。对于由循环链表而言，判空条件不再是看头节点指针域是否为NULL，而是看它是否等于头指针。

由于循环链表是一个环，因此不再必须从头结点开始遍历，从表中任意一个元素节点开始遍历都行。在循环链表中，设置尾指针比设置头指针操作效率更高。因为设置头指针时，如果要对尾节点进行操作，就必须从头开始遍历，时间复杂度为O(n)。而设置尾指针后可同时操作尾结点和头结点，时间复杂度均为O(1)，因为循环链表的尾指针直接指向头结点。由于循环链表与单链表大同小异，这里就不用代码实现了。