精华内容
下载资源
问答
  • 学过java同学,都知道java把内存分为两种形式,一种栈内存,另一种堆内存。java的基本类型(int,short,long,byte,float,double,boolean,char)在栈区分配空间,所有对象都在堆Heap中分配空间。我们按照这思路...

    这也是个老生常谈的问题,最近得空也开始总结下这方面的知识点。学过java的同学,都知道java把内存分为两种形式,一种是栈内存,另一种是堆内存。java的基本类型(int,short,long,byte,float,double,boolean,char)在栈区分配空间,所有的对象都在堆Heap中分配空间。我们按照这思路来谈下JavaScript。

    相信看过我以前博客的朋友也知道,我以前也说过JavaSctipt 语言类型和类型检测的一些知识点,想再了解的朋友也可以点进去看下。JavaSctipt 语言类型和类型检测

    在此之前,我先额外的补充下类型和存储结构的一些相干知识点

    内置类型

    JavaScript目前有八种内置类型(包含ES6的symbol):

    null

    undefined

    string

    number

    boolean

    object

    symbol

    BigInt

    解释下typeof null 为 'object'的bug

    JavaScript中的数据在底层是以二进制存储,比如null所有存储值都是0,但是底层的判断机制,只要前三位为0,就会判定为object,所以才会有typeof null === 'object'这个bug。

    基本包装类型

    string

    number

    boolean

    自动创建的基本包装类型的对象,非Boolean,Number, String内置函数new出来的,对象只存在代码的执行瞬间。所有有些面试题也会问到String(1)和new String(1)的区别。

    typeof返回值表明的类型

    任何一个JavaScript的标识、常量、变量和参数都只是undefined, null, bool, number, string, symbol,object, function类型中的一种(补充下bigint)

    言归正传,我们来介绍下语言中所有的底层存储方式是是什么。

    数组(Array)

    数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构,在各种编程语言中都有对应。一个数组可以分解为多个数组元素,按照数据元素的类型,数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。

    栈( Stack)

    栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据,也就是说,先插入的数据将被压入栈底,最后插入的数据在栈顶,读出数据时,从栈顶开始逐个读出。栈在汇编语言程序中,经常用于重要数据的现场保护。栈中没有数据时,称为空栈。

    队列(Queue)

    队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作。一般来说,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。队列中没有元素时,称为空队列

    链表( Linked List)

    链表是一种数据元素按照链式存储结构进行存储的数据结构,这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成,每个数据结点包括数据域和指针域两部分。其中,指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。

    树( Tree)

    树是典型的非线性结构,它是包括,2个结点的有穷集合K。在树结构中,有且仅有一个根结点,该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点,而且可以有两个后继结点,m≥0

    图(Graph)

    图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对。如果两个顶点之间存在一条边,那么就表示这两个顶点具有相邻关系

    堆(Heap)

    堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的,并且根结点的两个子树也是一个堆结构

    散列表(Hash)

    散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录

    JavaScript使用的是 堆(Heap) 和 栈( Stack)

    JavaScript基本类型数据都是直接按值存储在栈中的(Undefined、Null、不是new出来的布尔、数字和字符串),每种类型的数据占用的内存空间的大小是确定的,并由系统自动分配和自动释放。这样带来的好处就是,内存可以及时得到回收,相对于堆来说 ,更加容易管理内存空间。

    JavaScript引用类型数据被存储于堆中 (如对象、数组、函数等,它们是通过拷贝和new出来的)。其实,说存储于堆中,也不太准确,因为,引用类型的数据的地址指针是存储于栈中的,当我们想要访问引用类型的值的时候,需要先从栈中获得对象的地址指针,然后,在通过地址指针找到堆中的所需要的数据。

    展开全文
  • 我们平时用的较多的一个数据结构,它的特点先进后出,可以做括号匹配,撤销功能等,栈可以用两种基本的数据结构实现 链式栈 实现代码: package com.tangbaobao.stack; import ...

    什么是栈

    栈是我们平时用的较多的一个数据结构,它的特点是先进后出,可以做括号匹配,撤销功能等,栈可以用两种最基本的数据结构实现

    链式栈

    这里写图片描述
    实现代码:

    package com.tangbaobao.stack;
    
    import com.tangbaobao.util.Node;
    
    /**
     * @author 唐学俊
     * @create 2018/03/29
     * 链式栈
     **/
    
    public class MyStack2 {
         int top;
        private int bottom;
        private Node lastNode = null;
        private Node newNode = null;
    
        /**
         * 入栈
         *
         * @param e
         */
        public void push(int e) {
            newNode = new Node();
            newNode.setValue(e);
            if (lastNode == null) {
                //第一个节点
                lastNode = newNode;
            } else {
                //不是第一个节点
                newNode.setNextNode(lastNode);
                //记录当前节点,给下次插入使用
                lastNode = newNode;
            }
            top++;
        }
    
        /**
         * 出栈
         *
         * @return
         */
        public int pop() {
            if (top - bottom <= 0) {
                try {
                    throw new Exception("没有啦");
                } catch (Exception e) {
                    e.printStackTrace();
                }
            } else {
                top --;
                Node temp = newNode;
                newNode = newNode.getNextNode();
                return temp.getValue();
            }
            return -1;
        }
    
    }
    

    栈中依赖的链表数据结构

    package com.tangbaobao.util;
    
    /**
     * 链表的数据结构
     *
     * @author 唐学俊
     * @create 2018/03/29
     **/
    
    public class Node {
        private Node nextNode;
        private int value;
    
        public Node getNextNode() {
            return nextNode;
        }
    
        public void setNextNode(Node nextNode) {
            this.nextNode = nextNode;
        }
    
        public int getValue() {
            return value;
        }
    
        public void setValue(int value) {
            this.value = value;
        }
    }
    

    顺序栈

    用数组作为底层数据结构,入栈按照顺序从0–>n.出栈从n–>1出栈
    这里写图片描述
    代码实现

    package com.tangbaobao.stack;
    
    
    /**
     * 顺序栈
     *
     * @author 唐学俊
     * @create 2018/03/29
     **/
    
    public class MyStack {
        private int top;
        private int bottom;
        private int[] stackData;
    
    
        /**
         * 初始化一个容量为stackzize的栈
         */
        public MyStack(int capacity) {
            stackData = new int[capacity];
            top = 0;
            bottom = 0;
        }
    
    
        /**
         * 入栈
         *
         * @param e
         */
        public void push(int e) {
            //检查栈是否满了
            if (top - bottom > stackData.length-1) {
                try {
                    throw new Exception("栈已经满了");
                } catch (Exception e1) {
                    e1.printStackTrace();
                }
            } else {
                //入栈
                stackData[top++] = e;
            }
        }
    
        /**
         * 出栈
         *
         * @return
         */
        public int pop() {
            //检查栈是否空了
            if (top - bottom == 0) {
                try {
                    throw new Exception("栈里面没元素了");
                } catch (Exception e1) {
                    e1.printStackTrace();
                }
            } else {
                return stackData[--top];
            }
            return -1;
        }
    }
    
    展开全文
  • 数据结构是由数据和结构组成,数据是描述客观事物符号,能够被计算机识别一组符号,如包含有(整型、浮点、布尔、字符、声音、视频、图像等二进制数据); 什么叫二进制(由0和1组成数串)数据呢?二进制是...

    一、什么是数据结构

    数据结构是由数据结构组成,数据是描述客观事物的一种符号,能够被计算机识别的一组符号,如包含有(整型、浮点、布尔、字符、声音、视频、图像等二进制数据);

    什么叫二进制(由0和1组成的数串)数据呢?二进制是计算技术中广泛采用的一种数制二进制数据是用01两个数码来表示的数。它的基数为2,进位规则是逢二进一,借位规则是借一当二,由18世纪德国数理哲学大师莱布尼兹发现。当前的计算机系统使用的基本上是二进制系统,数据在计算机中主要是以补码的形式存储的。计算机中的二进制则是一个非常微小的开关,用来表示1来表示0

      说完了数据,那么结构是什么呢?简单概述就是一组或多组数据之间的任一组合关系,我们叫这种关系的表达方式为结构;不好理解,我们举个例子:如计算机由(cpu+内存+硬盘等)组成,我们把计算机中的各个部件看成数据,他们之间互相连接起来,通过什么方式连接起来的这种关系我们就叫做结构;

     

    综上所述,我们要编写好一个程序,首先需要分析待处理对象的特征(数据)及各个特征之间的关系(结构),这就是我们学习数据结构的目的。

     

    二、数据结构分为逻辑结构和物理结构

    根据不同的视觉看问题,我们把数据结构分类为逻辑结构物理结构

    逻辑结构是指数据对象中数据之间的相互关系表现;根据各个关系表达行为我们又可以分为以下四种表达方式:

    1)、集合结构

    数据元素同属于一个集合,并且没有和其他元素产生关联;各个元素之间是平等关系;他们之间的关系图如数学中集合,如下图:

     

    2)、线性结构

    数据元素之间是一对一的关系,就像我们小朋友排队手牵手的关系一样;你牵我,我牵他 巴拉巴拉;如下图:

    3)、树形结构

    指数据元素之间存在一对多的关系情况,如下图:

    4)、网状结构(又称图形结构)

    指数据元素之间存在多对多的关系情况,如下图:

     

    物理结构

    说完了逻辑结构,现在来说说物理结构,物理结构概念很简单,就是指逻辑结构在计算机中的一种存储方式;实际上是就是让数据元素怎么在计算机存储器里存储的问题;这里说的存储器实际就是我们常见的内存。

     

    数据的存储结构直接反应了数据的逻辑关系,应该怎样采用什么样的逻辑关系是数据存储结构(物理结构)的难点也是重点。

     

    数据存储结构这里有分两种(顺序存储、链式存储)

    顺序存储结构:

    这种存储结构其实很简单,就是排队占位,就好比我们排队买票一样;按先后顺序排列一排购买票。

    链式存储结构:

        由于我们不可能完全像顺序存储结构那样守规矩,实践情况很复杂,比如有人插队、有人中途离开了,位置留出来了怎么办了?还是按照顺序存储结构肯定就不能实现了;这里就会请出链式存储结构,数据元素存储任何的存储单元,存储在哪里不清楚,这组存储单元可以是连续的或非连续的;数据元素的存储关系并不能反应出逻辑关系,因此需要一个标示(指针)来存放数据;所以我们就可以通过指针找到具体的数据,并不用关心数据具体在哪里!

     

    总结,从上文中我们介绍了数据、数据结构、数据结构分为(逻辑结构、物理结构)初步认识到数据结构具体是什么,对我们写程序有什么好处;逻辑结构是面向问题的解决方案;而物理结构是面向计算机而言的;其最终目标是将数据与逻辑关系存储在计算机内存里;

    展开全文
  • 链表(linked list)在物理上非连续、非顺序的数据结构,由若干个节点(node)所组成。 链表分为单向链表和双向链表。 单向链表的每一个节点包含部分,一部分存放数据的变量data,另一部分指向下一个...

    什么是链表?

    链表(linked list)是一种在物理上非连续、非顺序的数据结构,由若干个节点(node)所组成。

    链表分为单向链表和双向链表。

    • 单向链表的每一个节点包含两部分,一部分是存放数据的变量data,另一部分是指向下一个节点的指针next。

    • 双向链表比单向链表复杂一些,它的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev指针。

    如果说数组在内存中的存储方式为顺序存储,那么链表在内存在的存储方式则是随机存储。

    什么是随机存储?

    数组在内存中占用了连续完整的存储空间。而链表则采用见缝插针的方式,链表的每一个节点分布在内存空间中的不同位置,依靠指针关联起来,这样可以灵活有效地利用零散的碎片空间。

    链表的组成

    本篇文章中的链表均以单链表的Demo,在文章的末尾处会附带双向链表的实现代码。

    • 节点:一个链表是有若干个结点组成的,节点是链表的基础结构。

    • 头节点指针:链表需要一个头节点指针,用于表示链表开始的位置。

    • 尾结点指针:链表可以设置一个尾部节点指针。

      当然,链表的尾部节点指针不是必须的,因为链表最后一个节点的next指针指向空,也可以标识链表的结尾。

    • 链表实际长度:可以设置一个变量记录链表的实际长度。

    public class LinkedList {
    
        /**
         * 链表的头指针
         */
        private Node head;
    
        /**
         * 链表的尾部指针
         */
        private Node last;
    
        /**
         * 链表的实际长度
         */
        private int size;
    
        /**
         * 获取链表的头指针
         *
         * @return 链表的头指针
         */
        public Node head() {
            return this.head;
        }
    
        /**
         * 获取链表的尾部指针
         *
         * @return 链表的尾部指针
         */
        public Node last() {
            return this.last;
        }
    
        /**
         * 获取链表的实际长度
         *
         * @return 链表的实际长度
         */
        public int size() {
            return this.size;
        }
    
        /**
         * 将节点点作为链表的一个内部类
         */
        class Node {
            // 节点存储的数据data
            private int data;
            // 该指针指向下一个节点的指针next
            private Node next;
    
            // 构造函数
            Node(int data) {
                this.data = data;
            }
    
            /**
             * 返回节点中存储的数据值
             *
             * @return 节点中存储的数据值
             */
            public int data() {
                return this.data;
            }
    
            /**
             * 返回下一个节点的指针
             *
             * @return 下一个节点的指针
             */
            public Node next() {
                return this.next;
            }
        }
    }
    

    链表的基本操作

    和数组一样,链表的基本操作也同样是增、删、改、查四种操作。

    链表查找元素不像数组那样可以通过下标进行随机访问,链表想要查找一个元素,只能从头节点开始,一个一个向后查找。

    /**
     * 链表的查找操作
     *
     * @param index 需要查找的链表索引
     * @return 索引对应的链表节点
     */
    public Node get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 找到链表的头节点的位置
        Node temp = this.head;
        // 从头节点向后查找,共向后循环index次,即可找到index位置的节点
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }
    

    链表的更新操作也比较简单,只需要查找到需要修改的节点,直接将原节点的数据替换即可。

    /**
     * 更新链表节点
     *
     * @param index 需要更新的链表位置
     * @param data  需要更新的节点的值
     */
    public void update(int index, int data) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 找到链表的头节点的位置
        Node temp = this.head;
        // 从头节点向后查找,共向后循环index次,即可找到index位置的节点
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        // 使用需要替换的值,替换原值
        temp.data = data;
    }
    

    链表的插入操作分为三组:

    • 尾部插入

      链表的尾部操作最为简单,只需要将链表的尾部节点的next指针,指向新结点即可。
      如果有尾部节点指针,则还需要维护链表尾部节点指针,将其指向新节点。

    • 中间插入

      链表的中间插入,分为三步:
      第一步:找到要插入的链表位置。
      第二步:将新结点的next指针指向插入位置的节点。
      第三步:将原插入位置的节点的上一个节点的next指针指向新节点。

    • 头部插入

      链表的头部插入,分为三步:
      第一步:将新节点的next指针指向新节点。
      第二步:维护链表的头部节点指针,将其指向新节点。

    链表的插入操作与数组的插入操作有些许不同,就在于链表不会出现容量不足的情况,无需进行扩容操作。

    /**
     * 直接在尾部插入
     *
     * @param data 需要插入的数据
     */
    public void insert(int data) {
        insert(size, data);
    }
    
    /**
     * 直接在尾部插入
     *
     * @param index 需要插入的链表位置
     * @param data  需要插入的数据
     */
    public void insert(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        // 将需要插入的数据封装为一个链表节点
        Node insertNode = new Node(data);
        // 链表节点为空的情况
        if (size == 0) {
            // 维护链表头部节点指针
            this.head = insertNode;
            // 维护链表尾部节点指针
            this.last = insertNode;
        } else if (index == 0) {
            // 头部插入
            // 使用新节点的next指针指向头部节点
            insertNode.next = this.head;
            // 维护链表头部节点的指针
            this.head = insertNode;
        } else if (index == size) {
            // 尾部插入
            // 直接使用尾部节点指针指向新结点
            this.last.next = insertNode;
            // 维护链表尾部节点的指针
            this.last = insertNode;
        } else {
            // 获取插入位置的前一个节点
            Node prevNode = get(index - 1);
            // 将新节点的next指针指向插入位置节点
            insertNode.next = prevNode.next;
            // 插入位置的前一个节点的next指针指向新节点
            prevNode.next = insertNode;
        }
        // 维护链表长度
        size++;
    }
    

    链表的删除操作和插入操作类似。

    • 删除头部节点

      删除头部节点,只需要将链表的head指针指向原head节点的下一个节点即可。

    • 删除中间节点

      删除中间节点,删除位置的前一个节点的next指针指向删除位置的下一个节点即可。

    • 删除尾部节点

      删除尾部节点,将尾部节点的前一个节点的next指针置空,并维护last指针即可。

    /**
     * 删除链表的结点
     *
     * @param index 需要删除的位置
     * @return 被删除的节点
     */
    public Node remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出链表的实际节点范围");
        }
        Node removeNode = null;
        // 头部删除
        if (index == 0) {
            removeNode = this.head;
            // 维护链表的头部指针
            this.head = removeNode.next;
        } else if (index == size - 1) {
            // 尾部删除
            // 获取尾部的前一个节点
            Node prevNode = get(index - 1);
            removeNode = prevNode.next;
            // 置空尾部的前一个节点的next指针
            prevNode.next = null;
            // 维护链表的尾部指针
            this.last = prevNode;
        } else {
            // 获取插入位置的前一个节点
            Node prevNode = get(index - 1);
            // 需要删除的节点
            removeNode = prevNode.next;
            // 将删除位置的上一个节点的next指针指向删除位置的下一个节点
            prevNode.next = removeNode.next;
        }
        // 维护链表长度
        size--;
        return removeNode;
    }
    

    链表操作的时间复杂度

    链表操作 时间复杂度
    查找节点 O(n)
    更新节点 O(1)
    插入节点 O(1)
    删除节点 O(1)

    链表的优势和劣势

    优势:链表能够灵活地插入,删除节点,所以更适用于插入,更新,删除操作更多场景。

    劣势:链表的查找操作,需要从头遍历整个链表,性能低下,不适用与读操作多的场景。

    单链表的完整代码(Java)

    public class LinkedList {
    
        /**
         * 链表的头指针
         */
        private Node head;
    
        /**
         * 链表的尾部指针
         */
        private Node last;
    
        /**
         * 链表的实际长度
         */
        private int size;
    
        /**
         * 获取链表的头指针
         *
         * @return 链表的头指针
         */
        public Node head() {
            return this.head;
        }
    
        /**
         * 获取链表的尾部指针
         *
         * @return 链表的尾部指针
         */
        public Node last() {
            return this.last;
        }
    
        /**
         * 获取链表的实际长度
         *
         * @return 链表的实际长度
         */
        public int size() {
            return this.size;
        }
    
        /**
         * 链表的查找操作
         *
         * @param index 需要查找的链表索引
         * @return 索引对应的链表节点
         */
        public Node get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            // 找到链表的头节点的位置
            Node temp = this.head;
            // 从头节点向后查找,共向后循环index次,即可找到index位置的节点
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp;
        }
    
        /**
         * 更新链表节点
         *
         * @param index 需要更新的链表位置
         * @param data  需要更新的节点的值
         */
        public void update(int index, int data) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            // 找到链表的头节点的位置
            Node temp = this.head;
            // 从头节点向后查找,共向后循环index次,即可找到index位置的节点
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            // 使用需要替换的值,替换原值
            temp.data = data;
        }
    
        /**
         * 直接在尾部插入
         *
         * @param data 需要插入的数据
         */
        public void insert(int data) {
            insert(size, data);
        }
    
        /**
         * 直接在尾部插入
         *
         * @param index 需要插入的链表位置
         * @param data  需要插入的数据
         */
        public void insert(int index, int data) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            // 将需要插入的数据封装为一个链表节点
            Node insertNode = new Node(data);
            // 链表节点为空的情况
            if (size == 0) {
                // 维护链表头部节点指针
                this.head = insertNode;
                // 维护链表尾部节点指针
                this.last = insertNode;
            } else if (index == 0) {
                // 头部插入
                // 使用新节点的next指针指向头部节点
                insertNode.next = this.head;
                // 维护链表头部节点的指针
                this.head = insertNode;
            } else if (index == size) {
                // 尾部插入
                // 直接使用尾部节点指针指向新结点
                this.last.next = insertNode;
                // 维护链表尾部节点的指针
                this.last = insertNode;
            } else {
                // 获取插入位置的前一个节点
                Node prevNode = get(index - 1);
                // 将新节点的next指针指向插入位置节点
                insertNode.next = prevNode.next;
                // 插入位置的前一个节点的next指针指向新节点
                prevNode.next = insertNode;
            }
            // 维护链表长度
            size++;
        }
    
        /**
         * 删除链表的结点
         *
         * @param index 需要删除的位置
         * @return 被删除的节点
         */
        public Node remove(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            Node removeNode = null;
            // 头部删除
            if (index == 0) {
                removeNode = this.head;
                // 维护链表的头部指针
                this.head = removeNode.next;
            } else if (index == size - 1) {
                // 尾部删除
                // 获取尾部的前一个节点
                Node prevNode = get(index - 1);
                removeNode = prevNode.next;
                // 置空尾部的前一个节点的next指针
                prevNode.next = null;
                // 维护链表的尾部指针
                this.last = prevNode;
            } else {
                // 获取插入位置的前一个节点
                Node prevNode = get(index - 1);
                // 需要删除的节点
                removeNode = prevNode.next;
                // 将删除位置的上一个节点的next指针指向删除位置的下一个节点
                prevNode.next = removeNode.next;
            }
            // 维护链表长度
            size--;
            return removeNode;
        }
    
    
        /**
         * 将节点点作为链表的一个内部类
         */
        class Node {
            // 节点存储的数据data
            private int data;
            // 该指针指向下一个节点的指针next
            private Node next;
    
            // 构造函数
            Node(int data) {
                this.data = data;
            }
    
            /**
             * 返回节点中存储的数据值
             *
             * @return 节点中存储的数据值
             */
            public int data() {
                return this.data;
            }
    
            /**
             * 返回下一个节点的指针
             *
             * @return 下一个节点的指针
             */
            public Node next() {
                return this.next;
            }
        }
    }
    

    双向链表的完整代码(Java)

    public class DoubleLinkedList {
    
        /**
         * 链表的头指针
         */
        private Node head;
    
        /**
         * 链表的尾部指针
         */
        private Node last;
    
        /**
         * 链表的实际长度
         */
        private int size;
    
        /**
         * 获取链表的头指针
         *
         * @return 链表的头指针
         */
        public Node head() {
            return this.head;
        }
    
        /**
         * 获取链表的尾部指针
         *
         * @return 链表的尾部指针
         */
        public Node last() {
            return this.last;
        }
    
        /**
         * 获取链表的实际长度
         *
         * @return 链表的实际长度
         */
        public int size() {
            return this.size;
        }
    
        /**
         * 链表的查找操作
         *
         * @param index 需要查找的链表索引
         * @return 索引对应的链表节点
         */
        public Node get(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            // 找到链表的头节点的位置
            Node temp = this.head;
            // 从头节点向后查找,共向后循环index次,即可找到index位置的节点
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp;
        }
    
        /**
         * 更新链表节点
         *
         * @param index 需要更新的链表位置
         * @param data  需要更新的节点的值
         */
        public void update(int index, int data) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            // 找到链表的头节点的位置
            Node temp = this.head;
            // 从头节点向后查找,共向后循环index次,即可找到index位置的节点
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            // 使用需要替换的值,替换原值
            temp.data = data;
        }
    
        /**
         * 直接在尾部插入
         *
         * @param data 需要插入的数据
         */
        public void insert(int data) {
            insert(size, data);
        }
    
        /**
         * 直接在尾部插入
         *
         * @param index 需要插入的链表位置
         * @param data  需要插入的数据
         */
        public void insert(int index, int data) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            // 将需要插入的数据封装为一个链表节点
            Node insertNode = new Node(data);
            // 链表节点为空的情况
            if (size == 0) {
                // 维护链表头部节点指针
                this.head = insertNode;
                // 维护链表尾部节点指针
                this.last = insertNode;
            } else if (index == 0) {
                // 头部插入
                Node headNode = this.head;
                // 将原头节点的上一个节点指针指向新节点
                headNode.prev = insertNode;
                // 使用新节点的next指针指向头部节点
                insertNode.next = headNode;
                // 维护链表头部节点的指针
                this.head = insertNode;
            } else if (index == size) {
                // 尾部插入
                // 直接使用尾部节点指针指向新结点
                this.last.next = insertNode;
                // 新节点的上一个节点指向原尾部节点
                insertNode.prev = this.last;
                // 维护链表尾部节点的指针
                this.last = insertNode;
            } else {
                // 获取插入位置的前一个节点
                Node prevNode = get(index - 1);
                // 插入位置的节点
                Node nextNode = prevNode.next;
                nextNode.prev = insertNode;
                // 将新节点的next指针指向插入位置节点,prev指针指向前一个节点
                insertNode.next = nextNode;
                insertNode.prev = prevNode;
                // 插入位置的前一个节点的next指针指向新节点
                prevNode.next = insertNode;
            }
            // 维护链表长度
            size++;
        }
    
        /**
         * 删除链表的结点
         *
         * @param index 需要删除的位置
         * @return 被删除的节点
         */
        public Node remove(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("超出链表的实际节点范围");
            }
            Node removeNode = null;
            // 头部删除
            if (index == 0) {
                removeNode = this.head;
                Node nextHead = removeNode.next;
                // 置空新的头部节点的pre指针
                nextHead.prev = null;
                // 维护链表的头部指针
                this.head = nextHead;
            } else if (index == size - 1) {
                // 尾部删除
                // 获取尾部的前一个节点
                Node prevNode = get(index - 1);
                removeNode = prevNode.next;
                // 置空尾部的前一个节点的next指针
                prevNode.next = null;
                // 维护链表的尾部指针
                this.last = prevNode;
            } else {
                // 获取插入位置的前一个节点
                Node prevNode = get(index - 1);
                // 需要删除的节点
                removeNode = prevNode.next;
                // 删除节点的下一个节点
                Node nextNode = removeNode.next;
                // 将删除位置的上一个节点的next指针指向删除位置的下一个节点
                prevNode.next = nextNode;
                nextNode.prev = prevNode;
            }
            // 维护链表长度
            size--;
            return removeNode;
        }
    
    
        /**
         * 将节点点作为链表的一个内部类
         */
        class Node {
            // 节点存储的数据data
            private int data;
            // 该指针指向上一个
            private Node prev;
            // 该指针指向下一个节点的指针next
            private Node next;
    
            // 构造函数
            Node(int data) {
                this.data = data;
            }
    
            /**
             * 返回节点中存储的数据值
             *
             * @return 节点中存储的数据值
             */
            public int data() {
                return this.data;
            }
    
            /**
             * 返回上一个节点的指针
             *
             * @return 上一个节点的指针
             */
            public Node prev() {
                return this.prev;
            }
    
            /**
             * 返回下一个节点的指针
             *
             * @return 下一个节点的指针
             */
            public Node next() {
                return this.next;
            }
        }
    }
    

    最后

    本文Github https://github.com/herenpeng/code-learn 已收录,欢迎Star

    展开全文
  • 程序=数据结构+算法数据结构是相互之间存在的一或多种特定关系的数据元素的集合。包括4类基本的结构:集合、线形结构、树形结构、图状或网状结构。通俗点就是数据的逻辑结构,比方说这些数据在内存中以什么样的...
  • 数据结构(Data Structure) :指相互之间存在一或多种特定关系的数据元素集合, 带有结构的数据元素的集合,它指的数据元素之间的相互关系,即数据的组织形式。 数据结构的逻辑结构与储存结构 数据结构的4...
  • 机器学习基本概念特征工程结构数据结构数据 特征工程 特征工程师对原始数据进行一系列...结构数据类型可以看做关系型数据库一张表,每列都有清晰定义,包含了数值型、类别型两种基本类型,每一行数...
  • CH3栈和队列 教学内容 数 本章介绍应用广泛的数据结构栈( stack)和队 列( queue,将分别给出这两种结构的定义基本 运算存储结构以及一些基本运算的具体实现, 栈和队列 并给出一些应用实例 教学重点与难点 重点掌握...
  • python中的pandas的两种基本使用2018年05月19日 16:03:36 木子柒努力成长 阅读数:480一、pandas简介pandas:panel data analysis(面板数据分析),基于numpy 构建的含有更高级数据结构和工具的数据分析包,类似...
  • 数据结构基本理解

    2020-04-15 13:27:01
    数据结构概述 1、什么是结构,我理解为一规则,为了达到一特定的目的,而进行的一项操作。 2、我们如何把现实中大量而复杂的问题以特定的数据类型和特定存储结构保存到住存储器(内存)中,以及在此基础上为实现...
  • 链表链式存取得数据结构,它与数组类似,但是单链表堆内存运用更加方便,可以在中间添加或者删除一个或者多个元素,不需要向数组那样移动大量元素。链表分为很多,单链表,双向链表,循环链表。 单链表...
  • 数据结构基本知识

    2021-03-10 11:44:11
    对于java开发来说数据结构的知识十分重要,以下只是为我个人总结,有什么不对地方希望各位小伙伴在评论区指出,不胜感激!我这里只讲一些重点知识点,其他就要靠各位小伙伴自己去查阅咯! 二叉树...
  • 1、 数据通路功能 数据在功能部件之间传送路径称为数据通路。...数据通路的基本结构主要有以下两种: (1) CPU内部单总线方式。将所有寄存器输入端和输出端都连接到一条公共通路上,者种结构比较简
  • 线性结构是有序数据项的集合,其中每个数据项都有唯一的前驱和后继(除了第一个没有前驱,最后一个没有后继)。新的数据项加入到数据集中时,只会加入到原有某个数据项之前或之后。具有这种性质的数据集,就称为...
  • 数据结构是一门研究数据以什么方式进行组织。学好数据结构并不一定就学好算法。要学好算法必须先学数据结构,数据结构是算法基础。 例如,学好了数组不一定学得会归并排序算法。 程序 = 算法 + 数据结构 数据...
  • 1.什么是顶点集? 图中具有相同特性的数据元素的集合称为顶点集 2.什么是边(弧)?...在有向图中,每个顶点有两种度,出度和入度。 (2)出度:顶点的出度指从那个顶点出发的边的数量。 (3)入度:顶点的入度...
  • 添加结点中序遍历BST三、BST删除情况做删除算法前准备工作1.删除叶子节点2.含一个子结点结点3.含个子结点结点 前言 前面所介绍树都不能达到排序效果 , 而本文要介绍BST-二叉排序树能轻松地...
  • 线性表(顺序表和链表) 什么是线性表? 在程序中将一组数据(通常同为...一个线性表某类元素的一个集合,还记录着元素之间的一顺序关系,线性表基本的数据结构之一。 根据线性表的实际存储方式,分为...
  • 本章通过扩张红黑树构造出两种数据结构:动态顺序统计和区间树。 1、动态顺序统计:查找倒数第i小的数据 复杂度为 lg(n) 为什么是扩张红黑树而不是搜索二叉树或者二叉树?  相对于搜索二叉树,红黑树的平衡性更...
  • Python基本数据结构

    2018-04-19 16:52:46
    既然有这样一个环境,那就狠狠逼自己一把Day1字典(dictionary)1、字典映射类型,它元素键值对2、字典关键字必须为不可变类型,且不能重复3.创建空字典使用{ } ,dic={}eg,tel={'jack':12,'mary':13}...
  • 利用完全二叉树的结构来维护一组数据,然后进行相关操作,一般操作进行一次时间复杂度在O(1)~O(log n)之间。 堆的两个特性: 结构性:用数组表示完全二叉树; 有序性:任一结点关键字其子树所有...
  • 这里就不总结了,只是说一下,这里栈和队列底层实现其实有数组和链表的两种实现方式。 栈的基本操作 这里采用链表实现方式,一个链表节点作为栈顶,一个链表节点作为栈底 基本数据结构如下所示: /** * autor...
  • 二叉树树型结构,它特点每个结点至多只有颗子树(二叉树有左右之分次序不能随意)括号这句话意思就是说二叉树有序 而树无序 二叉树的基本形态: (a)空树; (b)只有根结点; (c)右子树为空二叉树...
  • 什么要有图?...图种数据结构,其中节点可以具有零个或多个相邻元素,个节点之间连接称为边,结点也可以称为顶点,如图: 2.图常用概念 (1)顶点(vertex) (2)边(edge) (3)路径:比如从D->C...
  • 种数据结构,其中结点可以具有零个或多个相邻元素。个结点之间连接称为边。 结点也可以称为顶点。如图: 三、图常用概念 顶点(vertex):结点也可以称顶点。(如上图) 边(edge):个结点之间...
  • 链表作为最基本的数据结构之一,定义如下:链表物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序通过链表中的指针链接次序实现的。简单来说呢,链表就是由一系列节点组成的,每个节点都包括个...
  • 什么是数据结构 例1:如何在书架上摆放图书 问题:空间如何分配?类别应该分多细? 递归函数跑出来结果,前面100000输入,它什么都没做,直接罢工了。到底发生了什么?递归程序对...
  • 比特币的数据结构

    2021-01-07 20:22:22
    比特币中最基本的数据结构就是区块链。区块链是什么,就是一个一个区块组成的链表,区块链和普通的链表有什么区别?一个区别就是hash指针代替了普通的指针。 每个区块包含一个前一个区块的hash指针,这个指针是对前...
  • Inmon和Kimball两种DW架构支撑了数据仓库以及商业智能近二十年发展,其中Inmon主张自上而下架构,不同OLTP数据集中到面向主题、集成、不易失和时间变化的结构中,用于以后分析;且数据可以通过下钻到最细...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,152
精华内容 860
关键字:

两种基本的数据结构是什么

数据结构 订阅