双向数据链表

话不多说上代码

/**
 * 双向链表
 */
public class TwoWayLinkedList<T> {

    private class Node {
        private T data; // 节点数据
        private Node next; // 下一个节点
        private Node pre; // 上一个节点

        public Node(T data) {
            this.data = data;
        }
    }

    private Node head; // 链表头节点
    private Node tail; // 链表尾节点
    private int size; // 链表节点数量
    public TwoWayLinkedList(){
        head = null;
        tail = null;
        size = 0;
    }

    // 在链表头增加节点
    public boolean addHead(T data){
        try {
            // 构建新节点
            Node newNode = new Node(data);
            // 如果链表没有数据
            // 链表头节点和尾节点都指向新创建节点
            if (size == 0) {
                head = newNode;
                tail = newNode;
            } else {
                // 首先将原本头节点的上一个节点设置为 新节点
                head.pre = newNode;
                // 由于头节点没有上一个节点只有 next 节点
                // 将新节点的 next 指向旧的头节点
                newNode.next = head;
                // 再将头节点更新为新创建的节点
                head = newNode;
            }
            size++;
        }catch (Exception e){
            e.printStackTrace();
            return false;
        }
        return true;
    }

    // 在链表的尾部添加节点
    public boolean addTail(T data){
        try{
            // 构建新的节点
            Node newNode = new Node(data);
            // 如果没有节点
            // 头节点和尾节点都是新创建的节点
            if(size == 0){
                head = newNode;
                tail = newNode;
            }else{
                // 由于新创建的节点要添加到尾部
                // 所以新创建的节点的上一个节点就一年是原本的尾节点
                newNode.pre = tail;
                // 原本的尾节点的下一个节点应该是新创建的节点
                tail.next = newNode;
                // 尾节点就是 新创建的节点
                tail = newNode;
            }
            size ++;
        }catch (Exception e){
            e.printStackTrace();
            return false;
        }
        return true;
    }

    // 删除链表头节点 返回删除的节点
    public Node deleteHead(){
        Node deleNode = head;
        if(size > 0){
            // 将头节点设置为 头节点的 next 下一个节点
            head = head.next;
            // 由于头节点没有上一个节点，所以将头节点的 pre 上一个节点清空
            head.pre = null;
            size --;
        }
        return deleNode;
    }

    // 删除链表尾节点
    public Node deleteTail(){
        Node deleNode = tail;
        if(size > 0){
            // 将尾节点设置成为原本尾节点的上一个节点
            tail = tail.pre;
            // 由于尾节点没有 next 下一个节点，所以将其设置为 null
            tail.next = null;
            size --;
        }
        return deleNode;
    }

    // 获得链表的节点个数
    public int getSize(){
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 显示节点的信息
    public void display(){
        if(size > 0){
            Node curr = head;
            int tempSize = size;
            while (tempSize > 0){
                // 如果是头节点
                if(curr.equals(head)){
                    System.out.print("["+curr.data+"->");
                }else if(curr.next == null){
                    // 已经没有节点了
                    System.out.print(curr.data+"]");
                }else {
                    System.out.print(curr.data+"->");
                }
                curr = curr.next;
                tempSize --;
            }
            System.out.println();
        }else {
            // 无节点信息
            System.out.println("[]");
        }
    }

    public static void main(String[] args) {
        TwoWayLinkedList<String> twoWayLinkedList = new TwoWayLinkedList<String>();
        System.out.println("********************  添加尾节点  ********************");
        twoWayLinkedList.addTail("A");
        twoWayLinkedList.addTail("B");
        twoWayLinkedList.addTail("C");
        twoWayLinkedList.addTail("D");
        twoWayLinkedList.addTail("E");
        twoWayLinkedList.display();
        System.out.println("节点长度="+twoWayLinkedList.getSize());
        System.out.println("********************  添加头节点  ********************");
        twoWayLinkedList.addHead("9");
        twoWayLinkedList.addHead("8");
        twoWayLinkedList.addHead("7");
        twoWayLinkedList.addHead("6");
        twoWayLinkedList.addHead("5");
        twoWayLinkedList.display();
        System.out.println("节点长度="+twoWayLinkedList.getSize());
        System.out.println("********************  删除头节点  ********************");
        twoWayLinkedList.deleteHead();
        twoWayLinkedList.display();
        System.out.println("节点长度="+twoWayLinkedList.getSize());
        System.out.println("********************  删除尾节点  ********************");
        twoWayLinkedList.deleteTail();
        twoWayLinkedList.display();
        System.out.println("节点长度="+twoWayLinkedList.getSize());
    }
}

结果

********************  添加尾节点  ********************
[A->B->C->D->E]
节点长度=5
********************  添加头节点  ********************
[5->6->7->8->9->A->B->C->D->E]
节点长度=10
********************  删除头节点  ********************
[6->7->8->9->A->B->C->D->E]
节点长度=9
********************  删除尾节点  ********************
[6->7->8->9->A->B->C->D]
节点长度=8