目录

• 实现动态数组ArrayList
• 实现单链表
• 双向链表
• 双向循环链表
• 使用Array动态数组和链表实现栈
• 使用Array动态数组和链表实现队列
• 循环队列(LoopQueue)的实现

实现动态数组ArrayList

模拟实现ArrayList动态数组，包括的方法：

• rangeCheck()，检查数组下标是否越界；
• add()，在某个下标位置添加元素；
• resize()，动态扩容，当数组容量满或者空闲整个数组的3/4时，重新定义容量；
• get()，获取某个位置的元素值；
• set()，设置某个下标的元素值；
• contains()，查找是否包含某个元素；
• find()，找到某个元素的下标；
• remove()，移除某个下标对应的值；

public class Array<E> {

    private E[] data;
    private int size;

    public Array(int capacity){  //  user assign size
        data = (E[])new Object[capacity];
        size = 0;
    }
    public Array(){
        this(10); // default size
    }

    public int getSize(){
        return size;
    }
    public int getCapacity(){
        return data.length;
    }
    public boolean isEmpty(){
        return size == 0;
    }

    public void rangeCheck(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Index is Illegal!");
    }

    public void add(int index,E e){
         if(index < 0 || index > size){
            throw new IllegalArgumentException("Index is Illegal ! ");
	     }
        if(size == data.length)
            resize(data.length * 2);
        for(int i = size - 1; i >= index; i--){
            data[i+1] = data[i];
        }
        data[index] = e;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0; i < size; i++) newData[i] = data[i];
        data = newData;
    }

    public void addLast(E e){ //末尾添加
        add(size,e);
    }
    public void addFirst(E e){ //头部添加
        add(0,e);
    }


    public E get(int index){
        rangeCheck(index);
        return data[index];
    }
    public E getLast(){
        return get(size-1);
    }
    public E getFirst(){
        return get(0);
    }

    public void set(int index,E e){
        rangeCheck(index);
        data[index] = e;
    }

    public boolean contains(E e){
        for(int i = 0; i < size; i++){
            if(data[i].equals(e))return true;
        }
        return false;
    }
    public int find(E e){
        for(int i = 0; i < size; i++){
            if(data[i].equals(e))return i;
        }
        return -1;
    }


    public E remove(int index){  // remove data[index] and return the value
        rangeCheck(index);
        E res = data[index];
        for(int i = index; i < size-1; i++){
            data[i] = data[i+1];
        }
        size--;
        data[size] = null;//loitering objects  != memory  leak
        if(size == data.length / 4 && data.length/2 != 0)resize(data.length / 2); //防止复杂度的震荡
        return res;
    }

    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size-1);
    }


    public void removeElement(E e){ //only remove one(may repetition) and user not know whether is deleted.
        int index = find(e);
        if(index != -1){
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array : size = %d, capacity = %d\n",size,data.length));
        res.append("[");
        for(int i = 0; i < size; i++){
            res.append(data[i]);
            if(i != size-1){
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }
}

实现单链表

注意:

• 我使用了带头结点(dummyHead)的，也就是头结点的数据域不起作用；
• 这里我是以0开始的索引；

单链表的操作不是很难：

public class SingleList<E> {

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

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

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

    private Node dummyHead; //虚拟的头结点
    private int size; //表示链表当前的元素

    public SingleList() {
        dummyHead = new Node();
        size = 0;
    }

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

    public void rangeCheck(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Index is Illegal!");
    }

    //insert
    public void add(int index,E e){
       if(index < 0 || index > size){
            throw new IllegalArgumentException("Index is Illegal ! ");
        }
        Node prev = dummyHead; //设置虚拟头结点的目的是　为了插入和删除的方便(不需要判断第一个和最后一个位置)
        for(int i = 0; i < index; i++) prev = prev.next;
        Node node = new Node(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }
    public void addFirst(E e){
        add(0,e);
    }
    public void addLast(E e){
        add(size,e);
    }


    //获取
    public E get(int index) {
        rangeCheck(index);
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.val;
    }
    public E getFirst(){
        return get(0);
    }
    public E getLast(){
        return get(size - 1);
    }


    //remove
    public E remove(int index){
        rangeCheck(index);
        Node prev = dummyHead;
        for(int i = 0; i < index; i++) prev = prev.next;
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size--;
        return delNode.val;
    }
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size - 1);
    }


    public void set(int index,E e){
        rangeCheck(index);
        Node cur = dummyHead.next;
        for(int i = 0; i < index; i++)cur = cur.next;
        cur.val = e;
    }

    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.val.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void removeElement(E e){
        Node prev = dummyHead;
        while(prev.next != null){//找到对应e的　prev
            if(prev.next.val.equals(e)){
                break;
            }
            prev = prev.next;
        }

        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
        }
    }


    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        Node cur = dummyHead.next;
        while(cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");

        return res.toString();
    }



    //for test
    public static void main(String[] args) {
        SingleList<Integer> singleList = new SingleList<>();
        for(int i = 0 ; i < 5 ; i ++){
            singleList.addFirst(i);//头插
        }
        System.out.println(singleList);

        singleList.add(2, 666);
        System.out.println(singleList);

        singleList.remove(2);
        System.out.println(singleList);

        singleList.removeFirst();
        System.out.println(singleList);

        singleList.removeLast();
        System.out.println(singleList);

        singleList.removeElement(2);
        System.out.println(singleList);

        System.out.println(singleList.contains(3));

        singleList.set(1,999);
        System.out.println(singleList);

        singleList.addLast(888);
        System.out.println(singleList);

        System.out.println(singleList.getFirst() +" " +  singleList.getLast());
        System.out.println(singleList.size());
    }
}

运行效果如图:

双向链表

其实也挺简单的，看一下插入和删除的图示:

• 这里也是使用了一个头节点(dummyHead)；
• 索引从0开始；

/**
 * 双向链表
 * @param <E>
 */
public class DoubleList<E> {

    private class Node{
        public E val;
        public Node prev;
        public Node next;

        public Node(E val, Node prev, Node next) {
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
        public Node(E val){
            this(val,null,null);
        }
        public Node(){
            this(null,null,null);
        }

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

    private Node dummyHead;
    private int size;

    public DoubleList() {
        dummyHead = new Node();
        size = 0;
    }

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

    public void rangeCheck(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Index is Illegal!");
    }

    public void add(int index,E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Index is Illegal ! ");
        }
        Node pre = dummyHead;
        for(int i = 0; i < index; i++) pre = pre.next;
        Node node = new Node(e);
        Node nxt = pre.next;

        node.prev = pre;
        node.next = (nxt == null) ? null : nxt;
        pre.next = node;
        if(nxt != null)nxt.prev = node;
        size++;
    }
    public void addFirst(E e){
        add(0,e);
    }
    public void addLast(E e){
        add(size,e);
    }


    public E remove(int index){
        rangeCheck(index);
        if(isEmpty())return null;
        Node pre = dummyHead;
        for(int i = 0; i < index; i++) pre = pre.next;
        Node delNode = pre.next;
        pre.next = delNode.next;
        if(delNode.next != null)delNode.next.prev = pre;
        size--;
        return delNode.val;
    }
    public E removeFirst(){
        return remove(0);
    }
    public E removeLast(){
        return remove(size-1);
    }
    
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

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

        return res.toString();
    }

    public static void main(String[] args) {
        DoubleList<Integer> dulList = new DoubleList<>();
        for(int i = 0; i < 5; i++) dulList.addLast(i);
        System.out.println(dulList);

        dulList.removeLast();
        System.out.println(dulList);

        dulList.removeFirst();
        System.out.println(dulList);

        dulList.remove(1);
        System.out.println(dulList);

        dulList.addFirst(-1);
        dulList.add(1,666);
        System.out.println(dulList);

    }
}

效果：

双向循环链表

注意几点:

• 插入的时候要注意如果是在最后插入的话，可以直接通过dummyHead(虚拟头结点找到最后的)，然后直接插入；
• 在get的时候，可以判断一下从哪边开始查找，加快查找速度；

/**
 * 双向循环链表
 * @param <E>
 */
public class MyLinkedList<E>{

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

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

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

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

    private Node dummyHead;
    private Node tail;
    private int size;

    public MyLinkedList() {
        dummyHead = new Node();
        tail = dummyHead;
        //dummyHead自成一环
        dummyHead.next = tail;
        dummyHead.prev = tail;
        tail.next = dummyHead;
        tail.prev = dummyHead;
        size = 0;
    }

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

    //check index < 0 || index >= size
    public void rangeCheck(int index){
        if(index < 0 || index >= size){
            throw new IllegalArgumentException("Index is Illegal ! ");
        }
    }

    //add Last
    public void add(E e){
        Node node = new Node(e);
        node.prev = tail;
        node.next = dummyHead;
        tail.next = node;
        dummyHead.prev = node;
        tail = node;
        size++;
    }

    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Index is Illegal ! ");
        }
        if(index == size){ //add to Last
            add(e);
            return;
        }
        Node pre = dummyHead;
        for(int i = 0; i < index; i++)pre = pre.next;
        Node nxt = pre.next;
        Node node = new Node(e);
        node.prev = pre;
        node.next = nxt;
        pre.next = node;
        nxt.prev = node;
        size++;
    }

    // speed get
    public E get(int index){
        rangeCheck(index);
        Node cur = dummyHead;
        if(index < (size << 1)){
            for(int i = 0; i < index + 1; i++)cur = cur.next;
            return cur.e;
        }else {
            for(int i = 0; i < index + 1; i++)cur = cur.prev;
            return cur.e;
        }
    }


    public E removeLast(){
        E ret = tail.e;
        tail.prev.next = tail.next;
        tail.next.prev = tail.prev;
        tail = tail.prev;//改变tail
        size--;
        return ret;
    }

    public E remove(int index){
        rangeCheck(index);
        if(index == size - 1){
            return removeLast();
        }
        Node pre = dummyHead;
        for(int i = 0; i < index; i++)pre = pre.next;
        Node delNode = pre.next;

        pre.next = delNode.next;
        delNode.next.prev = delNode.prev;
        size--;
        return delNode.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node cur = dummyHead.next;
        while(cur != dummyHead){
            res.append(cur.e + "->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }


    public static void main(String[] args) {
        MyLinkedList<Integer>myLinkedList = new MyLinkedList<>();
        for(int i = 0; i < 5; i++){
            myLinkedList.add(i);
        }
        myLinkedList.add(0,-1);
        myLinkedList.add(1,999);
        myLinkedList.removeLast();
        System.out.println(myLinkedList);
        myLinkedList.remove(3);
        System.out.println(myLinkedList);
        System.out.println(myLinkedList.tail.next.next.e);
        System.out.println(myLinkedList.dummyHead.next.next.e);
        System.out.println(myLinkedList.tail.prev.e);
        System.out.println(myLinkedList.get(4));
    }
}

效果:

使用Array动态数组和链表实现栈

动态数组实现栈

public interface Stack<E> {
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();
}

public class ArrayStack<E> implements Stack<E> {

    private Array<E> array;

    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayStack(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void push(E e){
        array.addLast(e);
    }

    @Override
    public E pop(){
        return array.removeLast();
    }

    @Override
    public E peek(){
        return array.getLast();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: ");
        res.append('[');
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] top");
        return res.toString();
    }
}

链表实现栈:

public class SingListStack<E> implements Stack<E>  {

    private SingleList<E> list;

    public SingListStack(){
        list = new SingleList<>();
    }

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

    @Override
    public boolean isEmpty(){
        return list.isEmpty();
    }

    @Override
    public void push(E e){
        list.addFirst(e);
    }

    @Override
    public E pop(){
        return list.removeFirst();
    }

    @Override
    public E peek(){
        return list.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }
}

顺便提一下系统栈的应用以及方法的调用压栈过程:

• 系统栈中压入了之前的方法的所有信息，包括方法名，参数，运行到了第几行；
• 当后面的方法完全结束之后，从系统栈中弹出之前的方法，然后继续执行；

使用Array动态数组和链表实现队列

动态数组实现队列

public interface Queue<E> {
    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

    public ArrayQueue(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayQueue(){
        array = new Array<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void enqueue(E e){
        array.addLast(e);
    }

    @Override
    public E dequeue(){
        return array.removeFirst();
    }

    @Override
    public E getFront(){
        return array.getFirst();
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(int i = 0 ; i < array.getSize() ; i ++){
            res.append(array.get(i));
            if(i != array.getSize() - 1)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

链表实现队列:

• 注意为了dequeue的方便，增加了一个tail指针指向尾节点；
• 注意队列为空的情况要特判

public class SingleListQueue<E> implements Queue<E>{

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

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

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

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

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


    private Node head,tail;
    private int size;

    public SingleListQueue(){
        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 delNode = head;
        head = head.next;
        delNode.next = null;
        if(head == null) tail = null; //特判一下 维护tail指针
        size--;
        return delNode.val;
    }


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

    @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) {
        SingleListQueue<Integer>queue = new SingleListQueue<>();
        for(int i = 0 ; i < 5 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

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

效果:

循环队列的实现

• 注意循环队列的内置数组中要浪费一个空间用来区分队列空和满；
• 循环队列的出队操作比ArrayQueue要快很多，原因在于ArrayQueue出队要移动大量元素；

public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front,tail;
    private int size;


    public LoopQueue(int capacity) {
        data = (E[])new Object[capacity + 1];  //因为要浪费一个空间，所以在内部我们要多开辟一个空间
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue(){
        this(5);
    }

    public int getCapacity(){
        return data.length - 1; //因为我们多开了一个空间，所以返回的是data.length - 1
    }

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

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

    @Override
    public void enqueue(E e) {
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;//尾部指针变化
        size++;
    }

    @Override
    public E dequeue() {
        if(isEmpty()) throw new IllegalArgumentException("Queue is Empty! Can't delete!");
        E res = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if(size == getCapacity()/4 && getCapacity()/2 != 0){
            resize(getCapacity() / 2);
        }
        return res;
    }

    @Override
    public E getFront() {
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return data[front];
    }

    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0; i < size; i++){
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity()));
        res.append("front [");
        for(int i = front ; i != tail ; i = (i + 1) % data.length){ //实现方式二
            res.append(data[i]);
            if((i + 1) % data.length != tail) res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>();
        for(int i = 0 ; i < 5 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

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

效果: