单向链表和双向链表的区别
| 单向链表 | 双向链表 | |
|---|---|---|
| 查找方向 | 单向 | 可以向前查找也可以向后查找 |
| 删除 | 需要辅助节点 | 不需要辅助节点 |
所以相对单向链表，我们需要在节点中新加入一个per指向前一个节点的域。
双向链表代码实现
写一个新的Students类，相对单链表多了pre
class Students {
public String name; // 学生的姓名
public int id; // 学生的学号
public Students pre; // 节点的前一个
public Students next; // 节点的后一个
public Students(String name, int id) {
this.name = name;
this.id = id;
}
@Override
public String toString() {
return "Student{" + "name='" + name + '\'' + ", id=" + id + '}';
}
}
然后是对双向链表的各种操作
class DoubleLinkedList {
// 创建头节点
private Students head = new Students("", 0);
// 遍历链表
public void showList() {
if (head.next == null) {
System.out.println("链表为空");
return;
}
Students temp = head.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
// 添加节点到双向链表的最后
public void add(Students students) {
Students temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = students;
students.pre = temp;
}
// 更具顺序添加节点
public void addByOrder(Students students) {
Students temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.id > students.id) {
break;
} else if (temp.next.id == students.id) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
System.out.println("该节点已经存在");
} else {
students.next = temp.next;
temp.next = students;
students.pre = temp;
// 这里存在一个当最后一个节点为空时，没有pre域，所以要进行判断。
if (students.next != null) {
students.next.pre = students;
}
}
}
// 修改节点信息
public void update(Students students) {
if (head.next == null) {
System.out.println("链表为空");
return;
}
Students temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (students.id == temp.id) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = students.name;
temp.id = students.id;
} else {
System.out.println("没有该节点");
}
}
// 删除节点
public void del(int num) {
Students temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.id == num) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
// 要对是否为最后一个节点进行判断
if (temp.next != null) {
temp.next.pre = temp;
}
} else {
System.out.println("没有该节点");
}
}
}
