CS61B sp21fall Project01

项目内容

分别用List和Array实现一个双端队列

补充知识

Java中包的概念：在Java中，包的作用是将为了实现同一个目标的类都聚在一起。
其他项目相关的补充知识我放在文章末尾的链接里面，打开网页就能看到。

实现逻辑

addFirst方法

public void addFirst(T x) {
        Node newNode = new Node(x);
        if (isEmpty()) {
            sentinel.next = newNode;
            newNode.prev = sentinel;
            newNode.next = sentinel;
            sentinel.prev = newNode;
        } else {
            newNode.next = sentinel.next;
            newNode.prev = sentinel;
            sentinel.next.prev = newNode;
            sentinel.next = newNode;
        }
        size += 1;
    }

这里使用了模板（Template），方便添加元素的时候不用变换元素。

1. 判断当前的双端链表是否为空
2. 如果是空的，将头和尾指针都指向自己
3. 如果不是空的，就用传统头插法，我的理解就是把原来的两个节点之间撕开再把新节点插进空隙
4. 链表的大小加一

addLast方法

public void addLast(T x) {
        Node newNode = new Node(x);
        if (isEmpty()) {
            sentinel.next = newNode;
            newNode.prev = sentinel;
            newNode.next = sentinel;
            sentinel.prev = newNode;
        } else {
            newNode.next = sentinel;
            newNode.prev = sentinel.prev;
            sentinel.prev.next = newNode;
            sentinel.prev = newNode;
        }
        size += 1;
    }

整体思路跟头插法相似，唯一不同的就是在不是空的时候哨兵（sentinel）的指向有所不同

isempty方法

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

size方法

public int size() {
        return size;
    }

printDeque方法

public void printDeque() {
        Node p = sentinel.next;
        while (p != sentinel) {
            System.out.print(p.item + " ");
            p = p.next;
        }
        System.out.println();
    }

这里由于官网没有给出时间限制的要求，直接简单暴力遍历即可，从哨兵节点开始向后遍历。

removeFirst方法

public T removeFirst() {
        if (isEmpty()) {
            return null;
        }
        Node p = sentinel.next;
        sentinel.next = p.next;
        p.next.prev = sentinel;
        size -= 1;
        return p.item;
    }

由于官网给出了时间限制，因此不能通过简单遍历的方式进行元素的删除。
这里参考增加时候使用的方法
1.判断链表是否为空
2.直接移除sentinel节点后面的那个节点
3.如果不存在这个节点那么就返回元素的值（初始值就是null）

removeLast方法

public T removeLast() {
        if (isEmpty()) {
            return null;
        }
        Node p = sentinel.prev;
        sentinel.prev = p.prev;
        p.prev.next = sentinel;
        size -= 1;
        return p.item;
    }

殊途同归

get方法

public T get(int index) {
        if (index >= size) {
            return null;
        }
        Node p = sentinel.next;
        while (index > 0) {
            p = p.next;
            index -= 1;
        }
        return p.item;
    }

简单遍历，找到想找到的直接返回就行。

附加题

public Iterator<T> iterator() {
        return new LinkedListDequeIterator();
    }
    private class LinkedListDequeIterator implements Iterator<T> {
        private Node p;
        public LinkedListDequeIterator() {
            p = sentinel.next;
        }
        public boolean hasNext() {
            return p != sentinel;
        }
        public T next() {
            T item = p.item;
            p = p.next;
            return item;
        }
    }
    //判断两个链表是否相等，包括大小和元素
    public boolean equals(Object o) {
        if (o == null) {
            return false;
        }
        if (o.getClass() != LinkedListDeque.class) {
            return false;
        }
        LinkedListDeque<T> other = (LinkedListDeque<T>) o;
        if (other.size() != size) {
            return false;
        }
        Node p = sentinel.next;
        Node q = other.sentinel.next;
        while (p != sentinel) {
            if (!p.item.equals(q.item)) {
                return false;
            }
            p = p.next;
            q = q.next;
        }
        return true;
    }

这里实现了一个迭代器，同时完成了一个判断两个链表是否相同的方法，重点是这里使用了一个类型转换的方法！

ArrayList

ArrayList部分的原理是一样的，代码放在下面，需要的可以自取。

代码链接

我的所有实现代码链接
如果感觉不错的话欢迎交流！