Java单链表和双链表的反转及实现队列、栈和双端队列_双头链表反转java

一、简介

1.1 什么是单链表和双链表？

单链表：值、next指针（指向下一个节点）
双链表：值、next指针（指向下一个节点）、last指针（指向上一个节点）

1.2 定义一个单链表

 /**
     * 单节点：值、next指针
     */
    public static class Node{
        public int value;
        public Node next;

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

1
2
3
4
5
6
7
8
9
10
11
12

1.3 定义一个双链表

  /**
     * 双节点：值、last指针、next指针
     */
    public static class DoubleNode{
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data){
            this.value = data;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

二、单链表和双链表的反转

2.1 单链表的反转

/**
     * 反转单链表
     * head
     *  |
     *  1 -> 2 -> 3 -> null
     *
     *  null <- 1 <- 2 <- 3
     *                    head
     * @param head
     * @return
     */
    public static Node reverseLinkedList(Node head){
        Node pre = null;
        Node next = null;
        /**
         * 反转单链表： 1 -> 2 -> 3 -> null
         * head为1时：
         * 1 的 next指针为 2
         * 反转时，先将next指针保留为next
         * 然后将 1 的next指针指向 null
         * 将当前head（1） 记录为 pre（上一个）
         * 将next （2） 记录为 head
         * -------------------
         * head为2时： pre 为 1
         * 将head（2）的next指针保留为next
         * 将head（2）的next指针指向pre
         * 将head（2）记录为pre
         * 将head（2）记录为next（3）
         * -------------------
         * head为3时：pre为2 同上，但是head（3）记录为next（null）
         * -------------------
         * head 为 null 结束循环，同时返回pre：此时head为3
         *
         */
        while (head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

2.2 双链表的反转

 /**
     * 反转双链表
     * head
     * null <- 1 <-> 2 <-> 3 -> null
     *
     * null <- 1 <-> 2 <-> 3 -> null
     *                     head
     * @param head
     * @return
     */
    public static DoubleNode reverseDoubleLinkedList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null){
            /**
             * 首先head为 1 时： pre 为null
             * 此时记录head（1）的next（2）指针
             * 把 head（1）的next指针指向pre（null）
             * 把 head（1）的last指针指向next（2）
             * 将 pre 记录为 head（1）
             * 将 head 记录为 next（2）
             * ----------------------------------
             * 当head为2时：pre为1
             * 记录head（2）的 next（3）指针，
             * 将head（2）的next指向pre（1）
             * 将head（2）的last指针指向next（3）
             * 再将 pre（此时为1） 记录为 head  2
             * 将 head（此时为2） 记录为 next（3）
             * ----------------------------------
             * 当head为3时：pre为2
             * 记录 head（3）的next指针（null）
             * 将 head（3）的next指针指向pre （2）
             * 将 head（3）的last指针指向next （null）
             * 把 pre（此时为2）记录为 head（3）
             * 把 head（此时为3）记录为 next（null）
             * ----------------------------------
             * 当head为null， 结束循环。
             *
             */
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

2.3 测试

 public static void main(String[] args) {
        Node n1 = new Node(1);
        n1.next = new Node(2);
        n1.next.next = new Node(3);
        // 123 -> 321
        n1 = reverseLinkedList(n1);
        while (n1 != null){
            System.out.print(n1.value+" ");
            n1 = n1.next;
        }
        System.out.println();
        System.out.println("============");
        DoubleNode d1 = new DoubleNode(1);
        d1.next = new DoubleNode(2);

        d1.next.next = new DoubleNode(3);
        d1.next.last = d1;
        d1 = reverseDoubleLinkedList(d1);
        while (d1 != null){
            System.out.print(d1.value+" ");
            d1 = d1.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、单链表结构实现队列

3.1 什么是队列

队列的特点：先进先出，正常的排队顺序。

3.2 单链表结构实现队列

 public static class Node<V>{
        public V value;
        public Node<V> next;

        public Node(V v){
            this.value = v;
            this.next = null;
        }
    }

1
2
3
4
5
6
7
8
9
10

 public static class MyQueue<V>{
        //三个属性
        //头
        private Node<V> head;
        //尾
        private Node<V> tail;
        //大小
        private int size;

        //无参构造
        public MyQueue(){
            this.head = null;
            this.tail = null;
            this.size = 0;
        }

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

        public int size(){
            return size;
        }

        /**
         * 入队
         * @param value
         */
        public void offer(V value){
            Node<V> cur = new Node<>(value);
            if (tail == null){
                head = cur;
                tail = cur;
            }else {
                tail.next = cur;
                tail = cur;
            }
            size++;

        }

        /**
         * 弹出元素
         * @return
         */
        public V  poll(){
            V ans = null;
            if (head != null){
                ans = head.value;
                head = head.next;
                size--;
            }
            if (head == null){
                tail = null;
            }
            return ans;

        }

        /**
         * 查看队列尾部的元素
         * @return
         */
        public V peek(){
            V ans = null;
            if (head !=  null){
                ans = head.value;
            }
            return ans;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

3.3 对数器验证

 /**
     * 队列 对数器
     */
    public static void testQueue() {
        MyQueue<Integer> myQueue = new MyQueue<>();
        Queue<Integer> test = new LinkedList<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            if (myQueue.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myQueue.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                myQueue.offer(num);
                test.offer(num);
            } else if (decide < 0.66) {
                if (!myQueue.isEmpty()) {
                    int num1 = myQueue.poll();
                    int num2 = test.poll();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myQueue.isEmpty()) {
                    int num1 = myQueue.peek();
                    int num2 = test.peek();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (myQueue.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!myQueue.isEmpty()) {
            int num1 = myQueue.poll();
            int num2 = test.poll();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }

    public static void main(String[] args) {
        testQueue();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

四、单链表结构实现栈

4.1 什么是栈

栈的特点：先进后出，可以理解为弹夹，最先压入的子弹最后打出去。

4.2 单链表结构实现栈

   /**
     * 2. 单链表实现栈结构
     * @param <V>
     */
    public static class MyStack<V>{
        private Node<V>  head;
        private int size;

        public MyStack(){
            this.head = null;
            this.size = 0;
        }

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

        public int size(){
            return size;
        }

        /**
         * 入栈
         * @param value
         */
        public void push(V value){
            Node cur = new Node(value);
            if (head == null){
                //如果栈为空， 则head = cur
                head = cur;
            }else {
                //如果栈不为空，则cur的next指向当前head，并且head记录为cur
                cur.next = head;
                head = cur;
            }
            size++;
        }

        /**
         * 弹出栈元素
         * @return
         */
        public V pop(){
            V ans = null;
            if (head != null){
                //如果栈不为空，则直接返回head的value，并且head记录为head的next指针。
                ans = head.value;
                head = head.next;
                size--;
            }
            return ans;
        }

        public V peek(){
            return head.value == null ? null:head.value;
        }

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

4.3 对数器验证

 /**
     * 栈 对数器
     */
     public static void testStack() {
        MyStack<Integer> myStack = new MyStack<>();
        Stack<Integer> test = new Stack<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            if (myStack.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myStack.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                myStack.push(num);
                test.push(num);
            } else if (decide < 0.66) {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.pop();
                    int num2 = test.pop();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.peek();
                    int num2 = test.peek();
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (myStack.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!myStack.isEmpty()) {
            int num1 = myStack.pop();
            int num2 = test.pop();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
     }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

    public static void main(String[] args) {
        testStack();
    }
1
2
3

五、双链表结构实现双端队列

5.1 什么是双端队列

双端队列：即从队列头部和尾部都可以入队元素和出队元素。

5.2 代码实现

public static class MyDoubleQueue<V>{
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public MyDoubleQueue(){
            head = null;
            tail = null;
            size = 0;
        }

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

        /**
         * 从头部加元素
         * @param v
         */
        public void lpush(V v){
            Node<V> cur = new Node<>(v);
            //队列为空
            if (head == null){
                head = cur;
                tail = cur;
            }else {
                //队列不为空    head
                //     null     1   2   3   null
                //null   4(cur)   1   2   3   null
                //      head
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size ++;
        }

        /**
         * 从头部弹出元素
         * @return
         */
        public V lpop(){
            V ans = null;
            //队列为空
            if(head == null){
                return ans;
            }
            //队列不为空，弹出一个元素，队列大小-1
            size -- ;
            ans = head.value;
            //队列只有一个元素，弹出元素后，head和tail 置空
            if (head == tail){
                head = null;
                tail = null;
            }else {
                //队列中存在两个及以上元素，弹出头部元素后，head移动到next指针，并将此时的head的last置为null。
                head = head.next;
                head.last = null;
            }
            return ans;
        }

        /**
         * 从尾部加入元素
         * @param v
         */
        public void rpush(V v){
            Node<V> cur = new Node<>(v);
            if (tail == null){
                //如果队列为空
                head = cur;
                tail = cur;
            }else {
                //队列不为空                 tail
                // null     1       2       3       null
                // null     1       2       3       4       null
                //                                  tail
                cur.last = tail;
                tail.next = cur;
                tail = cur;
            }
            size ++;
        }
        public V rpop(){
            V ans = null;
            if (tail == null){
                return ans;
            }
            size --;
            ans = tail.value;
            if (head == tail){
                head = null;
                tail = null;
            }else {
                tail = tail.last;
                tail.next = null;
            }
            return ans;

        }
        
        public V lpeek(){
            return head == null ? null : head.value;
        }
        public V rpeek(){
            return tail == null ? null : tail.value;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112