双向链表

双向链表也叫双向表,是链表的一种,它由多个结点组成,每个结点都由一个数据域和两个指针域组成,数据域用 来存储数据,其中一个指针域用来指向其后继结点,另一个指针域用来指向前驱结点。链表的头结点的数据域不存 储数据,指向前驱结点的指针域值为null,指向后继结点的指针域指向第一个真正存储数据的结点。

image-20210506115312006

按照面向对象的思想,我们需要设计一个类,来描述结点这个事物。由于结点是属于链表的,所以我们把结点类作 为链表类的一个内部类来实现

双向链表结点设计

类名 Node
构造方法 Node(T t,Node pre,Node next):创建Node对象
成员变量 T item:存储数据
Node next:指向下一个结点
Node pre:指向上一个结点

双向链表Api设计

类名 TowWayLinkList
构造方法 TowWayLinkList():创建TowWayLinkList对象
成员方法 1.public void clear():空置线性表
2.publicboolean isEmpty():判断线性表是否为空,是返回true,否返回false
3.public int length():获取线性表中元素的个数
4.public T get(int i):读取并返回线性表中的第i个元素的值
5.public void insert(T t):往线性表中添加一个元素;
6.public void insert(int i,T t):在线性表的第i个元素之前插入一个值为t的数据元素。
7.public T remove(int i):删除并返回线性表中第i个数据元素。
8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号,若不存在,则 返回-1。
9.public T getFirst():获取第一个元素
10.public T getLast():获取最后一个元素
成员内部类 private class Node:结点类
成员变量 1.private Node first:记录首结点
2.private Node last:记录尾结点
2.private int N:记录链表的长度

代码实现

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
package com.bestrookie.link;

import java.util.Iterator;

/**
* @author : bestrookie
* @date : 9:25 2021/5/6
*/
public class TwoWayLinkList<T> implements Iterable<T> {
/**
* 头结点
*/
private Node head;
/**
* 尾结点
*/
private Node last;
/**
* 链表的总长度
*/
private int N;
private class Node {
//存储数据
public T item;
//指向上一个结点
public Node pre;
//指向下一个结点
public Node next;
public Node(T item,Node pre,Node next){
this.item = item;
this.pre = pre;
this.next = next;
}
}
public TwoWayLinkList(){
//初始化头结点和尾结点
this.head = new Node(null,null,null);
this.last = null;
//链表的总长度为0
this.N = 0;
}

/**
* 清空链表
*/
public void clean(){
this.head.next = null;
this.last = null;
this.N = 0;
}

/**
* 获取链表的长度
* @return 链表长度
*/
public int length(){
return N;
}

/**
* 判断链表是否为空
* @return 是否为空
*/
public boolean isEmpty(){
return N == 0;
}

/**
* 获取第一个元素
* @return 第一个元素
*/
public T getFirst(){
if (isEmpty()){
return null;
}
return head.next.item;
}

/**
* 获取最后一个元素
* @return 最后一个元素
*/
public T getLast(){
if (isEmpty()){
return null;
}
return last.item;
}

/**
* 插入一个结点
* @param t 插入的结点
*/
public void insert(T t){
if(isEmpty()){
//如果链表为空
//创建新结点
//尾结点为新结点
last = new Node(t,head,null);
//头结点指向尾结点
head.next = last;
}else {
//如果链表不为空
//几率旧的尾结点
Node oldLast = last;
//创建新的结点
Node newNode = new Node(t,oldLast,null);
//当前尾结点指向新节点
oldLast.next = newNode;
//新节点称为尾结点
last = newNode;
}
//链表长度+1
N++;
}

/**
* 在指定位置插入结点
* @param i 指定位置
* @param t 插入的元素
*/
public void insert(int i,T t){
//找到i位置的前一个结点
Node pre = head;
for (int index = 0; index < i; index++){
pre = pre.next;
}
//找到当前结点
Node curr = pre.next;
//创建一个新结点
Node newNode = new Node(t,pre,curr);
//i位置的前一个结点的先一个结点指向新节点
pre.next = newNode;
//原来i位置结点的前一个结点指向新节点
curr.pre = newNode;
//链表长度+1
N++;
}

/**
* 获取指定位置的元素
* @param i 指定位置
* @return 元素内容
*/
public T get(int i){
Node n = head.next;
for (int index = 0; index < i; index++){
n = n.next;
}
return n.item;
}

/**
* 获取指定元素第一次出现的位置
* @param t 指定元素
* @return 第一次出现的位置
*/
public int indexOf(T t){
Node n = head;
for (int index = 0; n.next != null; index++){
n = n.next;
if (n.item.equals(t)){
return index;
}
}
return -1;

}

/**
* 删除指定位置的元素
* @param i 指定位置
* @return 删除元素
*/
public T remove(int i){
//找到i位置的前一个结点
Node pre = head;
for (int index = 0;index < i; index++){
pre = pre.next;
}
//找到当前结点
Node curr = pre.next;
//找到当前结点的下一个结点
Node nextNode = curr.next;
//i位置的前一个结点指向i位置的下一个结点
pre.next = nextNode;
//i位置下一个结点的上一个结点指向i位置的前一个结点
nextNode.pre = pre;
//链表长度-1
N--;
return curr.item;
}
@Override
public Iterator<T> iterator() {
return new TIterator();
}
private class TIterator implements Iterator{
private Node n;
public TIterator(){
this.n = head;
}

@Override
public boolean hasNext() {

return n.next != null;
}

@Override
public Object next() {
n = n.next;
return n.item;
}
}
}

测试代码

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
package com.bestrookie.test;

import com.bestrookie.link.LinkList;
import com.bestrookie.link.TwoWayLinkList;

/**
* @author : bestrookie
* @date : 19:00 2021/5/5
*/
public class TwoWayTestLink {
public static void main(String[] args) {
TwoWayLinkList<String> s1 =new TwoWayLinkList<>();
s1.insert("姚明");
s1.insert("科比");
s1.insert("麦迪");
s1.insert("詹姆斯");
System.out.println("插入新元素前的元素个数:"+s1.length());
for (String s : s1) {
System.out.println(s);
}
s1.insert(1,"库里");
System.out.println("插入元素后的元素个数:"+s1.length());
for (String s : s1) {
System.out.println(s);
}
System.out.println("=================");
System.out.println("获取索引2的位置的数据:"+s1.get(2));
String remove = s1.remove(3);
System.out.println("删除索引3位置的数据并返回:"+remove+"删除后的元素个数"+s1.length());
System.out.println("=======================");
System.out.println("获取第一个元素:"+s1.getFirst());
System.out.println("获取最后一个元素:"+s1.getLast());
System.out.println("获取元素第一次出现的位置:"+s1.indexOf("科比"));
s1.clean();
System.out.println("========清空链表=======");
System.out.println(s1.length());

}
}

评论