数据结构与算法：链表，队列，栈

反转单链表，双链表

import java.util.ArrayList;
import java.util.List;

public class ReverseList {

    public static class Node{
        public int value;
        public Node next;

        public Node(int data){
            value = data;
        }
    }

    public static class DoubleNode{
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data){
            value = data;
        }
    }

    // 利用双指针，反转单链表
    // head   a - > b - > c - > d - > e - > null
    public static Node reverselinkedList(Node head){
        Node pre = null;
        Node next = null;

        while(null != head){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    // 反转双向链表
    public static DoubleNode reverseDoubleList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }

        return pre;
    }

    public static Node testReverselinkedList(Node head){
        if(null == head){
            return null;
        }

        ArrayList list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        int N = list.size();
        for (int i = 1; i < N; i++) {
            list.get(i).next = list.get(i-1);
        }
        return list.get(N-1);
    }

    public static Node generateRandomlinkedList(int len, int value){
        int size = (int)(Math.random() * (len+1));
        if(size == 0){
            return null;
        }

        size--;
        Node head = new Node((int)(Math.random())*(value+1));
        Node pre = head;
        while(size != 0){
            Node cur = new Node((int)(Math.random())*(value+1));
            pre.next = cur;
            pre = cur;
            size--;
        }

        return head;
    }

    public static List getlinkedListOriginOrder(Node head){
        List ans = new ArrayList<>();
        while(head != null){
            ans.add(head.value);
            head = head.next;
        }

        return ans;
    }

    public static boolean checklinkedListReverse(List origin, Node head){
        for (int i = origin.size()-1; i >= 0 ; i--) {
            if(!origin.get(i).equals(head.value)){
                return false;
            }

            head = head.next;
        }

        return true;
    }

    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 100000;
        System.out.println("test Begin!!");
        for (int i = 0; i < testTime; i++) {
            Node node1 = generateRandomlinkedList(len,value);
            List list1 = getlinkedListOriginOrder(node1);
            node1 = reverselinkedList(node1);
            if(!checklinkedListReverse(list1,node1)){
                System.out.println("Oops1!");
            }

        }

        System.out.println("test end!!");
    }

// 删除链表中值等于num的节点
    public static Node removevalue(Node head, int num){
        while(null != head){
            // 来到第一个不需要删的位置
            if(head.value != num){
                break;
            }

            head = head.next;
        }

        Node pre = head;
        Node cur = head;
        while(cur != null){
            if(cur.value == num){
                pre.next = cur.next;
            }else{
                pre = cur;
            }
            cur = cur.next;
        }

        return head;
    }
}

数组和链表都能实现队列和栈。

双端链表实现队列

public class DoubleEndsQueueToStackAndQueue {
    public static class Node{
        public T value;
        public Node last;
        public Node next;

        public Node(T data){
            value = data;
        }
    }

    // 双端队列
    public static class DoubleEndsQueue{
        public Node head; // 头指针
        public Node tail; // 尾指针

        // 从头部加
        public void addFromHead(T value){
            Node cur = new Node(value);
            if(head == null){
                head = cur;
                tail = cur;
            }else{
                head.last = cur;
                cur.next = head;
                head = cur;
            }
        }

        // 从尾部加
        public void addFromBottom(T value){
            Node cur = new Node(value);
            if(tail == null){
                head = cur;
                tail = cur;
            }else{
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
        }

        // 从头部弹出来
        public T popFromHead(){
            if(head == null){
                return null;
            }
            Node cur = head;
            if(head == tail){
                tail = null;
                head = null;
            }else{
                head = head.next;
                cur.next = null;
                head.last = null;
            }

            return cur.value;
        }

        // 从尾部弹出来
        public T popFromTail(){
            if(head == null){
                return null;
            }

            Node cur = tail;
            if(head == tail){
                tail = null;
                head = null;
            }else{
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }

            return cur.value;
        }
    }

    public static void main(String[] args) {

    }
}