第3章：单链表

本章目标

  1. 了解单链表的概念

  2. 掌握双链表存储结构的特点

  3. 掌握双链表的基本操作

  4. 对比单链表和双链表的区别

本章内容

顺序存储结构分析

  • 特点
    • 以数据元素物理位置的相邻表示逻辑关系的相邻
  • 优势
    • 随机存取元素时比较简单
    • 存储空间使用紧凑
  • 劣势
    • 插入、删除操作需移动较多数据元素，效率较低
    • 表容量难以扩充

链式存储结构

一种物理存储单元上非连续、非顺序的存储结构，简称为“链表”。

链表由一系列结点组成，每个结点包括两个部分：

  • 数据域:保存数据元素
  • 指针域:保存直接前驱元素或者直接后继元素的存储位置

单链表

  • 用一组任意的存储单元，存储线性表的各个数据元素。
  • 每个元素，除了存储自身信息外，还需要保存直接后继元素的存储位置。
  • 也称为“线性链表”

单链表的一般形式：

  • 带表头结点的非空单链表
  • 带表头结点的空单链表

示例：

使用单链表保存数据a1, a2，a3, 将数据a4插入到a1,a2之间，然后删除a2.

单链表的基本操作

  • 链表的初始化
  • 判断链表是否为空
  • 获取链表长度
  • 插入元素
  • 移除元素
  • 修改指定位置的对象
  • 查找数据元素的位置
  • 查询指定索引的对象

单链表初始化

问题：

如何构造带表头结点的空单链表？

示例：

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        TNode<T> next;
    }
}

单链表信息统计

问题：

如何判断单链表是否为空？

如何获取链表长度？

示例：

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
64
65
66
67
68
69
70
71
72
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        TNode<T> next;
    }
}

单链表的数据插入方式

单链表中数据的插入分三种情况：

  • 插入点在链表开头，插入元素做首结点
  • 插入点在链表结尾，插入元素做尾结点
  • 插入点在链表指定索引

插入数据到链表头

问题：

如何将数据为element的新结点插入单链表，作为链表的首结点？

分析：

  • 构造新结点保存数据element
  • 将新结点的指针指向链表的首结点
  • 设置新结点为链表的首结点
  • 链表长度加1

示例：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
        /// <summary>
        /// 插入数据到头
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            //接点
            TNode<T> node = new TNode<T>(item,this.Head.next);

            //关联到头节点
            this.Head.next = node;

            //更新数量
            this.Length++;
            
        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public TNode<T> next;
        public TNode() { }
        public TNode(T data,TNode<T> next)
        {
            this.data = data;
            this.next = next;
        }
    }
}

插入数据到链表尾

问题：

如何将数据为element的新结点插入单链表，作为链表的尾结点？

分析：

  • 构造新结点保存数据element
  • 遍历链表，获取尾结点
  • 将尾结点的指针指向新结点
  • 链表长度加1

示例：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
        /// <summary>
        /// 插入数据到头
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            //接点
            TNode<T> node = new TNode<T>(item,this.Head.next);

            //关联到头节点
            this.Head.next = node;

            //更新数量
            this.Length++;
            
        }

        /// <summary>
        /// 插入数据到尾
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            //新结点
            TNode<T> newNode=new TNode<T> (item,null);

            //接点
            TNode<T> node = this.Head;

            for (int i = 0; i < this.Length; i++)
            {
                node = node.next;
            }

            node.next = newNode;

            //更新数量
            this.Length++;

        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public TNode<T> next;
        public TNode() { }
        public TNode(T data,TNode<T> next)
        {
            this.data = data;
            this.next = next;
        }
    }
}

插入数据到链表指定位置

问题：

如何将数据为element的新结点插入到表的 第i(2≤i≤n)个结点的位置上，即插入到ai-1与ai之间？

分析：

  • 判断索引i是否在有效范围内，如果无效，不允许插入
  • 构造新结点保存数据element
  • 遍历链表，找到第i-1个结点
  • 设置新结点的指针指向第i个结点
  • 修改第i-1个结点的指针指向新结点
  • 链表长度加1

示例：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
        /// <summary>
        /// 插入数据到头
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            //接点
            TNode<T> node = new TNode<T>(item,this.Head.next);

            //关联到头节点
            this.Head.next = node;

            //更新数量
            this.Length++;
            
        }

        /// <summary>
        /// 插入数据到尾
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            //新结点
            TNode<T> newNode=new TNode<T> (item,null);

            //接点
            TNode<T> node = this.Head;

            for (int i = 0; i < this.Length; i++)
            {
                node = node.next;
            }

            node.next = newNode;

            //更新数量
            this.Length++;

        }

        /// <summary>
        /// 插入数据到指定索引
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            if (index < 0 || index > this.Length) return;

            TNode<T> tempNode= this.Head;
            for (int i = 0; i < index; i++)
            {
                tempNode = tempNode.next;
            }

            //新接点
            TNode<T> newNode = new TNode<T>(item, tempNode.next);

            //更新引用
            tempNode.next = newNode;

            this.Length++;
        }

        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.InsertLast(item);
        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public TNode<T> next;
        public TNode() { }
        public TNode(T data,TNode<T> next)
        {
            this.data = data;
            this.next = next;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
private void button3_Click(object sender, EventArgs e)
{
    SingleLinkedList<string> list = new SingleLinkedList<string>();

    list.Add("张三");
    list.Add("李四");
    list.Add("王五");

    list.Insert(1, "孙悟空");
}

删除单链表的接点

单链表中数据的删除分三种情况：

  • 删除链表首结点
  • 删除链表尾结点
  • 删除链表中间结点

删除链表首结点

问题：

如何删除链表的首结点？

分析：

  • 判断链表状态，如果链表为空，不允许删除
  • 如果不为空，设置表头结点指向链表中第二个结点
  • 链表长度减1

示例：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
        /// <summary>
        /// 插入数据到头
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            //接点
            TNode<T> node = new TNode<T>(item,this.Head.next);

            //关联到头节点
            this.Head.next = node;

            //更新数量
            this.Length++;
            
        }

        /// <summary>
        /// 插入数据到尾
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            //新结点
            TNode<T> newNode=new TNode<T> (item,null);

            //接点
            TNode<T> node = this.Head;

            for (int i = 0; i < this.Length; i++)
            {
                node = node.next;
            }

            node.next = newNode;

            //更新数量
            this.Length++;

        }

        /// <summary>
        /// 插入数据到指定索引
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            if (index < 0 || index > this.Length) return;

            TNode<T> tempNode= this.Head;
            for (int i = 0; i < index; i++)
            {
                tempNode = tempNode.next;
            }

            //新接点
            TNode<T> newNode = new TNode<T>(item, tempNode.next);

            //更新引用
            tempNode.next = newNode;

            this.Length++;
        }

        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.InsertLast(item);
        }

        /// <summary>
        /// 删除首结点
        /// </summary>
        public void RemoveFirst()
        {
            //判断数量
            if (this.Length == 0) return;

            //向后移动
            this.Head.next=this.Head.next.next;

            //更新数量
            this.Length--;
        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public TNode<T> next;
        public TNode() { }
        public TNode(T data,TNode<T> next)
        {
            this.data = data;
            this.next = next;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
private void button4_Click(object sender, EventArgs e)
{
    SingleLinkedList<string> list = new SingleLinkedList<string>();

    list.Add("张三");
    list.Add("李四");
    list.Add("王五");

    //删除首结点
    list.RemoveFirst();
}

删除链表尾结点

问题：

如何删除链表的尾结点？

分析：

  • 判断链表状态，如果链表为空，不允许删除
  • 如果不为空，将尾结点的前一个结点的指针置为空
  • 链表长度减1

示例：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms.VisualStyles;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
        /// <summary>
        /// 插入数据到头
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            //接点
            TNode<T> node = new TNode<T>(item,this.Head.next);

            //关联到头节点
            this.Head.next = node;

            //更新数量
            this.Length++;
            
        }

        /// <summary>
        /// 插入数据到尾
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            //新结点
            TNode<T> newNode=new TNode<T> (item,null);

            //接点
            TNode<T> node = this.Head;

            for (int i = 0; i < this.Length; i++)
            {
                node = node.next;
            }

            node.next = newNode;

            //更新数量
            this.Length++;

        }

        /// <summary>
        /// 插入数据到指定索引
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            if (index < 0 || index > this.Length) return;

            TNode<T> tempNode= this.Head;
            for (int i = 0; i < index; i++)
            {
                tempNode = tempNode.next;
            }

            //新接点
            TNode<T> newNode = new TNode<T>(item, tempNode.next);

            //更新引用
            tempNode.next = newNode;

            this.Length++;
        }

        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.InsertLast(item);
        }

        /// <summary>
        /// 删除首结点
        /// </summary>
        public void RemoveFirst()
        {
            //判断数量
            if (this.IsEmpty()) return;

            //向后移动
            this.Head.next=this.Head.next.next;

            //更新数量
            this.Length--;
        }

        /// <summary>
        /// 删除尾结点
        /// </summary>
        public void RemoveLast()
        {
            //判断数量
            if (this.IsEmpty()) return;

            TNode<T> tempNode = this.Head;

            for(int i=1;i<this.Length; i++)
            {
                tempNode= tempNode.next;
            }

            tempNode.next = null;

            //更新数量
            this.Length--;
        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public TNode<T> next;
        public TNode() { }
        public TNode(T data,TNode<T> next)
        {
            this.data = data;
            this.next = next;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
private void button5_Click(object sender, EventArgs e)
{
    SingleLinkedList<string> list = new SingleLinkedList<string>();

    list.Add("张三");
    list.Add("李四");
    list.Add("王五");

    //删除尾结点
    list.RemoveLast();
}

删除链表中间结点

问题：

如何删除单链表中第i个结点？

分析：

  • 信息有效性判断
    • 链表是否为空
    • 索引i是否在有效范围内
  • 如果信息有效，从表头结点开始，找到线性表中 第i-1个结点
  • 修改其指针，指向第i+1个结点
  • 链表长度减1

示例：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms.VisualStyles;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
        /// <summary>
        /// 插入数据到头
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            //接点
            TNode<T> node = new TNode<T>(item,this.Head.next);

            //关联到头节点
            this.Head.next = node;

            //更新数量
            this.Length++;
            
        }

        /// <summary>
        /// 插入数据到尾
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            //新结点
            TNode<T> newNode=new TNode<T> (item,null);

            //接点
            TNode<T> node = this.Head;

            for (int i = 0; i < this.Length; i++)
            {
                node = node.next;
            }

            node.next = newNode;

            //更新数量
            this.Length++;

        }

        /// <summary>
        /// 插入数据到指定索引
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            if (index < 0 || index > this.Length) return;

            TNode<T> tempNode= this.Head;
            for (int i = 0; i < index; i++)
            {
                tempNode = tempNode.next;
            }

            //新接点
            TNode<T> newNode = new TNode<T>(item, tempNode.next);

            //更新引用
            tempNode.next = newNode;

            this.Length++;
        }

        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.InsertLast(item);
        }

        /// <summary>
        /// 删除首结点
        /// </summary>
        public void RemoveFirst()
        {
            //判断数量
            if (this.IsEmpty()) return;

            //向后移动
            this.Head.next=this.Head.next.next;

            //更新数量
            this.Length--;
        }

        /// <summary>
        /// 删除尾结点
        /// </summary>
        public void RemoveLast()
        {
            //判断数量
            if (this.IsEmpty()) return;

            TNode<T> tempNode = this.Head;

            for(int i=1;i<this.Length; i++)
            {
                tempNode= tempNode.next;
            }

            tempNode.next = null;

            //更新数量
            this.Length--;
        }

        /// <summary>
        /// 删除指定索引元素
        /// </summary>
        /// <param name="index"></param>
        public void RemoveAt(int index)
        {
            if (this.IsEmpty()) return;
            if (index < 0 || index >= this.Length) return;

            TNode<T> tempNode = this.Head;

            //定位到前一个元素
            for(int i = 0; i < index; i++)
            {
                tempNode=tempNode.next;
            }

            //更新前后关系
            tempNode.next=tempNode.next.next;

            //更新数量
            this.Length --;
        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public TNode<T> next;
        public TNode() { }
        public TNode(T data,TNode<T> next)
        {
            this.data = data;
            this.next = next;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
private void button6_Click(object sender, EventArgs e)
{
    SingleLinkedList<string> list = new SingleLinkedList<string>();

    list.Add("张三");
    list.Add("李四");
    list.Add("王五");
    list.Add("赵六");
    list.Add("田七");

    //删除中间结点
    list.RemoveAt(2);
}

修改单链表结点

问题：

如何实现将单链表的第i(1≤i≤n)个结点的数据元素ai修改为element？

分析：

  • 信息有效性判断
    • 链表是否为空
    • 索引i是否在有效范围内
  • 如果信息有效，找到线性表中第i个结点
  • 修改数据域内容

示例：

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms.VisualStyles;

namespace CH03Demo
{
    /// <summary>
    /// 单链表
    /// </summary>
    internal class SingleLinkedList<T>
    {
        /// <summary>
        /// 长度
        /// </summary>
        private int Length;

        /// <summary>
        /// 头节点
        /// </summary>
        private TNode<T> Head;

        /// <summary>
        /// 构造函数
        /// </summary>
        public SingleLinkedList()
        {
            this.Length = 0;
            this.Head = new TNode<T>();
        }

        /// <summary>
        /// 获取链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {

            return this.Length; 
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.Length == 0; 
        }
    
        /// <summary>
        /// 插入数据到头
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            //接点
            TNode<T> node = new TNode<T>(item,this.Head.next);

            //关联到头节点
            this.Head.next = node;

            //更新数量
            this.Length++;
            
        }

        /// <summary>
        /// 插入数据到尾
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            //新结点
            TNode<T> newNode=new TNode<T> (item,null);

            //接点
            TNode<T> node = this.Head;

            for (int i = 0; i < this.Length; i++)
            {
                node = node.next;
            }

            node.next = newNode;

            //更新数量
            this.Length++;

        }

        /// <summary>
        /// 插入数据到指定索引
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            if (index < 0 || index > this.Length) return;

            TNode<T> tempNode= this.Head;
            for (int i = 0; i < index; i++)
            {
                tempNode = tempNode.next;
            }

            //新接点
            TNode<T> newNode = new TNode<T>(item, tempNode.next);

            //更新引用
            tempNode.next = newNode;

            this.Length++;
        }

        /// <summary>
        /// 添加数据
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.InsertLast(item);
        }

        /// <summary>
        /// 删除首结点
        /// </summary>
        public void RemoveFirst()
        {
            //判断数量
            if (this.IsEmpty()) return;

            //向后移动
            this.Head.next=this.Head.next.next;

            //更新数量
            this.Length--;
        }

        /// <summary>
        /// 删除尾结点
        /// </summary>
        public void RemoveLast()
        {
            //判断数量
            if (this.IsEmpty()) return;

            TNode<T> tempNode = this.Head;

            for(int i=1;i<this.Length; i++)
            {
                tempNode= tempNode.next;
            }

            tempNode.next = null;

            //更新数量
            this.Length--;
        }

        /// <summary>
        /// 删除指定索引元素
        /// </summary>
        /// <param name="index"></param>
        public void RemoveAt(int index)
        {
            if (this.IsEmpty()) return;
            if (index < 0 || index >= this.Length) return;

            TNode<T> tempNode = this.Head;

            //定位到前一个元素
            for(int i = 0; i < index; i++)
            {
                tempNode=tempNode.next;
            }

            //更新前后关系
            tempNode.next=tempNode.next.next;

            //更新数量
            this.Length --;
        }

        /// <summary>
        /// 修改指定索引元素
        /// </summary>
        /// <param name="index"></param>
        public void Set(int index,T item)
        {
            if (this.IsEmpty()) return;
            if (index < 0 || index >= this.Length) return;

            TNode<T> tempNode = this.Head;

            //定位到前一个元素
            for (int i = 0; i <= index; i++)
            {
                tempNode = tempNode.next;
            }

            //更新前后关系
            tempNode.data = item;
        }
    }

    /// <summary>
    /// 接点
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class TNode<T>
    {
        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        /// <summary>
        /// 下一个节点
        /// </summary>
        public TNode<T> next;
        public TNode() { }
        public TNode(T data,TNode<T> next)
        {
            this.data = data;
            this.next = next;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
private void button7_Click(object sender, EventArgs e)
{
    SingleLinkedList<string> list = new SingleLinkedList<string>();

    list.Add("张三");
    list.Add("李四");
    list.Add("王五");
    list.Add("赵六");
    list.Add("田七");

    //修改指定结点
    list.Set(2, "孙悟空");
}

单链表总结

特点：

  • 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系

优势：

  • 插入、删除操作通过修改结点的指针实现，效率较高
  • 不需要预先开辟存储空间

缺点：

  • 不能随机存储数据，查找速度慢
  • 指针需要占用额外存储空间
  • 结点的查找只能从表头结点开始，由前向后查找，不能反向查找

本章总结

略

课后作业

略