数据结构笔记总结(3.7)带有尾指针的链表:使用链表实现队列

改进我们的链表

之前曾经讨论过,为什么对于链表来说,在头的位置不管是插入元素或是删除元素都是容易的呢?

这是因为对于链表来说有head这一个变量来帮助我们标记头在哪,拥有了这个标记之后,我们在链表的头部进行添加元素或者删除元素都是很容易的。

现在我们希望在链表的尾部进行操作也是容易的,那我们该怎么做呢?

非常简单,我们可以再设计一个node型的变量tail,来标记链表的尾部在哪。

这种情况下,如果有了tail这个节点,我们在链表的尾部添加一个元素是非常容易的。

其实这相当于之前写的在size位置添加元素,换句话说,tail这个位置的节点就是待添加元素的位置也就是最后一个位置之前的节点,相应的在后面添加一个节点是非常容易的。

那么在tail端删除元素是否容易呢?

由于我们这个链表不是对称的,所以思考删除元素会有些不同。

回忆一下之前删除元素需要找待删除元素前一个位置的节点,现在如果想删除tail这个位置的节点就要找tail这个位置之前的节点,可是如何找之前的节点呢?

对于现在这个链表来说,对于每一个节点next,它指向后一个节点,所以我们是无法使用O(1)的复杂度找到tail节点之前位置的节点的,还是需要从head开始从头遍历,所以从tail删除元素不容易。

综上所示,我们应该从head端删除元素,从tail端插入元素,因此head端作为队列的队首,tail端作为队尾.

此外还要小心一种情况,如果此时链表为空的时候,head和tail都将指向空,这种情况是一种特殊情况。

代码演示

创建一个LinkedListQueue

public class LinkedListQueue implements Queue {

    private class Node{
        public E e;
        public Node next;

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e, null);
        }

        public Node(){
            this(null, null);
        }

        @Override
        public String toString(){
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    public LinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public boolean isEmpty(){
        return size == 0;
    }

    @Override
    public void enqueue(E e){
        if(tail == null){
            tail = new Node(e);
            head = tail;
        }
        else{
            tail.next = new Node(e);
            tail = tail.next;
        }
        size ++;
    }

    @Override
    public E dequeue(){
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if(head == null)
            tail = null;
        size --;
        return retNode.e;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return head.e;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while(cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return res.toString();
    }

    public static void main(String[] args){

        LinkedListQueue queue = new LinkedListQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

运行程序,分析结果:

首先入队三个元素0,1,2,然后出队,0出队后变成1,2,然后再入队三个元素3,4,5,出队一个元素1,队列变成2,3,4,5,再入队三个元素6,7,8,出队一个元素2,队列变成3,4,5,6,7,8,最后入队9,队列变成3,4,5,6,7,8,9。

比较一下LoopQueue和LinkedListQueue

代码如下:

import java.util.Random;

public class Main {

    // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间,单位:秒
    private static double testQueue(Queue q, int opCount){

        long startTime = System.nanoTime();

        Random random = new Random();
        for(int i = 0 ; i < opCount ; i ++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for(int i = 0 ; i < opCount ; i ++)
            q.dequeue();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");

        LinkedListQueue linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue, opCount);
        System.out.println("LinkedListQueue, time: " + time3 + " s");
    }
}

结果如下:

arrayQueue由于复杂度是n方级别的,所以时间最长,loopQueue和LinkedListQueue复杂度一样,时间差不多。

源码下载

[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

导航目录

[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(3.7)带有尾指针的链表:使用链表实现队列

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多