算法：图解Java双向循环链表的实现

比眉伴天荒 2023-02-24 07:46 2阅读 0赞

# 什么是双向链表 #

*  这是一个双向链表  
    ![在这里插入图片描述][20200708135509985.png]

双向链表由分成一个个节点组成：  
![在这里插入图片描述][20200708135801851.png]  
双向链表应该有一个head节点指向第一个节点、tail节点指向第二个节点、size表示数组长度

# 实现 #

## 结构体定义 ##

DoubleNode为链表中的节点，DoubleList双链表

public class DoubleNode<T> {
        
        T data;
        DoubleNode<T> pre;
        DoubleNode<T> next;
    
        public DoubleNode(T data) {
        
            this.data = data;
        }
    }

public class DoubleList<T> {
        
        private int size;
        private DoubleNode<T> head;
        private DoubleNode<T> tail;
    }

## 链表初始化 ##

public DoubleList() {
        
            this.size = 0;
            this.head = null;
            this.tail = null;
        }

## 插入数据 ##

*  尾插：
    
     *  先判断当前node是否为null，如果为null，直接返回
     *  当size = 0：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]
     *  当size不等于0：  
        例子1：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]

// 双向链表
    public boolean append(DoubleNode<T> node){
        
            if(node == null){
        
                return false;
            }
            if (this.size == 0){
        
                this.head = node;
                this.tail = node;
                node.pre = null;
                node.next = null;
                this.size++;
            }else{
        
                node.pre = tail;
                node.next = null;
                tail.next = node;
                tail = node;
                this.size++;
            }
            return true;
        }

*  头插：
    
     *  先判断node是否为null，如果为null，直接返回false
     *  当size = 0：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]
     *  当size = 1；  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]、![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]
     *  当size大于1：  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 10]

public boolean insertHead(DoubleNode<T> node){
        
            if(node == null){
        
                return false;
            }
            if (this.size == 0){
        
                this.head = node;
                this.tail = node;
                node.pre = null;
                node.next = null;
                this.size++;
            }else if(this.size == 1){
        
                node.pre = null;
                node.next = this.head;
                this.head.pre = node;
                this.head = node;
                this.size++;
            }else {
        
                node.pre = head;
                node.next = head.next;
                head.next.pre = node;
                head.next = node;
                this.size++;
            }
    
            return true;
        }

*  指定位置插入节点：
    
     *  先判断节点是否为空，以及pos是否合法
     *  如果pos等于size，就是尾部醉驾
     *  如果pos = 0.  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 11]  
        [深入分析java集合类LinkedList(源码分析)][java_LinkedList]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 12]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 13]
 *  如果pos>0，假设pos = 1
    
     *  先找到pos的位置  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 14]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 15]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 16]

public boolean insertPos(DoubleNode<T> node, int pos){
        
            if(node == null || pos > this.size || pos < 0){
        
                return false;
            }
            if (pos == 0){
        
                node.next = this.head;
                node.pre = null;
                this.head = node;
                this.size++;
                return true;
            }
    
            if (pos == this.size){
        
                return this.append(node);
            }
    
            DoubleNode<T> cur = this.head;
            for(int i = 0; i < pos; i++){
        
                cur = cur.next;
            }
            node.pre = cur.pre;
            node.next = cur;
            cur.pre.next = node;
            cur.pre = node;
            this.size++;
            return true;
        }

## 删除节点 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 17]

*  先判断索引是否正确：索引取值范围\[0, size-1\]，也就是pos必须大于size-1 ； size必须大于0
    
     *  如果pos = 0：
        
         *  如果size == 1  
            \* 让head和tail直接指向0就行了
         *  如果size大于1  
            ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 18]  
            ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 19]
     *  如果pos = size - 1  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 20]  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 21]
     *  否则：
        
         *  先找到pos对应的节点，也即是要删除这个节点  
            ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 22]  
            ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 23]

public boolean delete(int pos){
        
            if(pos > this.size - 1 || pos < 0 || this.size == 0){
        
                return false;
            }
    
            if(0 == pos){
        
                if(this.size == 1){
        
                    this.head = null;
                    this.tail = null;
                }else{
        
                    this.head.next.pre = null;
                    this.head = this.head.next;
                }
                this.size--;
                return true;
            }
    
            if(this.size - 1 == pos){
        
                this.tail.pre.next = null;
                this.tail = this.tail.pre;
                this.size--;
                return true;
            }
    
            DoubleNode<T> cur = this.head;
            for (int i = 0; i < pos; i++){
        
                cur = cur.next;
            }
    
            cur.next.pre = cur.pre;
            cur.pre.next = cur.next;
            this.size --;
            return true;
        }

## 打印链表 ##

public void display(){
        
            DoubleNode<T> cur = head;
            while (cur != null){
        
                System.out.print(cur.data + "\t");
                cur = cur.next;
            }
    
    
        }
    
        public void reverse(){
        
            DoubleNode cur = tail;
            while (cur != null){
        
                System.out.print(cur.data + "\t");
                cur = cur.pre;
            }
        }

[20200708135509985.png]: /images/20230209/b8651406b78b4ec9b9be40db54b5bd64.png
[20200708135801851.png]: /images/20230209/eae6b2d64f5f4d7ab309de9703625564.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230209/74d2dd9ff348452f9fa1fe03b10541aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20230209/88e34abe81054604b1de0623a46dd94c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: /images/20230209/3ecce0475a2d41a8bcfb558f72c3265a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/202007091355448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: /images/20230209/760e3885c9c04c25af3c1453119672d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]: /images/20230209/49ede54014c04d9593b302c80bb1b2fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]: /images/20230209/3ddf730e6e854c16b5f8d7f2022e39d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]: /images/20230209/d8f86bfa9afc4657a90335662cae8aef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]: /images/20230209/2561020d8d374097ae88246571836743.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]: /images/20230209/7459d0e6844c4251bfb4bc5652e6e6b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 10]: /images/20230209/6d6fce7d07a44c0aaad00999128c90be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 11]: /images/20230209/18d61d2035ef434ea3325316a41d70ef.png
[java_LinkedList]: https://baijiahao.baidu.com/s?id=1638491384762531690&wfr=spider&for=pc
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 12]: /images/20230209/d147fb4991eb42a9b5d1ab215cb05318.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 13]: /images/20230209/6fa8a3cd9d7942d282d829aadbe15d04.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 14]: /images/20230209/b9e3915a1bdc4b00857bdcc64a94027e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 15]: /images/20230209/11e7fcc1ede3499183beef179abd801d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 16]: /images/20230209/554d8e7c52014edc8f68ad1136e3e99c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 17]: /images/20230209/cf94354d9d664903a55d5bcdc29f24b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 18]: /images/20230209/43b9616dbb56410e99b336dc615ed0a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 19]: /images/20230209/c5696d09dedd47d68b356ba09201ed22.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 20]: /images/20230209/25cf8736ceb147d88874cab6105ed94d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 21]: /images/20230209/b0f8e5a365664dbf9e60b89564acdb58.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 22]: /images/20230209/06014d19bf5741a2bae571869d2cf0fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 23]: /images/20230209/d0d5061a450c486fbe593301013415f4.png