【数据结构】之双向链表、双端(双向)链表、循环(双向)链表_双端链表和双向链表结构图

双向链表、双端(双向)链表、循环(双向)链表示意(简)图：

声明：下面各图中，箭头指向的是整个节点，而不是指向节点中的prior或next。

双向链表：只有一个指针指向最开始的结点。

双端(双向)链表：有两个指针分别指向两端的节点。

循环(双向)链表：指向形成一个闭环。

双端(双向)链表的Java实现(简单示例)：

注：双向链表、双端(双向)链表、循环(双向)链表的实现思路几乎一样，这里以实现双端(双向)链表示例。

/**
 * 双端(双向)链表的(简单)实现
 *
 * @author JustryDeng
 * @date 2019/5/21 20:51
 */
public class DoublesidedLinkedlistImpl<T>  {
 
    /** 节点的个数 */
    private int size;
 
    /**
     * 尾节点
     * 注:本人新增节点时，从尾巴上新增
     * 注:也可以从头上进行新增节点
     */
    private Node rear;
 
    /**
     * 当前节点
     * 即:链表中最前面的节点，可理解为 队列中的头结点
     */
    private Node head;
 
    /**
     * 成员内部类， 节点
     */
    private class Node {
 
        /** 内部类的元素,Object类型 */
        private T data;
 
        /** 上一个节点(即:前驱节点)的地址 */
        private Node prior;
 
        /** 下一个节点(即:后继节点)的地址 */
        private Node next;
 
        private Node(T data) {
            this.data = data;
        }
 
        public T getData() {
            return data;
        }
 
        public void setData(T data) {
            this.data = data;
        }
 
        public Node getPrior() {
            return prior;
        }
 
        public void setPrior(Node prior) {
            this.prior = prior;
        }
 
        public Node getNext() {
            return next;
        }
 
        public void setNext(Node next) {
            this.next = next;
        }
    }
 
    /**
     * 新增节点
     *
     * @param obj
     *         添加的元素
     * @return  添加的元素对应的节点
     * @date 2019/5/20 20:48
     */
    public Node addNode(T obj) {
        // obj不能为null
        notNullCheck(obj);
        // 每次增加的元素，都作为新的尾节点
        Node newRear = new Node(obj);
        if (size == 0) {
            head = newRear;
            rear = newRear;
        } else {
            newRear.prior = rear;
            rear.next = newRear;
            // 更新尾节点
            rear = rear.next;
        }
        size++;
        return newRear;
    }
 
    /**
     * 删除当前(头)节点
     *
     * @return  被删除了的(头)节点
     * @date 2019/5/20 20:50
     */
    public Node deleteHead() {
        if(isEmpty()) {
            return null;
        }
        // targetObj存放原来的头节点数据
        Node targetNode = head;
        if (head.next != null) {
            // 断开后继节点对要删除的节点的引用
            head.next.prior = null;
        }
        // 更新头节点
        head = head.next;
        size--;
        return targetNode;
    }
 
    /**
     * 删除指定元素对应的第一个节点
     *
     * @return  删除成功与否(若元素不存在，则返回false)
     * @date 2019/5/20 20:50
     */
    public boolean deleteFirstNode(T obj) {
        // obj不能为null
        notNullCheck(obj);
        // 当head未null时，说明，当前为空链表
        if (size == 0) {
            return false;
        }
        // 当前节点
        Node current = head;
        // 前驱节点
        Node previous = head;
        // 判断条件，如果当前节点的值和待删除的值不一致，则继续
        while (!obj.equals(current.data)) {
            // 如果下一个节点不存在(即:当前节点是尾节点)
            // 则说明，不存在 元素值为obj的节点，直接返回false
            if (current.next == null) {
                return false;
            } else {
                // 更新前驱节点、当前节点
                previous = current;
                current = current.next;
            }
        }
        // 如果要删除的节点是第一个节点；
        if (head.equals(current)) {
            if (head.next != null) {
                // 断开后继节点对要删除的节点的引用
                head.next.prior = null;
            }
            // 更新头结点
            head = current.next;
        // 如果要删除的节点是尾节点
        } else if ((rear.equals(current))) {
            // 前驱节点断开对要删除的节点的应用
            previous.next = null;
        // 如果要删除的节点不是头结点(是中间的某个节点或尾节点)
        } else {
            // 将当前节点“抠除”，并将“两端”接上
            previous.next = current.next;
            current.prior = previous;
        }
        size--;
        return true;
    }
 
    /**
     * 删除指定元素对应的所有节点
     * 注:此方法性能较低，少用或不用
     *
     *
     * @return  删除了的节点数
     * @date 2019/5/20 20:50
     */
    public int deleteAllNode(T obj) {
        int count = 0;
        while(deleteFirstNode(obj)){
            count++;
        }
        return count;
    }
 
    /**
     * 查找元素的(第一个)节点
     *
     * @param obj
     *         待查找的元素对象
     * @return 元素的(第一个)节点, 无则返回null
     */
    public Node find(T obj) {
        // obj不能为null
        notNullCheck(obj);
        Node currNode = head;
        // 临时大小为size
        int tempSize = size;
        while (tempSize > 0) {
            if (obj.equals(currNode.data)) {
                return currNode;
            } else {
                currNode = currNode.next;
            }
            tempSize--;
        }
        return null;
    }
 
    /**
     * 非空检验
     *
     * @param obj
     *            被验证的对象
     * @throws NullPointerException 空指针异常(运行时异常)
     * @date 2019/5/20 21:00
     */
    private void notNullCheck(T obj){
        if(obj == null) {
            throw new NullPointerException("data must not be null!");
        }
    }
 
    /**
     * 判断链表是否为空
     *
     * @return  链表是否为空
     * @date 2019/5/20 20:49
     */
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }
 
        StringBuilder sb = new StringBuilder(16);
        sb.append("[");
        Node currentNode = head;
        for (int i = 0; i < size; i++) {
            sb.append(currentNode.data);
            sb.append(", ");
            currentNode = currentNode.next;
        }
        int length = sb.length();
        sb.delete(length - 2, length).append("]");
        return sb.toString();
    }
 
    public static void main(String[] args) {
        DoublesidedLinkedlistImpl<String> uli = new DoublesidedLinkedlistImpl<>();
        // 增
        uli.addNode("A");
        uli.addNode("B");
        uli.addNode("C");
        uli.addNode("C");
        uli.addNode("D");
        uli.addNode("C");
        uli.addNode("E");
        uli.addNode("E");
        uli.addNode("F");
        uli.addNode("E");
        // toString
        System.out.println("增加节点后的初始化链表:\t" + uli);
        // 找到C元素对应的第一个节点
        System.out.println("找到C元素对应的第一个节点:" + uli.find("C")
                + ",该节点的下下个节点的数据内容为:"
                + uli.find("C").getNext().getNext().getData());
        // 删除头结点
        uli.deleteHead();
        // toString
        System.out.println("删除头结点后:\t" + uli);
        // 删除C元素对应的第一个节点
        uli.deleteFirstNode("C");
        // toString
        System.out.println("删除C元素对应的第一个节点后:\t" +uli);
        // 删除E元素对应的所有节点
        uli.deleteAllNode("E");
        // toString
        System.out.println("删除E元素对应的所有节点后:\t" +uli);
 
    }
}

测试一下：

运行(写在实现类里面的)主方法，控制台输出：

由此可见：简单的双端(双向)链表实现完毕！

^_^ 如有不当之处，欢迎指正

^_^ 学习视频
               51CTO学院《数据结构与算法》，讲师张晨光

^_^ 本文已被收录进《程序员成长笔记(五)》，笔者JustryDeng