Java | 双向链表

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 + '\'' +
                '}';
    }
}

上一篇:java学习 使用循环链表解决约瑟夫问题


下一篇:在CentOS下搭建ftp服务器遇到的一些问题