看动画学算法之Java实现doublyLinkedList

简介:

LinkedList相比,doublyLinkedList中的节点除了next指向下一个节点之外,还有一个prev之前的一个节点。所以被称为doublyLinkedList。 doublyLinkedList是一个双向链表,我们可以向前或者向后遍历list。

今天我们来学习一下doublyLinkedList的基本操作和概念。

1、doublyLinkedList的构建

linkedList一样,doublyLinkedList是由一个一个的节点构成的。而每个节点除了要存储要保存的数据之外,还需要存储下一个节点和上一个节点的引用。

doublyLinkedList需要一个head节点,我们看下怎么构建:

public class DoublyLinkedList {

    Node head; // head 节点

    //Node表示的是Linked list中的节点,包含一个data数据,上一个节点和下一个节点的引用
    class Node {
        int data;
        Node next;
        Node prev;
        //Node的构造函数
        Node(int d) {
            data = d;
        }
    }
}

2、doublyLinkedList的操作

接下来,我们看一下doublyLinkedList的一些基本操作。

2.1 头部插入

头部插入的逻辑是:将新插入的节点作为新的head节点,并且将newNode.next指向原来的head节点。

同时需要将head.prev指向新的插入节点。

看下java代码:

    //插入到linkedList的头部
    public void push(int newData) {
        //构建要插入的节点
        Node newNode = new Node(newData);
        //新节点的next指向现在的head节点
        //新节点的prev指向null
        newNode.next = head;
        newNode.prev = null;

        if (head != null)
            head.prev = newNode;

        //现有的head节点指向新的节点
        head = newNode;
    }

2.2 尾部插入

尾部插入的逻辑是:找到最后一个节点,将最后一个节点的next指向新插入的节点,并且将新插入的节点的prev指向最后一个节点。

 //新节点插入到list最后面
    public void append(int newData) {
        //创建新节点
        Node newNode = new Node(newData);
        //如果list是空,则新节点作为head节点
        if (head == null) {
            newNode.prev = null;
            head = newNode;
            return;
        }

        newNode.next = null;
        //找到最后一个节点
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        //插入
        last.next = newNode;
        newNode.prev = last;
        return;
    }

2.3 插入给定的位置

如果要在给定的位置插入节点,我们需要先找到插入位置的前一个节点,然后将前一个节点的next指向新节点。新节点的prev指向前一个节点。

同时我们需要将新节点的next指向下一个节点,下一个节点的prev指向新的节点。

   //插入在第几个元素之后
    public void insertAfter(int index, int newData) {
        Node prevNode = head;
        for (int i = 1; i < index; i++) {
            if (prevNode == null) {
                System.out.println("输入的index有误,请重新输入");
                return;
            }
            prevNode = prevNode.next;
        }
        //创建新的节点
        Node newNode = new Node(newData);
        //新节点的next指向prevNode的下一个节点
        newNode.next = prevNode.next;
        //将新节点插入在prevNode之后
        prevNode.next = newNode;
        //将新节点的prev指向prevNode
        newNode.prev = prevNode;

        //newNode的下一个节点的prev指向newNode
        if (newNode.next != null)
            newNode.next.prev = newNode;
    }

2.4 删除指定位置的节点

删除节点的逻辑是:找到要删除节点的前一个节点,和下一个节点。前一个节点的next指向下一个节点,下一个节点的prev指向前一个节点。

 //删除特定位置的节点
    void deleteNode(int index)
    {
        // 如果是空的,直接返回
        if (head == null)
            return;

        // head节点
        Node temp = head;

        // 如果是删除head节点
        if (index == 1)
        {
            head = temp.next;
            return;
        }

        // 找到要删除节点的前一个节点
        for (int i=1; temp!=null && i<index-1; i++)
            temp = temp.next;

        // 如果超出范围
        if (temp == null || temp.next == null)
            return;

        // temp->next 是要删除的节点,删除节点
        Node next = temp.next.next;
        temp.next = next;
        Node prev = temp.next.prev;
        prev.prev = prev;
    }

到此这篇关于看动画学算法之Java实现doublyLinkedList的文章就介绍到这了,更多相关Java实现doublyLinkedList内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java 集合框架之List 的使用(附小游戏练习)

    目录 1. List 1.1 List 的常见方法 1.2 代码示例 2. ArrayList 2.1 介绍 2.2 ArrayList 的构造方法 2.3 ArrayList 底层数组的大小 3. LinkedList 3.1 介绍 3.2 LinkedList 的构造方法 4. 练习题 5. 扑克牌小游戏 1. List 1.1 List 的常见方法 1.2 代码示例 注意: 下面的示例都是一份代码分开拿出来的,上下其实是有逻辑关系的 示例一: 用 List 构造一个元素为整形的顺序表 Li

  • Java中list.foreach不能使用字符串拼接的问题

    目录 list.foreach不能使用字符串拼接 如图,不能使用String进行拼接 foreach循环中不能使用字符串拼接 问题 解决 原理    lambda表达式使用局部变量要用final list.foreach不能使用字符串拼接 如图,不能使用String进行拼接 因为Lambda的本质实际上是匿名内部类,所以t必须是final类型(不过代码中的final可以省略),是不可以重新赋值的. 可以使用 final StringBuilder str = new StringBuilder(

  • 浅析java中asList的使用详解

    asList概述 Java中的asList方法是数组工具类 Arrays中的一个静态方法,Arrays.asList()方法的作用是将数组或一些元素转为集合,asList方法返回值得到的集合并不是我们通常使用的List集合,asList()方法把数组转换成集合时,不能使用其修改集合相关的方法,如果使用修改集合相关的方法add/remove/clear方法会抛出java.lang.UnsupportedOperationException的异常. 1.使用asList方法返回的对象调用add/re

  • Java关于List集合去重方案详细介绍

    1 常规去重 碰到List去重的问题,除了遍历去重,我们常常想到利用Set集合不允许重复元素的特点,通过List和Set互转,来去掉重复元素. // 遍历后判断赋给另一个List集合,保持原来顺序 public static void ridRepeat1(List<String> list) { System.out.println("list = [" + list + "]"); List<String> listNew = new A

  • Java与Scala创建List与Map的实现方式

    目录 Java与Scala创建List与Map Java自定义map与scala map对比 1. 背景 2. java代码 Java与Scala创建List与Map //Java List<String> languages = new ArrayList<>(); Map<String, Class> mapFields = new HashMap(); //Scala val languages = new util.ArrayList[String] val m

  • Java中的ArrayList容量及扩容方式

    目录 查看JDK1.8 ArrayList的源代码 1.默认初始容量为10 2.最大容量为 Integer.MAX_VALUE - 8 3.扩容方式: Java ArrayList() 扩容原理 先看下 ArrayList 的属性以及构造方法,这个比较重要 上看说的是初始化场景,下面看一下其他场景,也是相当简单 结论 查看JDK1.8 ArrayList的源代码 1.默认初始容量为10 /** * Default initial capacity. */ private static final

  • Java实现单链表SingleLinkedList增删改查及反转 逆序等

    节点类 可以根据需要,对节点属性进行修改.注意重写toString()方法,以便后续的输出操作. //节点类 class Node { public int id; public String name; public Node next; public Node(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Node{" + &

  • Java泛型模拟scala实现自定义ArrayList方式

    目录 泛型模拟scala实现自定义ArrayList 自定义实现ArrayList代码 泛型模拟scala实现自定义ArrayList 泛型就是将类型由原来的具体的类型参数化,类似于方法中的变量参数,此时类型也定义成参数形式(可以称之为类型形参), 然后在使用/调用时传入具体的类型 操作的数据类型被指定为一个参数,这种参数类型可以用在类.接口和方法中,分别被称为泛型类.泛型接口.泛型方法. 以下实例通过泛型,灵活的实现了类似scala中集合的map,reduce方法,并可以链式编程 Functi

  • 看动画学算法之Java实现doublyLinkedList

    简介: 和LinkedList相比,doublyLinkedList中的节点除了next指向下一个节点之外,还有一个prev之前的一个节点.所以被称为doublyLinkedList. doublyLinkedList是一个双向链表,我们可以向前或者向后遍历list. 今天我们来学习一下doublyLinkedList的基本操作和概念. 1.doublyLinkedList的构建 和linkedList一样,doublyLinkedList是由一个一个的节点构成的.而每个节点除了要存储要保存的数

  • 新手小白看过来学JAVA必过IO流File字节流字符流

    目录 IO简介 1.流Stream 2.IO流的继承结构 3 File文件类 3.1概述 3.2创建对象 3.3常用方法 3.4 练习:测试常用方法 4.字节流读取 4.1 InputStream抽象类 4.2 FileInputStream子类 4.3 BufferedInputStream子类 4.4 练习:字节流读取案例 5.字符流读取 5.1 Reader抽象类 5.2 FileReader子类 5.3 BufferedReader子类 5.4 练习:字符流读取案例 6.字节流写出 6.

  • 浅析从同步原语看非阻塞同步以及Java中的应用

    一.从硬件原语上理解同步(非特指Java) 同步机制是多处理机系统的重要组成部分,其实现方式除了关系到计算的正确性之外还有效率的问题.同步机制的实现通常是在硬件提供的同步指令的基础上,在通过用户级别软件例程实现的.上面说到的乐观策略实际上就是建立在硬件指令集的基础上的(我们需要实际操作和冲突检测是原子性的),一般有下面的常用指令:测试并设置(test_and_set).获取并增加(fetch_and_increment).原子交换(Atomic_Exchange).比较并交换(CAS).加载连接

  • FP-Growth算法的Java实现+具体实现思路+代码

    FP-Growth算法原理 其他大佬的讲解 FP-Growth算法详解 FP-Growth算法的Java实现 这篇文章重点讲一下实现.如果看了上述给的讲解,可知,需要两次扫描来构建FP树 第一次扫描 第一次扫描,过滤掉所有不满足最小支持度的项:对于满足最小支持度的项,按照全局支持度降序排序. 按照这个需求,可能的难点为如何按照全局支持度对每个事务中的item排序.我的实现思路 扫描原数据集将其保存在二维列表sourceData中 维护一个Table,使其保存每个item的全局支持度TotalSu

  • 排序算法的Java实现全攻略

    Collections.sort() Java的排序可以用Collections.sort() 排序函数实现. 用Collections.sort方法对list排序有两种方法: 第一种是list中的对象实现Comparable接口,如下: /** * 根据order对User排序 */ public class User implements Comparable<User>{ private String name; private Integer order; public String

  • 三种简单排序算法(使用java实现)

    一.冒泡排序 算法思想:遍历待排序的数组,每次遍历比较相邻的两个元素,如果他们的排列顺序错误就交换他们的位置,经过一趟排序后,最大的元素会浮置数组的末端.重复操 作,直到排序完成. 示例演示: 算法实现: for(int i=0;i<array.length-1;i++){//最多排序n-1次 for(int j=0;j<array.length-i-1;j++){//需要交换的次数 if(array[j]>array[j+1]){ int temp=array[j]; array[j]

  • K均值聚类算法的Java版实现代码示例

    1.简介 K均值聚类算法是先随机选取K个对象作为初始的聚类中心.然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心.聚类中心以及分配给它们的对象就代表一个聚类.一旦全部对象都被分配了,每个聚类的聚类中心会根据聚类中现有的对象被重新计算.这个过程将不断重复直到满足某个终止条件.终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小. 2.什么是聚类 聚类是一个将数据集中在某些方面相似的数据成员进行分类组织

  • 快速排序算法在Java中的实现

    快速排序的原理:选择一个关键值作为基准值.比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的).一般选择序列的第一个元素. 一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换.找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换.直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两

  • JavaScript前端学算法题解LeetCode最大重复子字符串

    目录 最大重复子字符串 解题思路 知识点 这是LeetCode的第1668题:最大重复子字符串 最大重复子字符串 给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word 的 重复值为 k .单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值.如果 word 不是 sequence 的子串,那么重复值 k 为 0 .给你一个字符串 sequence 和 word ,请你返回

  • 详解Huffman编码算法之Java实现

    Huffman编码介绍 Huffman编码处理的是字符以及字符对应的二进制的编码配对问题,分为编码和解码,目的是压缩字符对应的二进制数据长度.我们知道字符存贮和传输的时候都是二进制的(计算机只认识0/1),那么就有字符与二进制之间的mapping关系.字符属于字符集(Charset), 字符需要通过编码(encode)为二进制进行存贮和传输,显示的时候需要解码(decode)回字符,字符集与编码方法是一对多关系(Unicode可以用UTF-8,UTF-16等编码).理解了字符集,编码以及解码,满

随机推荐