手撕Java集合之简易版Deque(LinkedList)

在���前，许多互联网公司的面试已经要求能手撕集合源码，集合源码本身算是源码里比较简单的一部分，但是要在面试极短的10来分钟内快速写出一个简易版的源码还是比较麻烦的，很容易出现各种小问题。所以在平时就要注重这方面的联系。

以下是我自己写的一个简易双端队列，我没有实现List接口，因为里面要实现的函数方法太多了，所以只是挑了几个核心的代码来写，本质其实就是头插法和尾插法的结合。

代码主要有三个文件，分别是Node节点，Deque类和测试文件。

Node:

package org.example.collection;import lombok.Data;import java.util.HashMap;import java.util.Map;@Datapublic class Node {    T var;    Node prev;    Node next;    Node(Node prev,T element, Node next){        this.var = element;        this.next = next;        this.prev = prev;    }}

Deque实现文件：

package org.example.collection;public class DequeCode{    int size = 0;    Node first;    Node last;    public DequeCode() {        this.first = new Node(null,null,null);        this.last = new Node(null,null,null);        //first和last之间应该建立联系        first.next = last;        last.prev = first;    }    public int size() {        return size;    }    public void addFirst(E element){        //采用头插法来进行双端的插入        Node node = new Node(null,element,null);        size++;        if(first.next==null){            first.next = node;            node.prev = first;            return ;        }        Node temp = first.next;        first.next = node;        node.prev = first;        node.next = temp;        temp.prev = node;    }    public void addLast(E element){        //和头插入相同的思路        Node node = new Node(null,element,null);        Node temp = last.prev;        size++;        if(last.prev==null){            last.prev = node;            node.next = last;            return ;        }        last.prev = node;        node.next = last;        temp.next = node;        node.prev = temp;    }    public void removeFirst() throws Exception {        if(size == 0) throw new Exception("出现问题");        Node node = first.next;        first.next = first.next.next;        node.next.prev = first;    }    public void removeLast() throws Exception {        if(size == 0) throw new Exception("出现问题");        Node node = last.prev;        last.prev = last.prev.prev;        node.prev.next = last;    }    public Node peekFirst(){        return first.next;    }    public Node peekLast(){        return last.prev;    }}

最后是测试文件：

package org.example.collection;public class TestDeque {    public static void main(String[] args) throws Exception {        DequeCode deque = new DequeCode();        deque.addFirst(1);        deque.addLast(2);        System.out.println(deque.peekFirst().var);        System.out.println(deque.peekLast().var);        deque.addFirst(3);        deque.addLast(4);        System.out.println(deque.peekFirst().var);        System.out.println(deque.peekLast().var);        deque.removeFirst();        deque.removeLast();        System.out.println(deque.peekFirst().var);        System.out.println(deque.peekLast().var);    }}

结果和预期一致

代码逻辑很简单，但是细节方面仍有很大的提升空间。但是面试时间短，这些代码能在10来分钟无失误写出，想来也是够用了。