Java数据结构与算法——双向链表_java双向链表数据结构

1.简介

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

2.代码案例

首先，我们需要有一个实体类，它对应了双向链表中的每个节点的数据信息。

package com.szh.bidirectional;
 
/**
 *
 */
public class BookNode {
 
    public int id;
    public String name;
    public double price;
    public BookNode prev; //当前节点的前驱节点
    public BookNode next; //当前节点的后继节点
 
    public BookNode(int id, String name, double price) {
        this.id = id;
        this.name = name;
        this.price = price;
    }
 
    @Override
    public String toString() {
        return "BookNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", price=" + price +
                '}';
    }
}

接下来，我们写一个具体对双向链表进行CRUD的操作类。

package com.szh.bidirectional;
 
import com.szh.unidirectional.GoodsNode;
 
/**
 *
 */
public class DualLinkedList {
 
    private BookNode head = new BookNode(0, "", 0.0);
 
    //在双向链表末尾插入节点
    public void addLast(BookNode bookNode) {
        BookNode temp = head; //辅助变量
        while (true) {
            if (temp.next == null) { //此双向链表为空
                break;
            }
            temp = temp.next;
        }
        //末尾节点的后继指针指向要插入的新节点
        temp.next = bookNode;
        //新节点的前驱指针指向原来的末尾节点
        bookNode.prev = temp;
    }
 
    //在双向链表的中间某个位置插入节点
    public void addOrder(BookNode bookNode) {
        BookNode temp = head; //辅助变量
        boolean flag = false; //标记变量
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.next.id > bookNode.id) {
                break;
            } else if (temp.next.id == bookNode.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("已经存在了该商品，不能添加重复元素");
        } else {
            bookNode.next = temp.next;
            temp.next.prev = bookNode;
            temp.next = bookNode;
            bookNode.prev = temp;
        }
    }
 
    //修改双向链表的某个节点
    public void updateNode(BookNode bookNode) {
        //是否是空链表
        if (head.next == null) {
            System.out.println("空链表....");
            return;
        }
        BookNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.id == bookNode.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = bookNode.name;
            temp.price = bookNode.price;
        } else {
            System.out.println("未找到要修改的节点....");
        }
    }
 
    //删除双向链表的某个节点
    public void deleteNode(int id) {
        //是否是空链表
        if (head.next == null) {
            System.out.println("空链表....");
            return;
        }
        BookNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.prev.next = temp.next;
            if (temp.next != null) {
                temp.next.prev = temp.prev;
            }
        } else {
            System.out.println("未找到要删除的节点....");
        }
    }
 
    //遍历单向链表，查看每个节点元素
    public void list() {
        //如果链表为空
        if (head.next == null) {
            System.out.println("链表为空....");
            return;
        }
        BookNode temp = head.next; //辅助变量
        int index = 0;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println("第 " + (++index) + " 个节点元素为：" + temp);
            temp = temp.next;
        }
    }
 
    //统计单向链表中节点的个数
    public int getNodeNum() {
        //如果链表为空
        if (head.next == null) {
            System.out.println("链表为空....");
            return 0;
        }
        BookNode temp = head.next;
        int num = 0;
        while (temp != null) {
            num++;
            temp = temp.next;
        }
        return num;
    }
}

最后是我们的主方法类，我们需要对上面写好的代码功能进行测试。

package com.szh.bidirectional;
 
import com.szh.unidirectional.GoodsNode;
 
/**
 * 双向链表相关操作
 */
public class LinkedTest2 {
    public static void main(String[] args) {
        DualLinkedList dualLinkedList = new DualLinkedList();
 
        BookNode bookNode1 = new BookNode(1, "斗罗大陆", 111.111);
        BookNode bookNode2 = new BookNode(2, "斗破苍穹", 666.666);
        BookNode bookNode3 = new BookNode(3, "盗墓笔记", 999.999);
        BookNode bookNode4 = new BookNode(4, "鬼吹灯", 888.888);
 
        System.out.println("双向链表的插入操作：");
        dualLinkedList.addLast(bookNode1);
        dualLinkedList.addLast(bookNode4);
        dualLinkedList.addOrder(bookNode3);
        dualLinkedList.addOrder(bookNode2);
        dualLinkedList.list();
        System.out.println("此双向链表中共有 " + dualLinkedList.getNodeNum() + " 个节点元素。");
        System.out.println();
 
        System.out.println("双向链表的修改操作：");
        dualLinkedList.updateNode(new BookNode(2, "Java编程思想", 555.555));
        dualLinkedList.list();
        System.out.println("此双向链表中共有 " + dualLinkedList.getNodeNum() + " 个节点元素。");
        System.out.println();
 
        System.out.println("双向链表的删除操作：");
        dualLinkedList.deleteNode(2);
        dualLinkedList.list();
        System.out.println("此双向链表中共有 " + dualLinkedList.getNodeNum() + " 个节点元素。");
    }
}

代码运行结果如下：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/919287