当前位置：首页 > news >正文

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

news 2025/8/25 2:05:27

在目前，许多互联网公司的面试已经要求能手撕集合源码，集合源码本身算是源码里比较简单的一部分，但是要在面试极短的10来分钟内快速写出一个简易版的源码还是比较麻烦的，很容易出现各种小问题。所以在平时就要注重这方面的联系。
以下是我自己写的一个简易双端队列，我没有实现List接口，因为里面要实现的函数方法太多了，所以只是挑了几个核心的代码来写，本质其实就是头插法和尾插法的结合。
代码主要有三个文件，分别是Node节点，Deque类和测试文件。
Node:

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

Deque实现文件：

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

最后是测试文件：

package org.example.collection;public class TestDeque {public static void main(String[] args) throws Exception {DequeCode<Integer> 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);}
}