xsd 节点可循环_数据结构Java实现：循环链表和双向链表

  Java大联盟

  致力于最高效的Java学习

关注

上篇教程给大家分享了单链表的概念，以及如何用 Java 实现一个单链表的结构：数据结构Java实现：单链表。单链表是最基础的一种链表结构，在实际开发中的使用有一些局限性，比如只能单向往后查找节点，如果需要找到某元素的前驱节点，单链表是无法实现的，今天来给大家分享另外两个复杂一些的链表结构：循环链表和双向链表。

循环链表

循环链表本质上就是一种单链表，两者的不同之处在于链表中最后一个节点的指针指向哪里，在单链表中，末尾节点的指针指向空，如下图所示。

第一个元素 a 的指针指向 1008，即第二个元素 b 的首地址，b 的指针指向第三个元素 c 的内存地址 1020，没有第四个元素，所以 c 的指针指向空。

而在循环链表中，末尾节点的指针指向首节点，形成一个闭环，所以它叫循环链表，应该很好理解，如下图所示。

接下来用 Java 实现一个循环链表的结构，只需要在原有单链表的基础上稍作修改即可，如下所示。

package com.southwind.link;public class Node {    //数据    public Object data;    //下一个节点    public Node next;    public Node(Object data){        this.data = data;     }}

package com.southwind.link;public class LoopLinkedList {    public int size;    public Node head;    /**     * 添加元素     * @param obj     * @return     */    public Node add(Object obj){         Node newNode = new Node(obj);        if(size == 0){             head = newNode;             head.next = head;         }else{             Node target = head;            while(target.next!=head){                 target = target.next;             }             target.next = newNode;             newNode.next = head;         }         size++;        return newNode;     }    /**     * 在指定位置插入元素     * @return     */    public Node insert(int index,Object obj){        if(index >= size){            return null;         }         Node newNode = new Node(obj);        if(index == 0){             newNode.next = head;             head = newNode;         }else{             Node target = head;             Node previous = head;            int pos = 0;            while(pos != index){                 previous = target;                 target = target.next;                 pos++;             }             previous.next = newNode;             newNode.next = target;         }         size++;        return newNode;     }    /**     * 删除链表头部元素     * @return     */    public Node removeHead(){        if(size > 0){             Node node = head;             Node target = head;            while(target.next!=head){                 target = target.next;             }             head = head.next;             target.next = head;             size--;            return node;         }else{            return null;         }     }    /**     * 删除指定位置元素     * @return     */    public Node remove(int index){        if(index >= size){            return null;         }         Node result = head;        if(index == 0){             head = head.next;         }else{             Node target = head;             Node previous = head;            int pos = 0;            while(pos != index){                 previous = target;                 target = target.next;                 pos++;             }             previous.next = target.next;             result = target;         }         size--;        return result;     }    /**     * 删除指定元素     * @return     */    public Node removeNode(Object obj){         Node target = head;         Node previoust = head;        if(obj.equals(target.data)){             head = head.next;             size--;         }else{            while(target.next!=null){                if(obj.equals(target.next.data)){                     previoust = target;                     target = target.next;                     size--;                    break;                 }else{                     target = target.next;                     previoust = previoust.next;                 }             }             previoust.next = target.next;         }        return target;     }    /**     * 返回指定元素     * @return     */    public Node findNode(Object obj){         Node target = head;        while(target.next!=null){            if(obj.equals(target.data)){                return target;             }else{                 target = target.next;             }         }        return null;     }    /**     * 输出链表元素     */    public void show(){        if(size > 0){             Node node = head;            int length = size;             System.out.print("[");            while(length > 0){                if(length == 1){                     System.out.print(node.data);                 }else{                     System.out.print(node.data+",");                 }                 node = node.next;                 length--;             }             System.out.println("]");         }else{             System.out.println("[]");         }     }}

双向链表

双向链表是相对单链表来讲的，区别在于单链表中只有一个指针指向下一个节点，是单向连接的，只能从当前节点访问它的后继节点。而双向链表顾名思义是双向连接的，既可以从当前节点访问到后继节点，也可以访问到前驱节点，所以在双向链表中有两个指针，一个叫做后继指针，指向下一个节点，另一个叫做前驱指针，指向它的上一个节点，双向链表的结构如下图所示。

双向链表相比于单链表会占用更多的内存空间，因为多了一个指针来存储前驱节点的内存地址。虽然如此，但是在某些操作上，相比于单链表，双向链表可以极大地提升效率。

比如要删除链表中的某个节点，那么我们就需要获取到目标节点的前驱节点，然后将前驱节点的指针指向目标节点的下一个节点，如下图所示。

如上所示，删除节点必须先找到其前驱节点，在单链表中是不会记录元素的前驱节点的，所以必须从头开始遍历链表，直到找到目标节点的前驱节点，时间复杂度为 O(n)。

如果是双向链表的结构，每一个节点都会记录其前驱节点，可直接获取，所以此时的时间复杂度为 O(1)。

搞清楚了双向链表的概念，接下来我们用 Java 来实现双向链表的结构。

package com.southwind.link;public class DoubleNode {    //数据    public Object data;    //下一个节点    public DoubleNode next;    //上一个节点    public DoubleNode previous;    public DoubleNode(Object data){        this.data = data;     }}

package com.southwind.link;public class DoubleLinkedList {    public int size;    public DoubleNode head;    /**     * 添加元素     * @param obj     * @return     */    public DoubleNode add(Object obj){         DoubleNode newNode = new DoubleNode(obj);        if(size == 0){             head = newNode;         }else{             DoubleNode target = head;            while(target.next!=null){                 target = target.next;             }             target.next = newNode;             newNode.previous = target;         }         size++;        return newNode;     }    /**     * 在指定位置插入元素     * @return     */    public DoubleNode insert(int index,Object obj){        if(index >= size){            return null;         }         DoubleNode newNode = new DoubleNode(obj);        if(index == 0){             newNode.next = head;             head.previous = newNode;             head = newNode;         }else{             DoubleNode target = head;            int pos = 0;            while(pos != index){                 target = target.next;                 pos++;             }             newNode.previous = target.previous;             newNode.previous.next = newNode;             newNode.next = target;         }         size++;        return newNode;     }    /**     * 删除链表头部元素     * @return     */    public DoubleNode removeHead(){        if(size > 0){             DoubleNode node = head;             head = head.next;             size--;            return node;         }else{            return null;         }     }    /**     * 删除指定位置元素     * @return     */    public DoubleNode remove(int index){        if(index >= size){            return null;         }         DoubleNode result = head;        if(index == 0){             DoubleNode node = head;             head = head.next;         }else{             DoubleNode target = head;            int pos = 0;            while(pos != index){                 target = target.next;                 pos++;             }             target.previous.next = target.next;         }         size--;        return result;     }    /**     * 删除指定元素     * @return     */    public DoubleNode removeNode(Object obj){         DoubleNode target = head;        if(obj.equals(target.data)){             DoubleNode node = head;             head = head.next;             size--;         }else{            while(target.next!=null){                if(obj.equals(target.data)){                     target.previous.next = target.next;                     size--;                    break;                 }                 target = target.next;             }         }        return target;     }    /**     * 返回指定元素     * @return     */    public DoubleNode findNode(Object obj){         DoubleNode target = head;        while(target.next!=null){            if(obj.equals(target.data)){                return target;             }else{                 target = target.next;             }         }        if(target.next==null && obj.equals(target.data)){            return target;         }        return null;     }    /**     * 输出链表元素     */    public void show(){        if(size > 0){             DoubleNode node = head;            int length = size;             System.out.print("[");            while(length > 0){                if(length == 1){                     System.out.print(node.data);                 }else{                     System.out.print(node.data+",");                 }                 node = node.next;                 length--;             }             System.out.println("]");         }else{             System.out.println("[]");         }     }}

【框架合集】SpringMVC教程汇总

【框架合集】MyBatis教程汇总

【框架合集】Spring教程汇总

【框架整合】SSM教程

【十套项目源码】

【BAT面试真题】

你在看吗？