带头节点的双向链表

模拟结点

//模拟双向链表的结点
public class DoubleNode {
    //data域中的数据
    public int id;
    public String name;
    public int price;
    //上一个结点（直接前驱）
    public DoubleNode pre;
    //下一个结点（直接后继）
    public DoubleNode next;

    public DoubleNode(int id, String name, int price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "DoubleNode{id=" + id + ", name=‘" + name + '’' + ", price=" + price + '}';
    }
}

双向链表的增删改查

public class DoubleLinkList {
    //头结点
    private DoubleNode headNode = new DoubleNode(0,"",0);

    /** * 在双向链表尾部添加结点 */
    public void addEnd(DoubleNode newNode){
        DoubleNode temp = headNode;
        while(true){
            if (temp.next == null) {
                //链表的尾部
                temp.next = newNode;
                newNode.pre = temp;
                return;
            }
            temp = temp.next;
        }
    }

    /** * 根据id值添加结点 */
    public void addById(DoubleNode newNode){
        if (headNode.next == null){
            //当前链表为空
            headNode.next=newNode;
            return;
        }
        DoubleNode temp = headNode;
        while(true){
            if(temp.id > newNode.id){
                if (temp.pre==null){
                    //如果目标结点在双向链表的首位，由于第一个结点的pre为null，不这么写或报空指针异常
                    headNode.next=newNode;
                    newNode.next=temp;
                    temp.pre=newNode;
                }else {
                    //在双向链表的中间位置
                    newNode.pre=temp.pre;
                    newNode.next=temp;
                    temp.pre.next=newNode;
                    temp.pre=newNode;
                }
                return;
            }
            if (temp.next == null){
                //目标结点在链表的末尾
                temp.next=newNode;
                newNode.pre=temp;
                return;
            }if (temp.id == newNode.id){
                System.out.println("id重复无法插入");
                return;
            }
            temp = temp.next;
        }
    }

    /** * 根据id值修改结点 */
    public void update(DoubleNode newNode){
        if (headNode.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        DoubleNode temp = headNode.next;
        while (true){
            if (temp.id == newNode.id) {
                //找到目标结点
                temp.name = newNode.name;
                temp.price = newNode.price;
                return;
            }
            /*把这个if放在后面 如果放在前面会导致最后一个结点的数据无法修改 原因是因为当遍历到最后一个结点的时候最后一个结点的next为null程序 就会进入这个if判断中然后跳出整个循环*/
            if (temp.next == null) {
                //遍历完整个链表都没有找到目标结点
                System.out.println("未找到要修改的结点");
                return;
            }
            temp = temp.next;
        }
    }
    /** * 根据id删除结点 */
    public void delete(int id){
        if (headNode.next == null) {
            System.out.println("当前链表为空，无法删除结点");
            return;
        }
        DoubleNode temp = headNode.next;
        boolean isFind = false;
        while (true){
            if (temp.next == null) {
                //遍历完整个链表都没有找到目标结点
                System.out.println("没有找到目标结点");
                return;
            }
            if (temp.id == id) {
                //找到目标结点
                //删除结点
                temp.pre.next = temp.next;
                if (temp.next != null){
                    //当前结点不是最后一个结点
                    temp.next.pre = temp.pre;
                }
                temp.pre = null;
                temp.next = null;
                return;
            }
            temp = temp.next;
        }
    }
    /** * 遍历双向链表 */
    public void show(){
        if (headNode.next == null){
            System.out.println("当前双向链表为空");
            return;
        }
        DoubleNode temp = headNode;
        while(true){
            if (temp.next==null) {
                return;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }
}

测试

public class DoubleLinkTest {
    public static void main(String[] args) {
        DoubleNode doubleNode1 = new DoubleNode(1,"三国演义",100);
        DoubleNode doubleNode2 = new DoubleNode(2,"水浒传",100);
        DoubleNode doubleNode3 = new DoubleNode(3,"西游记",100);
        DoubleNode doubleNode4 = new DoubleNode(4,"红楼梦",100);
        DoubleNode doubleNode5 = new DoubleNode(5,"山海经",100);
        DoubleNode doubleNode6 = new DoubleNode(6,"史记",100);
        DoubleNode doubleNode7 = new DoubleNode(7,"资治通鉴",100);
        DoubleNode doubleNode8 = new DoubleNode(8,"儒林外史",100);
        DoubleLinkList list = new DoubleLinkList();
        list.addById(doubleNode1);
        list.addById(doubleNode4);
        list.addById(doubleNode2);
        list.addById(doubleNode3);
        list.addEnd(doubleNode5);
        list.addEnd(doubleNode6);
        list.addEnd(doubleNode7);
        list.addEnd(doubleNode8);
        //list.delete(3);
        list.update(new DoubleNode(8,"test",100));
        list.show();
    }
}