第4章：双链表

本章目标

  1. 了解线性表的概念

  2. 掌握线性表顺序存储结构的特点

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

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }
    }

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

    }   
}

双链表的信息统计

问题：

  • 如何判断单链表是否为空？
  • 如何获取链表长度？

示例：

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

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }
    }

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

    }    
}

双链表的插入

双链表中数据的插入分三种情况:

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

插入元素到头部

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

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //初始化首尾结点
            this.head = new TNode<T>();
            this.tail = new TNode<T>();

            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }

        /// <summary>
        /// 插入到头部
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向后关联关系
            node.nextNode = this.head.nextNode;
            this.head.nextNode.prevNode = node;

            //向前关联关系
            this.head.nextNode = node;
            node.prevNode = this.head;

            this.length++;
        }
    }

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

        public TNode() { }
        public TNode(T data) { 
            this.data = data;
        }
    }
}

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

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

插入元素到尾部

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

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //初始化首尾结点
            this.head = new TNode<T>();
            this.tail = new TNode<T>();

            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }

        /// <summary>
        /// 插入到头部
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向后关联关系
            node.nextNode = this.head.nextNode;
            this.head.nextNode.prevNode = node;

            //向前关联关系
            this.head.nextNode = node;
            node.prevNode = this.head;

            this.length++;
        }

        /// <summary>
        /// 插入到尾部
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向前关联关系
            this.tail.nextNode = node;
            node.prevNode = this.tail;

            this.length++;
        }
    }

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

        public TNode() { }
        public TNode(T data) { 
            this.data = data;
        }

    }
         
}

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

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

插入元素到中间

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

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //初始化首尾结点
            this.head = new TNode<T>();
            this.tail = new TNode<T>();

            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }

        /// <summary>
        /// 插入到头部
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向后关联关系
            node.nextNode = this.head.nextNode;
            this.head.nextNode.prevNode = node;

            //向前关联关系
            this.head.nextNode = node;
            node.prevNode = this.head;

            this.length++;
        }

        /// <summary>
        /// 插入到尾部
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向前关联关系
            this.tail.prevNode.nextNode = node;
            node.prevNode = this.tail.prevNode;

            //向后关联关系
            node.nextNode = this.tail;
            this.tail.prevNode = node;

            //更新大小
            this.length++;
        }

        /// <summary>
        /// 插入到中间
        /// </summary>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            //校验索引
            if (index < 0 || index > this.length) return;

            //新结点
            TNode<T> node = new TNode<T>(item);

            //临时结点
            TNode<T> tempNode= this.head;
            for(int i = 0; i < index; i++)
            {
                tempNode= tempNode.nextNode;
            }

            //向后关联关系
            node.nextNode = tempNode.nextNode;
            tempNode.nextNode.prevNode = node;

            //向前关联关系
            tempNode.nextNode = node;
            node.prevNode = tempNode;

            //更新大小
            this.length++;
        }
    }

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

        public TNode() { }
        public TNode(T data) { 
            this.data = data;
        }

    }
         
}

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

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

    list.Insert(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
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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //初始化首尾结点
            this.head = new TNode<T>();
            this.tail = new TNode<T>();

            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }

        /// <summary>
        /// 插入到头部
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向后关联关系
            node.nextNode = this.head.nextNode;
            this.head.nextNode.prevNode = node;

            //向前关联关系
            this.head.nextNode = node;
            node.prevNode = this.head;

            this.length++;
        }

        /// <summary>
        /// 插入到尾部
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向前关联关系
            this.tail.prevNode.nextNode = node;
            node.prevNode = this.tail.prevNode;

            //向后关联关系
            node.nextNode = this.tail;
            this.tail.prevNode = node;

            //更新大小
            this.length++;
        }

        /// <summary>
        /// 插入到中间
        /// </summary>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            //校验索引
            if (index < 0 || index > this.length) return;

            //新结点
            TNode<T> node = new TNode<T>(item);

            //临时结点
            TNode<T> tempNode= this.head;
            for(int i = 0; i < index; i++)
            {
                tempNode= tempNode.nextNode;
            }

            //向后关联关系
            node.nextNode = tempNode.nextNode;
            tempNode.nextNode.prevNode = node;

            //向前关联关系
            tempNode.nextNode = node;
            node.prevNode = tempNode;

            //更新大小
            this.length++;
        }

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

            TNode<T> delNode= this.head;
            for(int i = 0; i <= index; i++)
            {
                delNode= delNode.nextNode;
            }

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;

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

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

        public TNode() { }
        public TNode(T data) { 
            this.data = data;
        }

    }
         
}

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

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

    list.Remove(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
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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //初始化首尾结点
            this.head = new TNode<T>();
            this.tail = new TNode<T>();

            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }

        /// <summary>
        /// 插入到头部
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向后关联关系
            node.nextNode = this.head.nextNode;
            this.head.nextNode.prevNode = node;

            //向前关联关系
            this.head.nextNode = node;
            node.prevNode = this.head;

            this.length++;
        }

        /// <summary>
        /// 插入到尾部
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向前关联关系
            this.tail.prevNode.nextNode = node;
            node.prevNode = this.tail.prevNode;

            //向后关联关系
            node.nextNode = this.tail;
            this.tail.prevNode = node;

            //更新大小
            this.length++;
        }

        /// <summary>
        /// 插入到中间
        /// </summary>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            //校验索引
            if (index < 0 || index > this.length) return;

            //新结点
            TNode<T> node = new TNode<T>(item);

            //临时结点
            TNode<T> tempNode= this.head;
            for(int i = 0; i < index; i++)
            {
                tempNode= tempNode.nextNode;
            }

            //向后关联关系
            node.nextNode = tempNode.nextNode;
            tempNode.nextNode.prevNode = node;

            //向前关联关系
            tempNode.nextNode = node;
            node.prevNode = tempNode;

            //更新大小
            this.length++;
        }

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

            TNode<T> delNode= this.head;
            for(int i = 0; i <= index; i++)
            {
                delNode= delNode.nextNode;
            }

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;

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

        /// <summary>
        /// 删除第一个元素
        /// </summary>
        /// <param name="index"></param>
        public void RemoveFirst()
        {
            if (this.IsEmpty()) return;

            TNode<T> delNode = this.head.nextNode;

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;


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

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

        public TNode() { }
        public TNode(T data) { 
            this.data = data;
        }

    }
         
}

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

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

    list.RemoveFirst();
}

删除链表的尾结点

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

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //初始化首尾结点
            this.head = new TNode<T>();
            this.tail = new TNode<T>();

            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }

        /// <summary>
        /// 插入到头部
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向后关联关系
            node.nextNode = this.head.nextNode;
            this.head.nextNode.prevNode = node;

            //向前关联关系
            this.head.nextNode = node;
            node.prevNode = this.head;

            this.length++;
        }

        /// <summary>
        /// 插入到尾部
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向前关联关系
            this.tail.prevNode.nextNode = node;
            node.prevNode = this.tail.prevNode;

            //向后关联关系
            node.nextNode = this.tail;
            this.tail.prevNode = node;

            //更新大小
            this.length++;
        }

        /// <summary>
        /// 插入到中间
        /// </summary>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            //校验索引
            if (index < 0 || index > this.length) return;

            //新结点
            TNode<T> node = new TNode<T>(item);

            //临时结点
            TNode<T> tempNode= this.head;
            for(int i = 0; i < index; i++)
            {
                tempNode= tempNode.nextNode;
            }

            //向后关联关系
            node.nextNode = tempNode.nextNode;
            tempNode.nextNode.prevNode = node;

            //向前关联关系
            tempNode.nextNode = node;
            node.prevNode = tempNode;

            //更新大小
            this.length++;
        }

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

            TNode<T> delNode= this.head;
            for(int i = 0; i <= index; i++)
            {
                delNode= delNode.nextNode;
            }

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;

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

        /// <summary>
        /// 删除第一个元素
        /// </summary>
        /// <param name="index"></param>
        public void RemoveFirst()
        {
            if (this.IsEmpty()) return;

            TNode<T> delNode = this.head.nextNode;

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;


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

        /// <summary>
        /// 删除最后一个元素
        /// </summary>
        /// <param name="index"></param>
        public void RemoveLast()
        {
            if (this.IsEmpty()) return;

            TNode<T> delNode = this.tail.prevNode;

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;


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

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        private T data;

        public TNode() { }
        public TNode(T data) { 
            this.data = data;
        }

    }
         
}

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

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

    list.RemoveLast();
}

修改结点

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
234
235
236
237
238
239
240
241
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CH04Demo
{
    /// <summary>
    /// 双链表
    /// </summary>
    public class DoubleLinkedList<T>
    {
        /// <summary>
        /// 头
        /// </summary>
        private TNode<T> head;

        /// <summary>
        /// 尾
        /// </summary>
        private TNode<T> tail;

        /// <summary>
        /// 长度
        /// </summary>
        private int length;

        public DoubleLinkedList()
        {
            //初始化首尾结点
            this.head = new TNode<T>();
            this.tail = new TNode<T>();

            //头尾相连
            this.head.nextNode = this.tail;
            this.tail.prevNode = this.head;

            this.length = 0;
        }

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

            return this.length == 0; 
        }

        /// <summary>
        /// 链表大小
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.length;
        }

        /// <summary>
        /// 插入到头部
        /// </summary>
        /// <param name="item"></param>
        public void InsertFirst(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向后关联关系
            node.nextNode = this.head.nextNode;
            this.head.nextNode.prevNode = node;

            //向前关联关系
            this.head.nextNode = node;
            node.prevNode = this.head;

            this.length++;
        }

        /// <summary>
        /// 插入到尾部
        /// </summary>
        /// <param name="item"></param>
        public void InsertLast(T item)
        {
            TNode<T> node = new TNode<T>(item);

            //向前关联关系
            this.tail.prevNode.nextNode = node;
            node.prevNode = this.tail.prevNode;

            //向后关联关系
            node.nextNode = this.tail;
            this.tail.prevNode = node;

            //更新大小
            this.length++;
        }

        /// <summary>
        /// 插入到中间
        /// </summary>
        /// <param name="item"></param>
        public void Insert(int index,T item)
        {
            //校验索引
            if (index < 0 || index > this.length) return;

            //新结点
            TNode<T> node = new TNode<T>(item);

            //临时结点
            TNode<T> tempNode= this.head;
            for(int i = 0; i < index; i++)
            {
                tempNode= tempNode.nextNode;
            }

            //向后关联关系
            node.nextNode = tempNode.nextNode;
            tempNode.nextNode.prevNode = node;

            //向前关联关系
            tempNode.nextNode = node;
            node.prevNode = tempNode;

            //更新大小
            this.length++;
        }

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

            TNode<T> delNode= this.head;
            for(int i = 0; i <= index; i++)
            {
                delNode= delNode.nextNode;
            }

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;

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

        /// <summary>
        /// 删除第一个元素
        /// </summary>
        /// <param name="index"></param>
        public void RemoveFirst()
        {
            if (this.IsEmpty()) return;

            TNode<T> delNode = this.head.nextNode;

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;


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

        /// <summary>
        /// 删除最后一个元素
        /// </summary>
        /// <param name="index"></param>
        public void RemoveLast()
        {
            if (this.IsEmpty()) return;

            TNode<T> delNode = this.tail.prevNode;

            //更新结点引用关系
            delNode.prevNode.nextNode = delNode.nextNode;
            delNode.nextNode.prevNode = delNode.prevNode;


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

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

            TNode<T> node= this.head;
            for(int i = 0; i <= index; i++)
            {
                node = node.nextNode;
            }

            node.data = item;
        }
    }

    /// <summary>
    /// 结点类
    /// </summary>
    public class TNode<T>
    {
        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> prevNode;

        /// <summary>
        /// 前节点
        /// </summary>
        public TNode<T> nextNode;

        /// <summary>
        /// 数据
        /// </summary>
        public T data;

        public TNode() { }
        public TNode(T data) { 
            this.data = data;
        }

    }
         
}

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

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

    list.Set(2, "孙悟空");
}

本章总结

略

课后作业

略