Java用链表实现双端队列

2024-03-29

这是笔者通过 ucb cs61b 18fall 自学数据结构完成proj1三个部分后写的笔记，笔者的实现放在了笔者的github仓库,供参考。本文旨在记录个人的学习过程。笔者非 CS 科班出身，也没有什么过人的脑力，如果文章的实现和思路有错误，欢迎指出。如果想参考更好的代码，可以移步这个北大大佬的github仓库

关于CS61B 18fall proj1

这个project在课程中分为了三个Part：

PartA是让你写一个双端队列(Deque)的实现，并且要求分别用链表和数组实现，笔者比较懒很笨，只写了链表的实现，数组的实现可以参考上面的仓库或者网络，课程后面也会在proj1 gloden里面给出一个正确的套娃链表实现的数组实现，很有意思。本文章暂时分享到PartA，PartB和Golden其实并没有那么PartA那么难(也可能是写上手了)
PartB是让你用写好的Deque作为数据结构写一个回文检查器，额外要实现的功能是“OffByN”即能判断差值为N的回文
Part Golden是让你写一个PartA的autograder

除此之外，从PartB开始，还会要求你给你的代码自己写test。

实现LinkListDeque的主要思路

笔者认为这是proj1中最难的一部分，课程中给出了Deque的定义然后让学生手搓这个数据结构。笔者是一边盯着ppt中给出的图示一边敲出这个数据结构的：

根据看图理解后得到的信息完成这个数据结构整体的要点大概有：

在队列初始化时创建一个哨兵(sentinel)节点，这个节点始终在队列的最前端且不会被类里的任何方法访问
每个节点都有prev和next两个成员，用于实现对前后两个节点的引用，图中的每一个箭头都是要实现的
sentinel节点初始化时，它的prev端和next端指向自己
对所有其他节点的访问都可以通过递归访问sentinel的next和prev来实现(比如想访问第三个节点，那么就是sentinel.next.next.next)，这点很重要

结合以上三点可以就可以写出Deque的构造函数了，再深入思考增删改查等方法时你应该想到：

实现核心的Add和Remove方法时，要注意prev和next的引用(指向)的修改。比如addFirst的时候要断开原头节点prev部分与sentinel节点next部分的互相连接，并将原头节点的prev部分与新头节点的next部分互相连接，还要将新节点的prev部分与sentinel的next部分进行互相连接。可能有点晕，笔者当时是把每一步都画图一步步把代码写下来的
增删后记得检查是否实现了图中每一条箭头

接下来是笔者的实现

构造函数：

public class Node {
        private T value;
        private Node prev;
        private Node next;

        public Node(T x, Node pre, Node nex) {
            value = x;
            next = nex;
            prev = pre;
        }
    }
    public Node sentinel;
    public int size;
    public LinkedListDeque() {
        T meaningless = null;
        //初始化sentinel，让prev和next都指向自己
        sentinel = new Node(meaningless, null, null);
        sentinel.prev = sentinel;
        sentinel.next = sentinel;
        //sentinel节点不算入size
        size = 0;
    }

判断Deque是否为空：

// 当只有sentinel节点时，Deque为空
   public boolean isEmpty() {
        return sentinel.next == sentinel;
    }

增删(Add，Remove)：

public void addFirst(T x) {
        size += 1;
        //创建新头节点
        Node Newnode = new Node(x, null, null);
        //新头节点prev指向sentinel
        Newnode.prev = sentinel;
        //新头节点next指向原头节点(现在还被sentinel.next所引用)
        Newnode.next = sentinel.next;
        //原头节点的prev指向新头节点
        sentinel.next.prev = Newnode;
        //最后断开原来sentinel.next对原头节点的引用，让sentinel.next的引用变为新头节点。这一步要放在最后进行，否则会在前几步的修改中丢失对原头节点的引用
        sentinel.next = Newnode;
    }

//下面代码同理，不再注释
public void addLast(T x) {
        size += 1;
        Node Newnode = new Node(x, null, null);
        Newnode.prev = sentinel.prev;
        Newnode.next = sentinel;
        sentinel.prev.next = Newnode;
        sentinel.prev = Newnode;
    }

public T removeFirst() {
        if (sentinel.next == null) {
            return null;
        }
        Node dropOne;
        dropOne = sentinel.next;
        sentinel.next.next.prev = sentinel;
        sentinel.next = sentinel.next.next;
        size --;
        return dropOne.value;
    }

public T removeLast() {
        if (sentinel.prev == null) {
            return null;
        }
        Node dropOne;
        dropOne = sentinel.prev;
        sentinel.prev.prev.next = sentinel;
        sentinel.prev = sentinel.prev.prev;
        size --;
        return dropOne.value;
    }

能写到这里，基本上之后的一些方法比如printDeque或者get的都很简单了，无非是选择迭代或者递归。
另外两个part有缘再写吧。