Java-双向链表-从实现到各类操作（全家桶，包含各类常见方法）

package com.lixunhuan.linkedlist;

public class DoubleLinkedListDemo {
public static void main(String[] args) {
    HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
    HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
    HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
    HeroNode2 hero4 = new HeroNode2(4, "公孙胜", "入云龙");

    DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
    doubleLinkedList.add(hero1);
    doubleLinkedList.add(hero2);
    doubleLinkedList.add(hero3);
    doubleLinkedList.add(hero4);
    doubleLinkedList.list();
    System.out.println(doubleLinkedList.getLength(doubleLinkedList.getHead()));
    System.out.println("+++++++++++++分隔符+++++++++++++++");
    doubleLinkedList.delete(1);
    doubleLinkedList.list();
    System.out.println(doubleLinkedList.getLength(doubleLinkedList.getHead()));

    //测试按序插入双向链表
    System.out.println("+++++++++++++++++++测试按序插入双向链表++++++++++++++++++++");
    DoubleLinkedList doubleLinkedList2 = new DoubleLinkedList();
    doubleLinkedList2.addByOrder(new HeroNode2(3, "吴用", "智多星"));
    doubleLinkedList2.addByOrder(new HeroNode2(2, "卢俊义", "玉麒麟"));
    doubleLinkedList2.addByOrder(new HeroNode2(1, "宋江", "及时雨"));
    doubleLinkedList2.addByOrder(new HeroNode2(4, "公孙胜", "入云龙"));
    doubleLinkedList2.list();
}
}

class DoubleLinkedList {
//初始化，创建表头
private HeroNode2 head = new HeroNode2(0, null, null);

//返回头节点
public HeroNode2 getHead() {
    return head;
}

//遍历双向链表的方法
public void list() {
    if (head.next == null) {
        System.out.println("链表为空!");
    } else {
        //因为头节点不能动，所以我们需要一个辅助遍历来遍历链表
        HeroNode2 temp = head.next;//这次遍历的时候可不需要头节点了，因为头节点不存有效数据
        while (temp != null) {
            System.out.println(temp);//即调用了重写的System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}

//双向链表增加节点的方法（默认增加至尾部）,对单向链表程序要略微修改(前后指针都有，不止一个方向赋值)
public void add(HeroNode2 heroNode) {
    //因为头节点不能动，所以我们需要一个辅助遍历来遍历链表找到最后节点
    HeroNode2 temp = head;
    //while循环用来找到当前链表的尾部
    while (temp.next != null) {
        temp = temp.next;
    }
    //是最后节点指向新增节点
    temp.next = heroNode;
    heroNode.pre = temp;
}

//双向链表删除节点的方法，需要对单向链表进行程序进行修改
public void delete(int no) {
    //1)判断链表是否为空
    if (head.next == null) {
        System.out.println("是空链表，无英雄");
        return;
    }
    //2）创建临时指针进行链表的遍历、查找
    HeroNode2 temp = head.next;
    boolean flag = false;//用于记录是否已找到指定英雄
    while (temp != null) {
        if (temp.no == no) {
            flag = true;//表示找到了
            break;
        } else {
            temp = temp.next;
        }
    }
    if (flag) {
        temp.pre.next = temp.next;
        //如果最后一个节点，则不需要执行下面这句话
        if (temp.next != null)
            temp.next.pre = temp.pre;
    } else {
        System.out.printf("未找到编号为：%d节点!\n", no);
    }
}

//双向链表中有效节点数目的查询
public int getLength(HeroNode2 head) {
    if (head.next == null || head == null) {
        return 0;
    }
    int length = 0;
    HeroNode2 cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

/**
 * 按序增加节点的方法
 * 按108将的 no将号进行排序服务
 * 排序次序：升序：1234
 */
public void addByOrder(HeroNode2 newNode) {
    if (newNode == null) {
        System.out.println("请输入正确的节点");
        return;
    }
    if (head.next == null) {
        head.next = newNode;
        newNode.pre=head;
    } else {
        HeroNode2 curNode = head.next;
        while (curNode != null) {
            if (curNode.no < newNode.no) {
                curNode = curNode.next;
            } else if (curNode.no == newNode.no) {
                System.out.printf("节点序号为：%d重复，无法重复添加\n", newNode.no);
                return;
            } else {
                break;
            }
        }
        if (curNode == null) {
            this.add(newNode);
        } else {
            newNode.next = curNode;
            newNode.pre =curNode.pre;
            curNode.pre.next=newNode;
            curNode.pre=newNode;
        }
    }

}
}

/**
 * 创建双向链表节点
 */
class HeroNode2 {
public int no;
public String name;
public String nickname;
public HeroNode2 next;//指向下一个节点
public HeroNode2 pre;//指向上一个节点

//构造器，注意单向链表新增节点的时候，其是不知道下一个节点的指向的，要么不管，要么赋值null

public HeroNode2(int no, String name, String nickname) {
    this.no = no;
    this.name = name;
    this.nickname = nickname;
    this.next = null;
    this.pre = null;
}

@Override
public String toString() {
    return "HeroNode2{" +
            "no=" + no +
            ", name='" + name + '\'' +
            ", nickname='" + nickname + '\'' +
            '}';
}
}