08、数据结构与算法 - 实战：双向链表
概念
检索起点跟单向链表一样
每个节点有指向上一个节点、以及下一个节点的指针
双向链表 - 添加节点到尾部
代码实现
class DoubleLinkedList<T> {
// 链表头指针
Node<T> headPointer = new Node<T>();
public void add(T a) {
// 1. 添加的元素封装成一个节点
Node<T> newNode = new Node<T>(a);
// 2. 表示遍历到的节点
Node<T> temp = headPointer;
// 3. 寻找到 next=null的尾节点
while(temp.next != null) {
temp = temp.next;
}
// 4. 尾节点的next指向 新节点
temp.next = newNode;
// 5. 新节点的pre指向 尾节点
newNode.pre = temp;
}
@Override
public String toString() {
if(headPointer.next == null) {
return "";
}
Node<T> currentNode = headPointer.next;
StringBuilder sb = new StringBuilder();
while(currentNode != null) {
sb.append(currentNode.toString() + "\n");
currentNode = currentNode.next;
}
sb.delete(sb.lastIndexOf("\n"), sb.length());
return sb.toString();
}
private class Node<T> {
T data;
Node<T> pre;
Node<T> next;
Node() {
data = null;
pre = null;
next = null;
}
Node(T a) {
data = a;
pre = null;
next = null;
}
public String toString() {
return data.toString();
}
}
}
测试代码
需要添加到链表的类
class Emp {
int empno;
String ename;
Emp(int empno, String ename) {
this.empno = empno;
this.ename =ename;
}
@Override
public String toString() {
return "car [empno=" + empno + ", ename=" + ename + "]";
}
}
将上述元素添加到链表
public static void main(String[] args) {
Emp emp1 = new Emp(32, "lrc");
Emp emp2 = new Emp(16, "rwe");
Emp emp3 = new Emp(79, "bcv");
DoubleLinkedList<Emp> dll = new DoubleLinkedList<Emp>();
dll.add(emp1);
dll.add(emp2);
dll.add(emp3);
System.out.println(dll);
}
}
运行结果
双向链表 - 删除节点
代码实现
public void delete(T a) {
// 1. 指代当前遍历到的节点
Node<T> currentNode = headPointer.next;
// 2. 当前遍历的节点不为空
while(currentNode != null) {
// 3.， 一旦遇到 需要删除的节点，结束完以下操作，立即停止遍历
if(currentNode.data.equals(a)) {
// 3.1 需要删除节点的前一个节点的next指针，指向需要删除节点的下一个节点
currentNode.pre.next = currentNode.next;
// 3.2 如果删除节点的后面还有节点则 其下一个节点的pre指针指向 删除节点的前一个节点
if(currentNode.next != null) {
currentNode.next.pre = currentNode.pre;
}
// 3.3 结束循环
break;
}
// 4. 当前节点不符合要求，遍历移动到下一个节点
currentNode = currentNode.next;
}
}
测试代码
public static void main(String[] args) {
Emp emp1 = new Emp(32, "lrc");
Emp emp2 = new Emp(16, "rwe");
Emp emp3 = new Emp(79, "bcv");
DoubleLinkedList<Emp> dll = new DoubleLinkedList<Emp>();
// 添加节点，并打印出来
dll.add(emp1);
dll.add(emp2);
dll.add(emp3);
System.out.println(dll);
System.out.println("\n-------------------\n");
// 删除一个节点，并打印链表存在的节点
dll.delete(new Emp(79,"bcv"));
System.out.println(dll);
}
运行结果
双向链表 - 逻辑有序添加到链表
public void addOrder(T a) {
// 1. 封装添加的元素为数组
Node<T> newNode = new Node<T>(a);
// 判断当前链表是否有有效元素，无，则直接在头指针向后加即可
if (headPointer.next == null) {
headPointer.next = newNode;
newNode.pre = headPointer;
return;
}
// 加一个标志位，看是否有元素添加成功
boolean flag = false;
Node<T> currentNode = headPointer;
while(currentNode.next != null) {
// 代表当前遍历到的元素
currentNode = currentNode.next;
// 如果遍历的元素大于添加的元素，则把添加的元素插入在当前元素前面
if(currentNode.data.hashCode() > newNode.data.hashCode()) {
flag = true;
currentNode.pre.next = newNode;
newNode.next = currentNode;
currentNode.pre = newNode;
newNode.pre = currentNode.pre;
break;
}
}
// 如果整个链表遍历完毕，依然未找到大于添加元素的值，则直接将添加元素放入链表尾部
if(!flag) {
currentNode.next = newNode;
newNode.pre = currentNode;
}
}
测试代码
public static void main(String[] args) {
Emp emp1 = new Emp(32, "lrc");
Emp emp2 = new Emp(16, "rwe");
Emp emp4 = new Emp(16, "rwetfgdg");
Emp emp3 = new Emp(79, "bcv");
DoubleLinkedList<Emp> dll = new DoubleLinkedList<Emp>();
dll.addOrder(emp1);
dll.addOrder(emp2);
dll.addOrder(emp4);
dll.addOrder(emp3);
System.out.println(dll);
}
运行结果
