//1.3.31

package com.qiusongde.linkedlist;

public class DoublyLinkedList<Item> {

    private DoublyNode<Item> first;

    private DoublyNode<Item> last;

    //can be accessed outside this class

    public static class DoublyNode<E>    {

        public E item;

        public DoublyNode<E> next;

        public DoublyNode<E> pre;

    }

    public DoublyLinkedList() {

        first = null;

        last = null;

    }

    /**

     * insert item at the beginning of the list

     *

     * @param list the list to insert

     * @param item the item to be inserted

     */

    public static <T> void insertAtBeginning(DoublyLinkedList<T> list, T item) {

        DoublyNode<T> oldfirst = list.first;//save old first node

        list.first = new DoublyNode<T>();//new first node

        list.first.item = item;//save item

        list.first.next = oldfirst;//point to oldfirst

        list.first.pre = null;//pre initialize to null

        if(oldfirst != null) {

            oldfirst.pre = list.first;

        } else {//oldfirst is null

            list.last = list.first;

        }

    }

    /**

     * insert item at the end of the list

     *

     * @param list the list to insert

     * @param item the item to be inserted

     */

    public static <T> void insertAtTheEnd(DoublyLinkedList<T> list, T item) {

        DoublyNode<T> oldlast = list.last;

        list.last = new DoublyNode<T>();

        list.last.item = item;

        list.last.next = null;

        list.last.pre = oldlast;

        if(oldlast == null) {

            list.first = list.last;

        } else {

            oldlast.next = list.last;

        }

    }

    /**

     * remove the first node in the list. If the first node in the list is null, then do nothing.

     *

     * @param list the list whose first node will be removed

     */

    public static <T> void removeFromBeginning(DoublyLinkedList<T> list) {

        if(list.first == null) {

            return;//do nothing

        }

        list.first = list.first.next;//new position for first

        if(list.first == null) {//not more leave

            list.last = null;

        } else {

            list.first.pre.next = null;

            list.first.pre = null;

        }

    }

    /**

     * remove the last node in the list. If the last node in the list is null, then do nothing.

     *

     * @param list the list whose last node will be removed

     */

    public static <T> void removeFromTheEnd(DoublyLinkedList<T> list) {

        if(list.last == null) {

            return;//do nothing

        }

        list.last = list.last.pre;

        if(list.last == null) {

            list.first = null;

        } else {

            list.last.next.pre = null;

            list.last.next = null;

        }

    }

    public static <T> DoublyNode<T> findDoublyNode(DoublyLinkedList<T> list, T item) {

        DoublyNode<T> current = list.first;

        while(current != null) {

            if(current.item.equals(item)) {

                break;

            }

            current = current.next;

        }

        return current;

    }

    /**

     * insert the item before the node in the list. if node is null or node isn't in the list, then do nothing.

     *

     * @param list the list in which the node is

     *

     * @param node the node before which the item will be inserted

     *

     * @param item the item to be inserted

     */

    public static <T> void insertBeforeNode(DoublyLinkedList<T> list, DoublyNode<T> node, T item) {

        if(node == null) {//do nothing

            return;

        }

        if(isInList(list, node)) {//node is in list

            DoublyNode<T> newnode = new DoublyNode<T>();

            newnode.item = item;

            newnode.next = node;

            if(node.pre != null) {//not first node in the list

                node.pre.next = newnode;

            } else {//first node in the list

                list.first = newnode;//change first node

            }

            newnode.pre = node.pre;

            node.pre = newnode;//should be last assign

        }

    }

    /**

     * insert the item after the node in the list. if node is null or node isn't in the list, then do nothing.

     *

     * @param list the list in which the node is

     *

     * @param node the node after which the item will be inserted

     *

     * @param item the item to be inserted

     */

    public static <T> void insertAfterNode(DoublyLinkedList<T> list, DoublyNode<T> node, T item) {

        if(node == null) {//do nothing

            return;

        }

        if(isInList(list, node)) {

            DoublyNode<T> newnode = new DoublyNode<T>();

            newnode.item = item;

            newnode.pre = node;

            if(node.next != null) {//not last node in the list

                node.next.pre = newnode;

            } else {//last node in the list

                list.last = newnode;

            }

            newnode.next = node.next;

            node.next = newnode;//should be last assign

        }

    }

    /**

     * remove the node in the list

     *

     * @param list the list in which the node is

     * @param node the node to be removed

     */

    public static <T> void removeNode(DoublyLinkedList<T> list, DoublyNode<T> node) {

        if(node == null) {

            return;

        }

        if(isInList(list, node)) {

            if(list.first == node) {

                removeFromBeginning(list);

            }

            else if(list.last == node) {

                removeFromTheEnd(list);

            }

            else {

                node.pre.next = node.next;

                node.next.pre = node.pre;

            }

        }

    }

    /**

     * see if the node is in the list

     *

     * @param list the list

     * @param node the node

     * @return {@code true} the node is in the list

     *            {@code false} the node isn't in the list

     */

    public static <T> boolean isInList(DoublyLinkedList<T> list, DoublyNode<T> node) {

        DoublyNode<T> current = list.first;

        while(current != null) {

            if(current == node) {

                return true;

            }

            current = current.next;

        }

        return false;

    }

    @Override

    public String toString() {

        String s = "";

        DoublyNode<Item> current = first;

        while(current != null) {

            s += current.item + " ";

            current = current.next;

        }

        s += first == null ? "first:null " : "first:" + first.item + " ";

        s += last == null ? "last:null " : "last:" + last.item + " ";

        return s;

    }

}

package com.qiusongde.linkedlist;

import com.qiusongde.linkedlist.DoublyLinkedList.DoublyNode;

import edu.princeton.cs.algs4.StdOut;

import edu.princeton.cs.algs4.StdRandom;

public class Exercise1331 {

    public static void main(String[] args) {

        DoublyLinkedList<Integer> list = new DoublyLinkedList<Integer>();

        StdOut.println("Initial doublylist:");

        StdOut.println(list);

        StdOut.println();

        //test insertAtBeginning function

        StdOut.println("Test insertAtBeginning function");

        for(int i = 1; i <= 10; i++) {

            DoublyLinkedList.insertAtBeginning(list, i);

            StdOut.println("insertAtBeginning success: " + i);

            StdOut.println(list);

        }

        StdOut.println();

        //test removeFromBeginning function

        StdOut.println("Test removeFromBeginning function");

        for(int i = 1; i <= 11; i++) {

            DoublyLinkedList.removeFromBeginning(list);

            StdOut.println("removeFromBeginning success: ");

            StdOut.println(list);

        }

        StdOut.println();

        //test insertAtTheEnd function

        StdOut.println("Test insertAtTheEnd function");

        for(int i = 1; i <= 10; i++) {

            DoublyLinkedList.insertAtTheEnd(list, i);

            StdOut.println("insertAtTheEnd success: " + i);

            StdOut.println(list);

        }

        StdOut.println();

        //test removeFromTheEnd function

        StdOut.println("Test removeFromTheEnd function");

        for(int i = 1; i <= 11; i++) {

            DoublyLinkedList.removeFromTheEnd(list);

            StdOut.println("removeFromTheEnd success: ");

            StdOut.println(list);

        }

        StdOut.println();

        //test insertBeforeNode function

        StdOut.println("Test insertBeforeNode function");

        for(int i = 1; i <= 10; i++) {

            DoublyLinkedList.insertAtBeginning(list, i);

        }

        StdOut.println("Initial list:");

        StdOut.println(list);

        for(int i = 0; i < 10; i++) {

            int number = StdRandom.uniform(10 + i) + 1;

            DoublyNode<Integer> node = DoublyLinkedList.findDoublyNode(list, number);

            DoublyLinkedList.insertBeforeNode(list, node, 11 + i);

            StdOut.println("insert " + (11+i) +  " BeforeNode " +  node.item + " success");

            StdOut.println(list);

        }

        StdOut.println();

        //test remove

        StdOut.println("Test removeNode function");

        for(int i = 0; i < 20; i++) {

            DoublyNode<Integer> node = DoublyLinkedList.findDoublyNode(list, i + 1);

            DoublyLinkedList.removeNode(list, node);

            StdOut.println("removeNode success:" + (i+1));

            StdOut.println(list);

        }

        StdOut.println();

        //test insertAfterNode function

        StdOut.println("Test insertAfterNode function");

        for(int i = 1; i <= 10; i++) {

            DoublyLinkedList.insertAtBeginning(list, i);

        }

        StdOut.println("Initial list:");

        StdOut.println(list);

        for(int i = 0; i < 10; i++) {

            int number = StdRandom.uniform(10 + i) + 1;

            DoublyNode<Integer> node = DoublyLinkedList.findDoublyNode(list, number);

            DoublyLinkedList.insertAfterNode(list, node, 11 + i);

            StdOut.println("insert " + (11+i) +  " AfterNode " +  node.item + " success");

            StdOut.println(list);

        }

        StdOut.println();

    }

}

Initial doublylist:

first:null last:null 

Test insertAtBeginning function

insertAtBeginning success: 1

1 first:1 last:1

insertAtBeginning success: 2

2 1 first:2 last:1

insertAtBeginning success: 3

3 2 1 first:3 last:1

insertAtBeginning success: 4

4 3 2 1 first:4 last:1

insertAtBeginning success: 5

5 4 3 2 1 first:5 last:1

insertAtBeginning success: 6

6 5 4 3 2 1 first:6 last:1

insertAtBeginning success: 7

7 6 5 4 3 2 1 first:7 last:1

insertAtBeginning success: 8

8 7 6 5 4 3 2 1 first:8 last:1

insertAtBeginning success: 9

9 8 7 6 5 4 3 2 1 first:9 last:1

insertAtBeginning success: 10

10 9 8 7 6 5 4 3 2 1 first:10 last:1 

Test removeFromBeginning function

removeFromBeginning success:

9 8 7 6 5 4 3 2 1 first:9 last:1

removeFromBeginning success:

8 7 6 5 4 3 2 1 first:8 last:1

removeFromBeginning success:

7 6 5 4 3 2 1 first:7 last:1

removeFromBeginning success:

6 5 4 3 2 1 first:6 last:1

removeFromBeginning success:

5 4 3 2 1 first:5 last:1

removeFromBeginning success:

4 3 2 1 first:4 last:1

removeFromBeginning success:

3 2 1 first:3 last:1

removeFromBeginning success:

2 1 first:2 last:1

removeFromBeginning success:

1 first:1 last:1

removeFromBeginning success:

first:null last:null

removeFromBeginning success:

first:null last:null 

Test insertAtTheEnd function

insertAtTheEnd success: 1

1 first:1 last:1

insertAtTheEnd success: 2

1 2 first:1 last:2

insertAtTheEnd success: 3

1 2 3 first:1 last:3

insertAtTheEnd success: 4

1 2 3 4 first:1 last:4

insertAtTheEnd success: 5

1 2 3 4 5 first:1 last:5

insertAtTheEnd success: 6

1 2 3 4 5 6 first:1 last:6

insertAtTheEnd success: 7

1 2 3 4 5 6 7 first:1 last:7

insertAtTheEnd success: 8

1 2 3 4 5 6 7 8 first:1 last:8

insertAtTheEnd success: 9

1 2 3 4 5 6 7 8 9 first:1 last:9

insertAtTheEnd success: 10

1 2 3 4 5 6 7 8 9 10 first:1 last:10 

Test removeFromTheEnd function

removeFromTheEnd success:

1 2 3 4 5 6 7 8 9 first:1 last:9

removeFromTheEnd success:

1 2 3 4 5 6 7 8 first:1 last:8

removeFromTheEnd success:

1 2 3 4 5 6 7 first:1 last:7

removeFromTheEnd success:

1 2 3 4 5 6 first:1 last:6

removeFromTheEnd success:

1 2 3 4 5 first:1 last:5

removeFromTheEnd success:

1 2 3 4 first:1 last:4

removeFromTheEnd success:

1 2 3 first:1 last:3

removeFromTheEnd success:

1 2 first:1 last:2

removeFromTheEnd success:

1 first:1 last:1

removeFromTheEnd success:

first:null last:null

removeFromTheEnd success:

first:null last:null 

Test insertBeforeNode function

Initial list:

10 9 8 7 6 5 4 3 2 1 first:10 last:1

insert 11 BeforeNode 7 success

10 9 8 11 7 6 5 4 3 2 1 first:10 last:1

insert 12 BeforeNode 8 success

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

insert 13 BeforeNode 10 success

13 10 9 12 8 11 7 6 5 4 3 2 1 first:13 last:1

insert 14 BeforeNode 10 success

13 14 10 9 12 8 11 7 6 5 4 3 2 1 first:13 last:1

insert 15 BeforeNode 2 success

13 14 10 9 12 8 11 7 6 5 4 3 15 2 1 first:13 last:1

insert 16 BeforeNode 4 success

13 14 10 9 12 8 11 7 6 5 16 4 3 15 2 1 first:13 last:1

insert 17 BeforeNode 12 success

13 14 10 9 17 12 8 11 7 6 5 16 4 3 15 2 1 first:13 last:1

insert 18 BeforeNode 7 success

13 14 10 9 17 12 8 11 18 7 6 5 16 4 3 15 2 1 first:13 last:1

insert 19 BeforeNode 15 success

13 14 10 9 17 12 8 11 18 7 6 5 16 4 3 19 15 2 1 first:13 last:1

insert 20 BeforeNode 9 success

13 14 10 20 9 17 12 8 11 18 7 6 5 16 4 3 19 15 2 1 first:13 last:1 

Test removeNode function

removeNode success:1

13 14 10 20 9 17 12 8 11 18 7 6 5 16 4 3 19 15 2 first:13 last:2

removeNode success:2

13 14 10 20 9 17 12 8 11 18 7 6 5 16 4 3 19 15 first:13 last:15

removeNode success:3

13 14 10 20 9 17 12 8 11 18 7 6 5 16 4 19 15 first:13 last:15

removeNode success:4

13 14 10 20 9 17 12 8 11 18 7 6 5 16 19 15 first:13 last:15

removeNode success:5

13 14 10 20 9 17 12 8 11 18 7 6 16 19 15 first:13 last:15

removeNode success:6

13 14 10 20 9 17 12 8 11 18 7 16 19 15 first:13 last:15

removeNode success:7

13 14 10 20 9 17 12 8 11 18 16 19 15 first:13 last:15

removeNode success:8

13 14 10 20 9 17 12 11 18 16 19 15 first:13 last:15

removeNode success:9

13 14 10 20 17 12 11 18 16 19 15 first:13 last:15

removeNode success:10

13 14 20 17 12 11 18 16 19 15 first:13 last:15

removeNode success:11

13 14 20 17 12 18 16 19 15 first:13 last:15

removeNode success:12

13 14 20 17 18 16 19 15 first:13 last:15

removeNode success:13

14 20 17 18 16 19 15 first:14 last:15

removeNode success:14

20 17 18 16 19 15 first:20 last:15

removeNode success:15

20 17 18 16 19 first:20 last:19

removeNode success:16

20 17 18 19 first:20 last:19

removeNode success:17

20 18 19 first:20 last:19

removeNode success:18

20 19 first:20 last:19

removeNode success:19

20 first:20 last:20

removeNode success:20

first:null last:null 

Test insertAfterNode function

Initial list:

10 9 8 7 6 5 4 3 2 1 first:10 last:1

insert 11 AfterNode 10 success

10 11 9 8 7 6 5 4 3 2 1 first:10 last:1

insert 12 AfterNode 9 success

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

insert 13 AfterNode 8 success

10 11 9 12 8 13 7 6 5 4 3 2 1 first:10 last:1

insert 14 AfterNode 10 success

10 14 11 9 12 8 13 7 6 5 4 3 2 1 first:10 last:1

insert 15 AfterNode 10 success

10 15 14 11 9 12 8 13 7 6 5 4 3 2 1 first:10 last:1

insert 16 AfterNode 4 success

10 15 14 11 9 12 8 13 7 6 5 4 16 3 2 1 first:10 last:1

insert 17 AfterNode 8 success

10 15 14 11 9 12 8 17 13 7 6 5 4 16 3 2 1 first:10 last:1

insert 18 AfterNode 11 success

10 15 14 11 18 9 12 8 17 13 7 6 5 4 16 3 2 1 first:10 last:1

insert 19 AfterNode 14 success

10 15 14 19 11 18 9 12 8 17 13 7 6 5 4 16 3 2 1 first:10 last:1

insert 20 AfterNode 3 success

10 15 14 19 11 18 9 12 8 17 13 7 6 5 4 16 3 20 2 1 first:10 last:1