精华内容
下载资源
问答
  • 1. 基于数组实现循环队列 package com.feifei.demo.queue; import java.io.Serializable; import java.util.Objects; import java.util.stream.Stream; /** * 自定义循环队列 * 1. 单队列会出现假溢出的情况,...

    1. 基于数组实现循环队列

    package com.feifei.demo.queue;
    
    import java.io.Serializable;
    import java.util.Objects;
    import java.util.stream.Stream;
    
    /**
     * 自定义循环队列
     * 1. 单队列会出现假溢出的情况,也就是队列有空闲空间,但是无法插入
     * 队列有2个指针标识位,一个为front(用于指向队首) 一个为rear(用于指向队尾)
     * 在队列为空时,front和rear相同
     * front
     * rear
     * null   null   null   null   null
     *
     * 插入一个值后, rear后移一位, 只有当队列出队时,front才会发生偏移,请记住,
     * 队列的队首一直指向队列的首部(有数据的首部)
     * front
     *        rear
     *   1    null   null   null   null
     *
     * 当队列rear达到数组长度时,此时在出队一个数据,模型如下所示:
     *          front
     *                             rear
     * null      1     2      3    null
     *
     * 此时我们在插入数据5到队尾时,就会出现假溢出情况,明明还有存储空间,但是rear已经越界了
     *          front
     *                                  rear
     * null      1     2      3     4   越界
     *
     * 此时,我们需要循环队列(逻辑上来说,实际还是数组)来完成此操作,当插入数据4时,我们的rear应该指        
     * 向数组索引下标为0的单元格,采用通用公式为 rear = (rear + 1) % capacity, 其中capacity为数 
     * 组长度此时模型如下所示:
     *          front
     * rear
     * null      1     2      3     4   
     *
     * rear到达数组长度时,这里我们标识数组长度为capacity,此时我们再次插入数据,此时队列已满
     *          front
     *          rear
     *  5        1       2        3       4
     *
     * 但是我们发现队列为空和队列已满时,都满足front == rear,为了区分,我们通常采用的做法是在队列还 
     * 剩一个空的单元格未插入时标识队列已满,比如:
     *          front
     * rear
     * null      1     2      3     4   
     *
     * 这个就表示队列已满,满足front = (rear + 1) % capacity即标识队列已满
     *
     */
    public class CircularQueue<E> implements Serializable {
    
        private static final long serialVersionUID = -2938153003420395845L;
    
        /**
         * 数据存储数组
         */
        private transient Object[] elementData;
    
        /**
         * 定义队首
         */
        private transient int front;
    
        /**
         * 定义队尾
         */
        private transient int rear;
    
        /**
         * 定义元素个数
         */
        private int size;
    
        /**
         * 自定义容量
         */
        private int capacity;
    
        /**
         * 定义默认的数组容量大小, 定义为11的目的是为了实现预留一个存储空间来
         * 区分队列是否已存满和队列是否为空, 因为队列为满和为空时的front == rear
         */
        private transient static final int DEFAULT_CAPACITY_SIZE = 11;
    
        public int size() {
            return size;
        }
    
        public CircularQueue() {
            elementData = new Object[(capacity = DEFAULT_CAPACITY_SIZE)];
        }
    
        public CircularQueue(int capacity) {
            if (capacity <= 0) {
                elementData = new Object[(this.capacity = DEFAULT_CAPACITY_SIZE)];
            } else {
                this.capacity = capacity;
                elementData = new Object[(capacity + 1)];
            }
            this.size = 0;
        }
    
        /**
         * 入队,数据添加至队尾
         * 校验队列是否已满,因为队列为空
         * @return
         */
        public boolean offer(E element) {
            if (Objects.isNull(element)) {
                return false;
            }
            // 校验队列是否已满, 如果队列已满则不新增
            if ((rear + 1) % capacity == front) {
                System.out.println("队列已满, 不可再新增数据");
                return false;
            }
    
            elementData[rear] = element;
            size++;
            // 将队尾重新赋值,这里不直接进行加一的原因在于可能会出现假溢出的情况
            // 比如说已经存在队尾的索引为4,(4 + 1) % 5 = 0 => 队尾指向了索引下标为0
            rear = (rear + 1) % capacity;
    
            return true;
        }
    
        /**
         * 出队,数据从队首中被移除
         * @return
         */
        public E poll() {
            // 校验队列是否为空,为空则不允许删除
            if (rear == front) {
                System.out.println("队列为空,不允许删除");
                return null;
            }
    
            E elementDatum = (E) elementData[front];
    
            elementData[front] = null;
            // 将队首重新赋值,赋值逻辑和队尾逻辑类似
            front = (front + 1) % capacity;
            // 将队列数据长度进行减一操作
            size--;
            return elementDatum;
        }
    
        public static void main(String[] args) {
    
            CircularQueue<Integer> queue = new CircularQueue<>();
            System.out.println("queue = " + queue.size());
            System.out.println("queue = " + queue.capacity);
            queue.offer(21);
            queue.offer(22);
            queue.offer(23);
            queue.offer(24);
            queue.offer(25);
            queue.offer(26);
    
            Object[] elementData = queue.elementData;
            Stream.of(elementData).forEach(ele -> System.out.println(ele));
    
            System.out.println("elementData = " + queue.poll());
            System.out.println("elementData = " + queue.poll());
            System.out.println("elementData = " + queue.poll());
            Stream.of(queue.elementData).forEach(ele -> System.out.println(ele));
        }
    }

    2. 使用双向链表实现队列:

    package com.feifei.demo.queue;
    
    
    /**
     * 自定义链表队列(链表为双向链表),理论上是没有长度限制的
     */
    public class LinkedQueue<E> {
    
        /**
         * 定义队首
         */
        private Node<E> front;
    
        /**
         * 定义队尾
         */
        private Node<E> rear;
    
        /**
         * 定义数据长度
         */
        private int size;
    
        /**
         * 定义节点类
         * @param <E>
         */
        private class Node<E> {
    
            private E element;
    
            private Node<E> preNode;
    
            private Node<E> nextNode;
        }
    
        public LinkedQueue() {
            front = rear = new Node<>();
        }
    
        /**
         * 获取数据长度
         * @return
         */
        public int size() {
            return size;
        }
    
        /**
         * 入队
         *
         * @param element
         * @return
         */
        public boolean offer(E element) {
            Node<E> eNode = new Node<>();
            eNode.element = element;
            // 当队列为空时
            if (rear == front) {
                front = eNode;
                rear.preNode = eNode;
            } else {
                Node<E> preNode = rear.preNode;
                preNode.nextNode = eNode;
                eNode.preNode = preNode;
                rear.preNode = eNode;
                System.out.println("添加成功");
            }
            size++;
    
            return true;
        }
    
    
        /**
         * 出队
         *
         * @return
         */
        public E pop() {
            if (rear == front) {
                System.out.println("队列为空,无法进行删除操作");
            }
    
            E element = front.element;
            Node<E> nextNode = front.nextNode;
            // 置空处理,方便GC回收
            front.preNode = null;
            front.nextNode = null;
            front.element = null;
            // 将下一个节点作为队首
            front = nextNode;
            size--;
            return element;
        }
    
        public static void main(String[] args) {
            LinkedQueue<Integer> linkedQueue = new LinkedQueue<>();
            linkedQueue.offer(1);
            linkedQueue.offer(2);
            linkedQueue.offer(3);
            linkedQueue.offer(4);
            linkedQueue.offer(5);
    
            System.out.println("linkedQueue pop = " + linkedQueue.pop());
            System.out.println("linkedQueue pop = " + linkedQueue.pop());
            System.out.println("linkedQueue pop = " + linkedQueue.pop());
            System.out.println("linkedQueue pop = " + linkedQueue.pop());
            System.out.println("linkedQueue pop = " + linkedQueue.pop());
        }
    }
    
    

     

    展开全文
  • 若是不清楚链表的结构,该篇文章不适合观看,这里只做文字说明,没有链表结构的图示


    前言:
    线性表是我们最常用的一种数据结构,线性表包含顺序表和链表,顺序表典型应用就是我们常用的ArrayList,链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结链表中的双向循环链表,为单链表的结点增加一个指向前驱的指针域,单链表就变成了双链表,将双链表的头尾相连,双链表就成了双向循环链表。

    一、相关概念

    第一部分主要介绍下和链表有关的相关概念,这里给出的概念都是书本上的官方定义,并不是作者胡诌的,为什么给出这些官方的定义呢 ?因为笔者认为官方给出的定义,是对一个概念最本质的解释,它的解释经过了时间的考验,被认为是解释的最合理深入简明扼要的。

    1.什么是线性表

    线性表是由n个数据元素构成的有限序列,n为线性表的表长,当n为0时表示当前线性表是空表。线性表有且仅有一个开始结点和终端节点。且开始结点没有前驱,终端节点没有后继,其余节点有且仅有一个前驱和后继。线性表一般分为顺序表和链表。

    2.什么是顺序表

    采用顺序存储结构存储数据元素的线性表被称为顺序表,顺序表,要求逻辑上相邻的数据元素在物理内存的存储上也是相邻的,当在顺序表的第i(0<=i<=n)插入一个数据元素时,需要后移n-i+1个数据元素,当删除第i个元素时需要移动n-i个数据元素。java实现顺序表

    3.什么是链表

    采用链式存储结构存储数据元素的线性表被称为链表,链表不要求逻辑上相邻的数据元素内存上必须相邻,链表的每个节点都包含两部分,一部分是数据域用以存储数据,一部分是指针域用以存储指向相邻结点的指针或者引用。链表通过每个节点的指针域将一串数据串联成链。当结点只有一个指针域时,被称为单链表。单链表-含头结点单链表-不含头结点

    4.单链表、双链表、循环单链表、循环双链表

    当链表的结点只有一个指针域时被称为单链表,循环单链表是单链表的一种特殊变化,只是将尾结点又指向了头结点(也可能是首结点)。
    当链表的结点有两个时,一个指向前驱,一个指向后继这种链表便是双链表,循环双链表是双链表的一种特殊变化,只是将尾结点又指向了头结点(也可能是首结点)。
    所有的链表的实现均有两种方式,一种是带有头结点,一种是不带有头结点的实现方式,两种实现略有区别。

    5.为什么需要循环链表?

    循环链表一般就是指循环单链表,不特殊指明是双向循环链表,那么该名称描述的就是单项循环链表,之所以需要循环链表是因为在操作系统中,循环链表有特定的应用场景,在一些场景中,链表中的元素需要循环的执行,但是在实际的开发中应用最多的还是双向循环链表。

    6.为什么需要双向链表?

    若是给定了一个结点,根据当前结点获取该结点的上一个结点,那么我们是没有办法直接获取的,只能是遍历链表,但若是使用了双向链表,我们则可以直接获取到该元素的上一个结点,时间复杂度就变成了O(1)。所以双向链表的实际应用意义更强,将双向链表的首尾相连就成了双向循环链表,双向循环链表的应用最常见的就是LinkedList。

    7.头结点和首结点

    首节点:真正存储第一个数据元素的结点被称为首节点。
    头结点:当链表采用带头结点方式实现时,会创建一个数据域为null的节点,该节点的指针域存储的指针指向首节点的指针,他的唯一作用是标识链表的开始,带有头结点的链表更易于操作。

    8.常见的栈和队列与线性表的关系

    栈和队列也是常见的数据结构,但是栈和队列并不是线性表的一种,线性表只包含了顺序表和链表。不过我们可以将栈和队列看成是特殊的线性表。怎么特殊呢,栈是被限制了只能在一端进行插入和删除操作的线性表,所以栈的特性是先入后出,队列是被限制了只能在一端插入另一端删除的线性表,所以队列的特性是先入先出。既然栈和队列都是特殊的线性表,那么栈和队列自然就可以使用线性表来实现了,通常可以使用线性表中的顺序表和队列来实现栈和队列。

    二、实现过程

    单链表-含头结点
    单链表-不含头结点
    上面是两种单链表的实现方式,其实无论是双链表还是双向循环链表他的实现方式都是类似的,区别都很有限,上面两篇文章里详细实现了单链表的各种常用方法,因此在该文章里只会总结必须用到的几个方法,比如插入、删除、清空、长度、判空、根据下标获取等,其他方法的实现都不难,就不一一展示了。

    1.提供节点类:DupNode

    双向循环链表的实现,我们首先必须为其提供一个结点类,该类需要有三个属性,一个数据域,一个指向前驱的指针域,还有一个指向后继的指针域,然后提供必要的构造方法即可,如下:

    /**
     * @author pcc
     * @version 1.0.0
     * @className DupNode
     * @date 2021-04-19 16:43
     * 该类是双向链表的结点类
     * 该类包含了数据域,后继指针域、前驱指针域三个属性。
     */
    public class DupNode {
        Object object;
        DupNode prior;//前驱指针域
        DupNode next;//后继指针域
    
        public DupNode(){
            this(null);
        }
        public DupNode(Object object){
            this(object,null,null);
        }
        public DupNode(Object object,DupNode prior,DupNode next){
            this.object = object;
            this.prior = prior;
            this.next = next;
        }
    }
    

    2.提供双向循环链表的实现类:DoubleLinkedTable

    采用带有头结点的方式实现双向循环链表,因此我们需要定义一个头结点。然后提供初始化它的构造器。值得注意的是,在初始化头结点时,我们必须将他的前驱和后继都声明为自己,这样才是一个空的双向循环链表。

    public class DoubleLinkedTable {
        //头结点
        DupNode head;
    
        public DoubleLinkedTable(){
            head = new DupNode();
            head.prior = head;
            head.next = head;
        }
    }
    

    3.提供长度(length)、打印(display)、清空(clear)等方法

    这些方法的实现原理都很简单,求链表长就是遍历链表计数即可,打印也是遍历链表,清空则是将头结点的前驱和后继都声明为自己,下面是三个方法的实现:

        //长度
        public int length(){
            DupNode node = head.next;
            int j = 0;
            while(!node.equals(head)){
                j++;
                node = node.next;
            }
            return j;
        }
    
        //打印
        public void display(){
            DupNode node = head.next;
            while(!node.equals(head)){
                System.out.println(node.object);
                node = node.next;
            }
        }
        //清空
        public void clear(){
            head.next = head;
            head.prior = head;
        }
    

    4.提供根据下标插入方法:insert(int i,Object object)
    学习双向循环链表建议还是先学习单链表,会了单链表双向循环链表就是窗户纸,一桶就破,因为他们的实现思路都是一样的,只是稍微的变化而已。单链表的遍历我们的退出条件是找到尾结点就退出(node.next == null),循环链表肯定没有尾结点了,退出循环的条件就成了碰到头结点再退出(node ==head),另外一点区别就是双向循环链表的赋值问题,我们需要为新结点的前驱指针和后继指针赋值,同时需要为新结点的上一个节点的后继后继指针从新赋值,还需要为新节点的后继结点的前驱指针重新赋值,代码实现如下:

       /**
         * 思路:
         * 1.寻找下标为i-1的数据元素,注意退出循环的条件应该是node!=head
         * 2.赋值即可,循环链表的核心就是空表也会有循环体系
         * 3,赋值时,i+1位置的元素应该是node.next 所以,应为node.next最后赋值
         * @param i
         * @param object
         * @throws Exception
         */
        public void insert(int i,Object object) throws Exception{
            if(i<0 || i>length())
                throw new Exception("下标不合法");
             DupNode node = head;
             int j = 0;
             while(!node.next.equals(head) && j<i){
                 j++;
                 node = node.next;
             }
    //         DupNode newNode = new DupNode(object);
    //         node.next.prior = newNode;
    //         newNode.prior = node;
    //         newNode.next = node.next;
    //         node.next = newNode;
    
            //写成以下这种和上面注释的部分,效果一样,无区别
             DupNode newNode = new DupNode(object,node,node.next);
             node.next.prior = newNode;
             node.next = newNode;
        }
    

    到了这里,我们就可以初步测试下,双向链表的插入是否有效了,下面创建一个测试类测试下,如下图所示,将几个元素插入到了双向循环链表中,然后输出结果正常,说明插入方法实现无误。有了这些头插法、尾插法直接根据下标即可轻松实现,这里不展示了。
    在这里插入图片描述

    5.提供根据下标删除的方法:remove(int i)

    实现思路其实和单链表的删除是没有区别的:寻找到下标为i-1的数据元素,然后将他的后继更改为i+1的数据元素,然后将下标为i+1的数据元素的前驱更改为,下标为i-1的数据元素即可,实现如下:

        //删除
        public void remove(int i) throws Exception{
            if(i<0 || i>length()-1)
                throw new Exception("下标不合法");
            DupNode node = head;
            int j = 0;
            while(!node.next.equals(head) && j<i){
                j++;
                node = node.next;
            }
            node.next = node.next.next;
            node.next.prior = node;
        }
    

    然后来测试下删除方法,就测试下删除下标为2的元素吧,理论上删除后,输出的应该是:张三、李四、赵柳,如下图可见,输出无误,可见删除方法实现时无误的。
    在这里插入图片描述

    6.提供根据下标获取方法(get(int i))、根据指定结点获取前一个结点方法(getPrior)、根据指定结点获取后一个结点信息方法(getNext)

    上面也说过,双向链表解决的问题就是在获取指定结点的上一个结点时是无需遍历链表的,这样大大节省了时间成本,这里就测试下该方法的实现。三个方法的实现如下所示:

        //根据下标获取
        public Object get(int i) throws Exception{
            return getNode(i).object;
        }
    
        //根据下标获取其前一个元素
        public Object getPrior(int i) throws Exception{
            return getNode(i).prior.object;
        }
    
        //根据下标获取其后一个元素
        public Object getNext(int i) throws Exception{
            return getNode(i).next.object;
        }
    
        public DupNode getNode(int i) throws Exception{
            if(i<0 || i>length())
                throw new Exception("下标不合法");
            DupNode node = head.next;
            int j =0;
            while(node.equals(head) && j<i){
                j++;
                node = node.next;
            }
            return node;
        }
    

    下面我们来测试下这三个方法是否正确,使用李四所在结点来进行测试,李四的下标应该是1,传入1分别运行三个方法,若是正确应该输出的是:李四、张三、王五,如下图可见结果正确。
    在这里插入图片描述

    三、总结

    1.链表的缺点

    线性表的两种实现顺序表、链表。相比于顺序表,链表的缺点就是查找元素比较慢,查找元素的时间复杂度是O(n),而顺序表的时间复杂度是O(1),在查找上顺序表要优于链表,链表查找慢,就是它的缺点了,但是双向循环链表在一定程度上减少了查找时的时间复杂度,但是依然是不及顺序表的查找效率的,所以具体的使用场景还是静态数据适合使用顺序表,动态数据适合使用链表。

    2.链表的优点

    顺序表在指定下标x位置插入元素,组需要后移n-x+1个元素,若是删除下标为x的数据元素,则需要向前移动n-x个数据元素,但是链表则不需要移动任何元素,链表需要做的只是找到对应的元素将指针域中的指针进行更新即可。链表的插入和删除的时间复杂度可以看成O(1),而顺序表插入和删除操作的都是O(n).所以链表的优点就是插入和删除比较快。

    3.如何使用链表

    所以综合链表的优点与缺点我们可以发现,顺序表更适合存储“静态”型数据,而链表更适合存储“动态”型数据,何为动态型呢,就是那些插入、删除操作比较频繁的数据。这类数据更适合使用链表存储。而数据结构不易改变的数据使用顺序表存储更合适。顺序表可类比java中的ArrayList,链表可类比java中的LinkedList。这两者都是顺序表与链表的典型应用。

    展开全文
  • Java实现队列的两种方式(链表循环数组)数组实现循环队列1、需要一个theSize变量,来判断队列是否填满了数组,或者判断队列是否为空代码如下public class cycleQueue { private int front ;//队头 private int ...

    Java实现队列的两种方式(链表,循环数组)

    数组实现循环队列

    1、需要一个theSize变量,来判断队列是否填满了数组,或者判断队列是否为空

    代码如下

    public class cycleQueue<T>
    {
        private int front ;//队头
        private int back;  //队尾
        private int  theSize;  //队伍长度
        private  T[] theQueue=(T[]) new Object[10]; //数组
    
        /*
         * 方法名:enqueue
         * 作用:入队列
         */
        public boolean enqueue(T x)
        {
            if (theSize==theQueue.length) //判断队列是否已满
                return false;
    
            theQueue[back]=x;//在队列尾部添加新成员
            back=(1+back)%theQueue.length;
            theSize++;
            return true;
        }
        /*
         * 方法名:dequeue
         * 作用:出队列
         */
        public T dequeue()
        {
            if (theSize==0) //判断队列是否为空
                return null;
    
            T dequeueVal=theQueue[front];//不为空,返回队列的对头
            theSize--;
            front=(front+1)%theQueue.length;
            return dequeueVal;
        }
    
        public static void main(String[] args)
        {
            cycleQueue<Integer> test=new cycleQueue<>();
    
            //测试无误 
            for(int i=1;i<=10;i++)
                test.enqueue(i);
            for(int i=1;i<=5;i++)
                System.out.println(test.dequeue());
            System.out.println();
            for(int i=11;i<=15;i++)
                test.enqueue(i);
            for(int i=1;i<=10;i++)
                System.out.println(test.dequeue());     
        }
    
    }

    链表实现队列

    1、使用单项链表

    2、可以使用两种方式判断队列是否为空 1是theSize的大小,2是front.next是否等于null。下面的代码两种判断方式都使用了

    public class QueueOfList<E> 
    {
        private Node front=null; //队头
        private Node back=null;  //对尾
        private int size;        //队伍大小
    
        /*
         *    节点定义成内部类
         */
        private class Node//链表节点类
        {
            Node next; //指向下一节点
            E data;//存放数据
            public Node(Node next, E data) //构造方法
            {
                super();
                this.next = next;
                this.data = data;
            }
    
        }
        /*
         *   方法:isEmpty
         *   作用:判断队列是否为空
         */
        public boolean isEmpty()//队列是否为空
        {
            return front==null;
        }
        /*
         *   方法:enQueue
         *   作用:入列
         */
        public void enQueue(E newVal)//入队
        {
            Node newNode=new Node(null, newVal);
            if (front==null)//分成队伍为空,与不空两种情况
            {
                front=newNode;
                back=newNode;
            }
            else
            {
                back.next=newNode;
                back=newNode;
            }
        }
        /*
         *   方法:deQueue
         *   作用:出列,空列返回null
         */
        public E deQueue()
        {
    
            if (!isEmpty()) //队伍不为空
            {
                Node put=front;
                front=front.next;
                return put.data;
            }
            else//队伍为空,返回null
                return null;
        }
        public static void main(String[] args)
        {
            QueueOfList<String> test=new QueueOfList<>();
            //测试
            test.enQueue("111");
            test.enQueue("222");
            test.enQueue("333");
            while(!test.isEmpty())
                System.out.println(test.deQueue());
            test.enQueue("111");
            test.enQueue("111");
            test.enQueue("111");
            System.out.println(test.deQueue());
    
            System.out.println(test.deQueue());
            System.out.println(test.deQueue());
        }
    }
    展开全文
  • 什么是双向循环链表在了解双向循环链表之前,如果对链表还没有一个清晰的概念,建议你看看单链表和单向循环链表,这有利于你更好的理解下面的内容。(废话有点多[逃]相比单链表,双向循环链表是一个更加复杂的结构。...

    什么是双向循环链表

    在了解双向循环链表之前,如果对链表还没有一个清晰的概念,建议你看看单链表和单向循环链表,这有利于你更好的理解下面的内容。(废话有点多[逃]

    相比单链表,双向循环链表是一个更加复杂的结构。因为双向循环链表的节点不仅包含指向下一个节点的指针(next),还包含指向前一个节点的指针(prev)。

    3cfb2159c2188132acb06b838a76be86.png

    在双向循环链表中,可见的不只有头指针head,还有尾节点end。这是和单链表的区别。

    双向循环链表的头指针head的前一个节点指向end,尾节点end的后一个节点指向head。

    基本操作

    双向循环链表的基本操作有:增(add),删(remove),改(set),查(find),插(insert)等。在这里我们只讲解remove,insert和getNode操作,其他实现可看下方源码。

    获取节点

    由于双向链表有两个可见的节点(head和end),因此双向循环链表获取节点的操作和单链表有所不同。

    把需要获取的节点序号和链表长度/2比较

    若小于,说明节点是偏前的,因此从head开始一路next下去

    若大于,说明节点是偏后的,因此从end开始一路prev上去

    这样的设计能使getNode操作的时间复杂度缩短为O(logN)

    删除元素

    获取待删除元素的节点node

    把node前一个节点的next指针设置为node的后一个节点。具体实现为:node.prev.next=node.next

    把node后一个节点的prev指针设置为node的前一个节点。具体实现为:node.next.prev=node.prev

    由于没有指针指向node,node会被自动清理

    记录链表长度的变量-1

    插入元素

    获取待插入元素的节点node

    创建一个节点mynode,next指向node,prev指向node.prev

    把node.prev该节点的next指向mynode

    把node的前一个节点prev指向mynode

    双向循环链表的优劣

    优势

    相比单链表,双向循环链表所有基本操作均快于单链表(java源码的LinkList类就是双向循环链表)

    能直接获取节点的前一个节点,十分灵活

    劣势

    相比单链表,双链表的空间内存明显要大很多

    双链表的设计应用了算法设计的“空间换时间”思想,通过消耗更多的空间来缩小操作的时间复杂度。

    源码实现

    public class Node {

    public Anytype data;//数据

    public Node prev;//前一个节点

    public Node next;//后一个节点

    public Node(Anytype data,Node prev,Node next){

    this.data=data;

    this.prev=prev;

    this.next=next;

    }

    }

    ----------------------------------------------

    public class DoubleLink {

    Node head;//头指针

    Node end;//尾节点

    int size;//记录链表长度

    //初始化链表

    public void initlist(){

    end=new Node<>(null,null,null);

    head=new Node<>(null,null,end);

    end.prev=head;

    end.next=head;

    size=0;

    }

    //获取长度

    public int length(){

    return size;

    }

    //获取节点

    public Node getNode(int index){

    Node n;

    if(index>=size/2){

    n=end;

    for(int i=length();i>index;i--){

    n=n.prev;

    }

    return n;

    }

    else{

    n=head;

    for(int i=0;i<=index;i++){

    n=n.next;

    }

    return n;

    }

    }

    //添加元素

    public void add(AnyType a){

    Node renode=new Node<>(a,getNode(size-1),end);

    renode.prev.next=renode;

    renode.next.prev=renode;

    size++;

    }

    //插入元素

    public void insert(int i,AnyType a){

    Node n=getNode(i);

    Node renode=new Node<>(a,n.prev,n);

    n.prev.next=renode;

    n.prev=renode;

    size++;

    }

    //删除元素

    public AnyType remove(int i){

    Node n=getNode(i);

    AnyType data=n.data;

    n.prev.next=n.next;

    n.next.prev=n.prev;

    size--;

    return data;

    }

    //获取i位置的数据

    public AnyType get(int i){

    return getNode(i).data;

    }

    //为i位置元素重新赋值

    public AnyType set(int i,AnyType a){

    Node n=getNode(i);

    AnyType old=n.data;

    n.data=a;

    return old;

    }

    //清空链表

    public void clear(){

    initlist();

    }

    public void print(){

    for(int i=0;i

    System.out.println(getNode(i).data);

    }

    }

    }

    展开全文
  • * 基于双向链表实现双端队列结构 */ package dsa; public class Deque_DLNode implements Deque { protected DLNode header;//指向头节点(哨兵) protected DLNode trailer;//指向尾节点(哨兵) protected ...
  • 队列的定义: 队列是一种只允许一端进行插入操作,在另一端进行删除操作的线性表。允许插入的一端称为称为队尾,删除的一段是队头。想象你去排队购买车票时,排着一个很长的队,排在最前面的人买完票走了,这个...
  • 1.顺序队列(循环) 基于数组的循环队列其实很简单,就是当数组满后重置入队和出队位置到数组头部。 public class CircleQueue<E> { // Object保存E,因为E不能E[] --> (E)obj private Object[] items; ...
  • 数组实现顺序队列实现简单入队、出队操作; //数组实现固定大小n的顺序队列; public class QueueByArray { private Object[] array; private int head = 0; private int tail = 0; pr...
  • ●在这个实验中,我们将创建一个更通用的数据结构,称为 deque,是双端队列的缩写。 ●在一个 deque 中,您可以添加和删除两端的项(无论是其前端还是后端)。 ○在本实验室,您将完成包括添加和删除在内的许多...
  • 1、队列 特点:先进先出 ... 基于数组的实现: public class MyQueue { private int[] elements; public MyQueue() { elements = new int[0]; } //入队列 public void add(int data) { int...
  • 假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法。(Java描述)
  • 链式存储结构中栈、队列循环链表,都是在上篇的单链表基础上进行实现的。话不多说先看链式存储的栈。 栈 先看一下的类图: 接下来是实现: public class LinkedStack<E> implements Stack<E>{ ...
  • 循环链表与循环队列

    万次阅读 2017-03-07 14:05:38
    和普通链表相比,循环链表不需要头指针,能够从任意位置实现链表遍历 双向循环链表 和单向链表相比,双向链表多了一个指向上一个节点的前向指针 相比于单向链表,双向循环链表的遍历更加灵活,但缺点...
  • 文章目录1、什么是队列2、Queue数据结构实现——基于动态数组2.1、基本函数实现2.2 进出队列函数2.3 查询操作3、Queue数据结构实现——基于链表函数3.1、基本函数实现3.2 进出队列函数3.3 查询操作4、LoopQueue循环...
  • Java 实现有序链表

    2021-03-04 01:56:42
    平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1),如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择优先级队列 可以使用有序链表实现有序链表的插入排序:...
  • 使用链表实现队列 下面改进链表使链表带有尾指针。 为最后一个节点添加一个指针tail做标记。 此时在head和tail两端添加节点是非常容易的。 由于链表可能不是对称的,所以在tail删除节点可能不太容易。要删除...
  • java 用单链表实现队列

    千次阅读 2017-07-28 11:28:52
    public class LinkQueue { class Node { private T data;//数据域 private Node next;//引用域 public Node() { this.data=null; this.next=null; } public Node(T data) ...
  • Java代码实现循环队列

    2021-09-26 21:21:41
    Java代码实现循环队列 // 基于数组实现一个循环链表 public class CircleArrayQueue<T> { // 定义数组用于存放数据 private T[] arr; private int head; // 记录队列头 private int tail; // 记录队列尾 ...
  • Java实现单向链表

    2021-02-28 17:23:40
    数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~本文主要讲解单链表的基础知识点,做一个简单的入门~如果有错的地方请指正二、回顾与知新说起链表,我们先提一下数组吧,跟数组比较一下就很...
  • 本篇博客所涉及到的代码,均已...本篇博文,将通过数组,单向循环链表两种方式,使用Java实现队列, 帮助大家进一步了解队列这种数据结构 本篇博客要点如下: 队列 基本概念 存储结构 顺序存储结构 链式存储结构 使...
  • 链表实现消息队列 Redis链表支持前后插入以及前后取出,所以如果往尾部插入元素,往头部取出元素,这就是一种消息队列,也可以说是消费者/生产者模型。可以利用lpush和rpop来实现。但是有一个问题,如果链表中没有...
  • JAVA 实现双向链表

    千次阅读 2019-01-28 23:23:05
    我觉得 Java 的垃圾回收机制很恶心。Java 不让人对内存做任何操作。为了让人放弃直接操作内存的想法,甚至佯装没有指针。 Java 虚拟机有一个垃圾回收机制,负责释放 / 回收无用对象所占用的内存空间,从而防止内存...
  • 双端链表: 双端链表与传统链表非常相似.只是新增了一个属性-即对最后一个链结点的引用rear 这样在链尾插入会变得非常容易,只需改变rear的next为新增的结点即可,而不需要循环搜索到最后一个节点 所以有insertFirst...
  • Java语言怎么使用一个链表实现循环队列?是不是必须要使用双向链表?期待权威的回答
  • //如果要插入的节点比链表中的最后一个节点的值还要大,直接在尾部插入 if (this.isEmpty() || cmp.compareTo(head.prev.data) > 0) { return super.add(data); } //寻找插入位置 LDNode p = head.next; while...
  • 在上次分享完单向链表的简单编写后,索性对于双向链表进行了一定的了解,在上次的基础上进行了一定程度的改进,做了一个非循环的双向链表。  双向链表的特点在于每个节点不仅知道自己的下属节点而且还知道自己的父...
  • Java链表实现队列

    千次阅读 2019-11-17 20:05:20
    Java链表实现队列

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 55,535
精华内容 22,214
关键字:

java实现循环链表队列

java 订阅