package Java_Algorithm.LinkList;
import org.junit.Test;
/**
* ClassName: DoubleLinkedList
* Date: 2020/3/16 19:16
* author: Oh_MyBug
* version: V1.0
*
* 管理单向链表的缺点分析:
* 1. 单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找
* 2. 单向链表不能自我删除,需要靠辅助节点,而双向链表可以自我删除,所以在单向链表删除节点时,
* 总是找到temp,temp是待删除节点的前一个节点
*
* 使用带head头的双向链表实现 - RunningMan成员关于时间排序
*/
public class DoubleLinkedList {
@Test
public void test(){
DoubleLinkedList runningMan = new DoubleLinkedList();
runningMan.list();
System.out.println("RunningMan开始啦!");
runningMan.add(new MemberNode1(1, "池石镇","王鼻子"));
runningMan.add(new MemberNode1(2, "刘在石","刘姆斯·邦德"));
runningMan.add(new MemberNode1(3, "金钟国","能力者"));
runningMan.add(new MemberNode1(4, "Gary","狗哥"));
runningMan.add(new MemberNode1(5, "HAHA","时间支配者"));
runningMan.add(new MemberNode1(7, "李光洙","长颈鹿"));
runningMan.add(new MemberNode1(8, "宋仲基","同龄朋友"));
runningMan.list();
System.out.println("智孝加入!");
runningMan.addById(new MemberNode1(6, "宋智孝","懵智孝"));
runningMan.list();
System.out.println("Lizzy加入!");
runningMan.addById(new MemberNode1(11, "Lizzy","RM的维他命"));
runningMan.list();
System.out.println("Lizzy下车");
runningMan.del(11);
runningMan.list();
System.out.println("宋仲基下车");
runningMan.del(8);
runningMan.list();
System.out.println("金钟国信息修改");
runningMan.update(new MemberNode1(3, "金钟国","能力者、斯巴达国斯"));
runningMan.list();
System.out.println("刘在石信息修改");
runningMan.update(new MemberNode1(2, "刘在石","刘姆斯·邦德、蚂蚱"));
runningMan.list();
System.out.println("Gary下车");
runningMan.del(4);
runningMan.list();
System.out.println("全昭旻、梁世灿加入");
runningMan.addById(new MemberNode1(10, "梁世灿","小不点"));
runningMan.addById(new MemberNode1(9, "全昭旻","女版李光洙"));
runningMan.list();
System.out.println("RunningMan要一直健健康康下去");
}
private MemberNode1 head = new MemberNode1(0,null,null);
public MemberNode1 getHead() {
return head;
}
// 遍历双向链表的方法
public void list(){
MemberNode1 h = head;
if (h.getNext() == null){
System.out.println("当前链表为空!");
return;
}
while (h.getNext() != null) {
h = h.getNext();
System.out.println(h.toString());
}
System.out.println();
}
// 添加一个节点到双向链表的最后
public void add(MemberNode1 memberNode){
MemberNode1 h = head;
while (h.getNext() != null) {
h = h.getNext();
}
h.setNext(memberNode);
memberNode.setPre(h);
System.out.println(memberNode.getName() + "添加成功");
}
public void addById(MemberNode1 memberNode) {
MemberNode1 h = head;
while (h.getNext() != null) {
if (h.getNext().getId() < memberNode.getId()) {
h = h.getNext();
continue;
} else if (h.getNext().getId() == memberNode.getId()) {
System.out.println("添加失败,已有该成员!");
return;
}
break;
}
if (h.getNext() == null){
add(memberNode);
return;
}
h.getNext().setPre(memberNode);
memberNode.setNext(h.getNext());
h.setNext(memberNode);
memberNode.setPre(h);
System.out.println(memberNode.getName() + "添加成功");
}
// 修改一个结点的内容,可以看到双向链表的节点内容修改和单项链表一样
public void update(MemberNode1 memberNode){
MemberNode1 h = head;
while (h.getNext() != null) {
if (h.getNext().getId() != memberNode.getId()) {
h = h.getNext();
continue;
} else if (h.getNext().getId() == memberNode.getId()) {
h.getNext().setInfo(memberNode.getInfo());
System.out.println("修改成功");
return;
}
}
System.out.println("修改失败,未找到该成员!");
}
// 从双向链表中删除一个节点
public void del(int id){
MemberNode1 h = head;
while (h.getNext() != null){
h = h.getNext();
if (h.getId() == id)
break;
}
if (h.getNext() == null){
h.getPre().setNext(null);
return;
}
h.getPre().setNext(h.getNext());
h.getNext().setPre(h.getPre());
}
}
class MemberNode1{
private int id;
private String name;
private String info;
private MemberNode1 next;
private MemberNode1 pre;
public MemberNode1(int id, String name, String info) {
this.id = id;
this.name = name;
this.info = info;
this.next = null;
this.pre = null;
}
public MemberNode1(MemberNode1 node) {
this.id = node.id;
this.name = node.name;
this.info = node.info;
this.next = null;
this.pre = null;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getInfo() {
return info;
}
public void setInfo(String info) {
this.info = info;
}
public MemberNode1 getNext() {
return next;
}
public void setNext(MemberNode1 next) {
this.next = next;
}
public MemberNode1 getPre() {
return pre;
}
public void setPre(MemberNode1 pre) {
this.pre = pre;
}
@Override
public String toString() {
return "MemberNode1{" +
"id=" + id +
", name='" + name + '\'' +
", info='" + info + '\'' +
'}';
}
}