数据结构与算法-双向链表

package *;

/**
 * @program: data-structure
 * @description: 双向链表
 * @author: ChenWenLong
 * @create: 2019-09-10 09:33
 **/
public class MyDoubleLinkedList<T> {

    //头
    private Node<T> first;
    //尾
    private Node<T> last;

    public MyDoubleLinkedList(){
        first = null;
        last = null;
    }

    private class Node<T> {
        T data;
        Node<T> previous;
        Node<T> next;
        public Node(T data) {
            this.data = data;
        }

        public void display() {
            System.out.println(String.valueOf(data));
        }
    }

    /**
     * 功能描述:
     * 〈从头新增数据〉
     *
     * @params : [value]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 9:59
     */
    public void insertFirst(T value){
        Node newNode = new Node(value);
        if (first == null) {
            last = newNode;
        }else {
            first.previous = newNode;
            //把first节点往下移动
            newNode.next = first;
        }
        //把插入的节点作为新的节点
        first = newNode;
    }

    /**
     * 功能描述:
     * 〈从尾部新增数据〉
     *
     * @params : [value]
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:00
     */
    public void insertLast(long value){
        Node newNode = new Node(value);
        if (first == null) {
            first = newNode;
        }else {
            last.next = newNode;
            //first.previous = newNode;
            newNode.previous = last;
        }
        //把最后个节点设置为最新的节点
        last = newNode;
    }

    /**
     * 功能描述:
     * 〈判断当前链表是否为空〉
     *
     * @params : []
     * @return : boolean
     * @author : cwl
     * @date : 2019/9/10 10:00
     */
    public boolean isEmpty(){
        return first == null;
    }

    /**
     * 功能描述:
     * 〈删除第一个节点〉
     *
     * @params : []
     * @return : com.cwl.data.link.MyDoubleLinkedList<T>.Node
     * @author : cwl
     * @date : 2019/9/10 10:01
     */
    public Node deleteFirst(){
        if (first == null) {
            throw new RuntimeException("链表数据不存在");
        }
        Node temp = first;
        if (first.next == null) {
            last = null;
        }else {
            first.next.previous = null;
        }
        first = temp.next;
        return temp;
    }

    /**
     * 功能描述:
     * 〈删除最后一个节点〉
     *
     * @params : []
     * @return : com.cwl.data.link.MyDoubleLinkedList<T>.Node
     * @author : cwl
     * @date : 2019/9/10 10:01
     */
    public Node deleteLast(){
        if (first == null) {
            throw new RuntimeException("链表数据不存在");
        }

        Node temp = last;
        if (first.next == null) {
            last = null;
            //把第一个删除
            first = null;
        }else {
            last.previous.next = null;
        }
        last = temp.previous;
        return temp;
    }

    /**
     * 功能描述:
     * 〈删除指定节点〉
     *
     * @params : [key]
     * @return : com.cwl.data.link.MyDoubleLinkedList<T>.Node<T>
     * @author : cwl
     * @date : 2019/9/10 10:02
     */
    public Node<T> deleteByKey(T key){
        Node<T> current = first;
        while(current.data != key){
            if (current.next == null) {
                System.out.println("没找到节点");
                return null;
            }
            current = current.next;
        }
        if (current == first) {
            //return deleteFirst();
            //指向下个就表示删除第一个
            first = first.next;
        }else {
            current.previous.next = current.next;
        }
        return current;
    }

    /**
     * 功能描述:
     * 〈打印所有的节点数据〉
     *
     * @params : []
     * @return : void
     * @author : cwl
     * @date : 2019/9/10 10:03
     */
    public void display(){
        if (first == null) {
            //throw new RuntimeException("链表数据不存在");
            return;
        }
        Node<T> current = first;
        while(current != null){
            current.display();
            current = current.next;
        }
        System.out.println("---------------");
    }

    /**
     * 功能描述:
     * 〈根据数据内容查找指定节点〉
     *
     * @params : [value]
     * @return : com.cwl.data.link.MyDoubleLinkedList<T>.Node<T>
     * @author : cwl
     * @date : 2019/9/10 10:04
     */
    public Node<T> findByValue(T value){
        Node<T> current = first;
        while(current != null){
            if (current.data != value) {
                current = current.next;
            }else {
                break;
            }
        }
        if (current == null) {
            System.out.println("没找到");
            return null;
        }
        return current;
    }

    /**
     * 功能描述:
     * 〈根据节点找节点〉
     *
     * @params : [key]
     * @return : com.cwl.data.link.MyDoubleLinkedList<T>.Node<T>
     * @author : cwl
     * @date : 2019/9/10 10:07
     */
    public Node<T> findByKey(T key) {
        Node<T> current = first;
        while (current.data != key) {
            if (current.next == null) {
                System.out.println("没找到");
                return null;
            }
            current = current.next;
        }
        return current;
    }

    /**
     * 功能描述:
     * 〈根据位置找到某个节点〉
     *
     * @params : [position]
     * @return : com.cwl.data.link.MyDoubleLinkedList<T>.Node<T>
     * @author : cwl
     * @date : 2019/9/10 10:07
     */
    public Node<T> findByPosition(int position){
        Node<T> current = first;
        //为什么是position - 1，因为要使用遍历，让current指向下一个， 所以position - 1的下个node就是要找的值
        for (int i = 0; i < position - 1 ; i++) {
            current  = current.next;
        }
        return current;
    }

}