java模拟实现双向链表

作者:小码农叔叔 时间:2022-06-05 09:16:16 

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

下图是双向链表的逻辑结构图,和单链表不同的是,双向链表中每个节点包含两个节点的指针引用,和一个数据域,这两个节点分别指向前一个节点和后一个节点;

双向链表的这种结构比起单链表,其改进之处正在于此,通过对前后节点的引用可以使得在整个链表中,通过给定的值,可以从前或者向后遍历,大大提升了遍历查询的效率,一定程度上解决了单链表的性能问题,但与此同时,链表的存储开销也增大了,我们熟悉的linkedList,其底层就是这个原理实现的.

java模拟实现双向链表

废话不多说,相信通过上面的解释大家已经很明白了,下面直接上代码,可以结合代码和图结构理解双向链表,

public class DoubleLinkTest<T> {

    /**
     * 内部构造节点类
     * 
     * @param <T>
     */
    private class Node<T> {
        private T data;
        private Node next; // 指向下一个节点的引用
        private Node prev; // 指向前一个节点的引用

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head; // 模拟头结点
    private Node<T> last; // 模拟尾部节点
    private Node<T> other; // 暂定一个临时节点,用作指针节点
    private int length;

    public void DoubleLinkTest() {
        head = new Node<T>(null);
        last = head;
        length = 0;
    }

    public void DoubleLinkTest(T data) {
        head = new Node<T>(data);
        last = head;
        length = 0;
    }

    /**
     * 链表是否为空
     * 
     * @return
     */
    public boolean isEmpty() {
        return length == 0;
    }

    /**
     * 普通添加,往链表尾部添加
     * 
     * @param data
     */
    public void add(T data) {
        if (isEmpty()) { // 链表为空,新创建一个链表
            head = new Node<T>(data);
            last = head;
            length++;
        } else {
            other = new Node<T>(data);
            other.prev = last;
            last.next = other; // 将新的节点与原来的尾部节点进行结构上的关联
            last = other; // other将成为最后一个节点
            length++;
        }
    }

    /**
     * 在指定的数据后面添加数据
     * 
     * @param data
     * @param insertData
     */
    public void addAfter(T data, T insertData) {
        other = head;
        while (other != null) { // 我们假定这个head是不为空的。
            if (other.data.equals(data)) {
                Node<T> t = new Node<T>(insertData);
                t.prev = other;
                t.next = other.next;// 对新插入的数据进行一个指向的定义
                other.next = t;

                if (t.next == null) {
                    last = t;
                }
                length++;
            }
            other = other.next;
        }
    }

    /**
     * 删除,删除指定的数据
     * 
     * @param data
     */
    public void remove(T data) {
        other = head;// 我们假定这个head是不为空的。
        while (other != null) {
            if (other.data.equals(data)) {
                other.prev.next = other.next;
                length--;
            }
            other = other.next;
        }

    }

    /**
     * 测试打印数据
     */
    public void printList() {
        other = head;
        for (int i = 0; i < length; i++) {
            System.out.println(other.data + "  ");
            other = other.next;
        }
    }

    public static void main(String[] args) {

        DoubleLinkTest<Integer> link = new DoubleLinkTest<Integer>();
        link.add(1);
        link.add(2);
        link.add(3);
        link.add(5);
        link.add(6);
        link.add(7);
        link.printList();

        System.out.println(" ============== ");

        System.out.println(" ==== 在3后面添加一个数据开始========== ");
        link.addAfter(3, 99);
        link.printList();

        System.out.println(" ==== 在3后面添加一个数据结束========== " + "\r\n");

        System.out.println(" ==== 移除一个数据开始========== ");
        link.remove(99);
        link.printList();
        System.out.println(" \r\n");

    }

}

运行main函数,可以看到控制台的打印输出:

java模拟实现双向链表

来源:https://blog.csdn.net/zhangcongyi420/article/details/88383069

标签:java,双向链表
0
投稿

猜你喜欢

  • Java高并发之CyclicBarrier的用法详解

    2023-11-17 16:27:57
  • 解决CollectionUtils.isNotEmpty()不存在的问题

    2021-11-15 12:03:17
  • Java常用锁synchronized和ReentrantLock的区别

    2023-06-01 04:42:21
  • Android实现单选按钮

    2021-11-20 18:32:53
  • MyBatis的嵌套查询解析

    2023-11-26 16:58:46
  • MyBatis学习教程(五)-实现关联表查询方法详解

    2021-06-23 21:04:04
  • java实现在原有日期时间上加几个月或几天

    2023-08-06 16:39:48
  • java并发编程专题(五)----详解(JUC)ReentrantLock

    2023-12-01 04:04:09
  • 详解C#之事件

    2022-01-07 22:18:14
  • IDEA编译报错:Error:java:无效的源发行版:17的解决办法

    2023-08-25 10:38:06
  • JAVAlogback日志管理详解

    2023-01-11 22:33:54
  • C#反射应用实例

    2023-11-03 14:47:46
  • Android 逆向学习详解及实例

    2022-12-26 08:51:50
  • c++函数转c#函数示例程序分享

    2023-08-13 14:45:26
  • Unity3D使用Shader实现腐蚀消失

    2022-01-07 20:57:59
  • Hibernate hql查询代码实例

    2021-07-24 18:03:33
  • 详解Spring全局异常处理的三种方式

    2023-11-11 15:31:47
  • Android一行代码实现圆形头像

    2022-02-23 02:00:25
  • C#Process的OutputDataReceived事件不触发问题及解决

    2023-08-12 19:22:41
  • 解决SpringBoot自定义拦截器和跨域配置冲突的问题

    2022-01-31 04:59:29
  • asp之家 软件编程 m.aspxhome.com