当前位置 博文首页 > 战丶后风!!的博客:Java数据结构之双向链表概述及实现
package com.hf.structures.linkedlist;
public class EmpNode {
//排名
public int ranking;
//名字
public String name;
//下一个节点
public EmpNode next;
//上一个节点
public EmpNode pre;
public EmpNode(int ranking, String name) {
this.ranking = ranking;
this.name = name;
}
@Override
public String toString() {
return "EmpNode{" +
"ranking=" + ranking +
", name='" + name + '\'' +
'}';
}
}
① 初始化链表头
package com.hf.structures.linkedlist;
public class EmpDoubleLinkedList {
//初始化链表头
private EmpNode head = new EmpNode(0, "");
}
② 判断链接是否为null
private boolean isNull() {
return head.next == null;
}
③ 添加节点(EmpNode)到链表
/**
* 功能描述:
* 〈
* 根据节点排名信息添加到链表
* 1.找到要添加的具体位置
* 2.判断是否是最后一个节点位置
* 3.empNode.next = temp.next;
* 4.temp.next.pre = empNode;
* 5.temp.next = empNode;
* 6.empNode.pre = temp;
* 〉
*
* @className: EmpDoubleLinkedList
* @author: hf
* @version: 1.0.0
* @date: 2019/7/29 15:47
* @param: [empNode]
* @return: void
*/
public void addByOrder(EmpNode empNode) {
EmpNode temp = head;
boolean flag = false;
while (true) {
//链表为null、或链表下一个节点排名>要插入节点排名
if (temp.next == null || temp.next.ranking > empNode.ranking) {
break;
}
//若排名相同
if (temp.next.ranking == empNode.ranking) {
flag = true;
break;
}
//temp后移
temp = temp.next;
}
if (flag) {
System.out.println("节点元素重复....");
} else {
//已至链表末尾
if (temp.next == null) {
temp.next = empNode;
empNode.pre = temp;
return;
}
//置换节点位置
empNode.next = temp.next;
temp.next.pre = empNode;
temp.next = empNode;
empNode.pre = temp;
}
}
/**
* 功能描述:
* 〈
* 添加节点信息到链表
* 1.找到链表末尾的位置
* 2.temp.next=empNode;
* 3.empNode.pre=temp;
* 〉
*
* @className: EmpDoubleLinkedList
* @author: hf
* @version: 1.0.0
* @date: 2019/7/29 15:41
* @param: [empNode]
* @return: void
*/
public void add(EmpNode empNode) {
EmpNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
//追加节点到链表末尾
temp.next = empNode;
empNode.pre = temp;
}
④ 从双链表中删除节点
/**
* 功能描述:
* 〈
* 根据排名删除节点
* 1.找到要删除的节点信息
* 2.temp.pre.next=temp.next;
* 3.temp.next.pre=temp.pre;
* 〉
*
* @className: EmpDoubleLinkedList
* @author: hf
* @version: 1.0.0
* @date: 2019/7/29 15:28
* @param: [raking 排名信息]
* @return: void
*/
public void del(int raking) {
if (isNull()) {
return;
}
EmpNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.ranking == raking) {
flag = true;
break;
}
//链表后移
temp = temp.next;
}
if (flag) {
//置换数据
temp.pre.next = temp.next;
//判断是否删除的是最后一个节点
if (temp.next != null) {
temp.next.pre = temp.pre;
}
}
}
⑤ 修改节点数据
/**
* 功能描述:
* 〈
* 修改节点信息
* 1.找到要修改的节点
* 2.置换节点数据(data域)
* 〉
*
* @className: EmpDoubleLinkedList
* @author: hf
* @version: 1.0.0
* @date: 2019/7/29 15:34
* @param: [empNode 带有新数据信息的节点]
* @return: void
*/
public void upd(EmpNode empNode) {
if (isNull()) {
return;
}
EmpNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
return;
}
if (temp.ranking == empNode.ranking) {
flag = true;
break;
}
//temp后移
temp = temp.next;
}
if (flag) {
//置换data域数据
temp.name = empNode.name;
}
}
⑥ 遍历链表
/**
* 功能描述:
* 〈
* 显示双向链表所有内容信息【也可从链表尾部节点开始遍历】
* 〉
*
* @className: EmpDoubleLinkedList
* @author: hf
* @version: 1.0.0
* @date: 2019/7/29 15:27
* @param: []
* @return: void
*/
public void show() {
if (isNull()) {
return;
}
EmpNode temp = head.next;
while (temp != null) {
System.out.println(temp);
temp = temp.next;
}
}
cs