小码哥《恋上数据结构与算法》笔记（三）：双向链表

约定不等于承诺〃 2023-07-20 13:46 10阅读 0赞

> 具体代码在 [LinkedList][] , 欢迎 `star`

## 目录 ##

*  一、双向链表（LinkedList）
 *  二、双向链表接口设计
 *  三、双向链表的实现
    
     *  1、构造方法
     *  2、查找结点
     *  3、清空结点
     *  4、插入结点 (`重点`)
     *  5、删除结点
     *  6、测试双向链表
 *  六、双向链表和动态数组比较

附录: 双向链表完整代码

--------------------

# 一、双向链表 #

跳转到目录

*  [单向链表][Link 1]只能通过Node中`next`属性从头遍历链表，完成搜索。
 *  双向链表中的Node增加`prev`属性，指向该结点上一个结点。
 *  双向链表查找元素可以从`first`或`last`两个方向开始查找。

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

# 二、双向链表接口设计 #

*  相较于单向链表，双向链表需要重写`查找结点`、`插入结点`、`删除结点`、`清空结点`四个方法。

# 三、双向链表的实现 #

### 1、构造方法 ###

跳转到目录

*  在双向链表属性中增加`last`属性记录`尾结点`。在Node属性中增加`prev`属性记录上一个结点。

public class LinkedList<E> extends AbstractList<E> { 
    
        /** * 指向第一个结点 */
        private Node<E> first;
    
        /** * 指向最后一个结点 */
        private Node<E> last;
    
    
        /** * 结点类;为链表的内部类 * * @param <E> */
        private static class Node<E> { 
    
            //存储元素的信息
            E element;
    
            //指向下一个结点
            Node<E> next;
    
            // 指向上一个结点
            Node<E> prev;
    
            // 结点构造器
            public Node(Node<E> prev, E element, Node<E> next) { 
                this.prev = prev;
                this.element = element;
                this.next = next;
            }
        }

### 2、查找结点 ###

跳转到目录

*  通过要查找`结点的位置`在链表的`前半段`还是`后半段`, 选择是`first`结点`从前往后遍历`还是`last`结点`从后往前遍历`。

/** * 传入一个index,返回该index位置的结点对象 * * @param index * @return */
    private Node<E> node(int index) { 
        // 当传入非法index就会报异常
        rangeCheck(index);
    
        if (index < (size >> 1)) { 
            /* 通过first去寻找结点,看需要next几次,找到该结点; 可以发现,next的次数和index有关系,index为几,就需要next几次 */
            Node<E> node = first;
            for (int i = 0; i < index; i++) { 
                node = node.next;
            }
            return node;
        } else { 
            /* 从后往前找, 因为是双向链表; */
            Node<E> node = last;
            for (int i = size - 1; i > index; i--){ 
                node = node.prev;
            }
            return node;
        }
    }

### 3、清空结点 ###

跳转到目录

*  需将新增属性`last`置为`null`。

public void clear() { 
        size = 0;
        first = null;
        last = null;
    }

### 4、插入结点 ###

跳转到目录

*  插入位置原结点为`old_node`（下图2号结点），上一个结点为`pre_node`（下图1号结点），新结点为new\_node。
 *  `pre_node`的`next`现在为`new_node`。
 *  `old_node`的`prev`现在为`new_node`。
 *  `new_node`的`prev`即为`old_node 的 prev`。
 *  `new_node`的`next`为`old_node`。

// 获取当前要插入位置的结点
    Node<E> next = node(index);
    // 其上一个结点
    Node<E> prev = next.prev;
    // 创建一个新的结点(这个新结点的指向已经初始化好了)
    Node<E> node = new Node<>(prev, element, next);
    next.prev = node;
    prev.next = node;

*  特殊情况，插入在最前面：
 *  如果`old_node`的`prev`为`null`，那么`old_node`即为原头结点。那么双向链表的`first`属性需改为`new_node`。
 *  插入在最后面：
 *  `new_node`的`prev`为双向链表的`last`(因为last指向的就是原来的最后一个结点)，`next`为`null`，同时`last`属性需改为`new_node`。  
    如果原链表为`空`，则双向链表的`first`和`last`都为`new_node`。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

public void add(int index, E element) { 
        rangeCheckForAdd(index);
    
        if (index == size) {     // 往最后添加元素
            Node<E> oldLast = last; // 之前的最后一个结点
            last = new Node<E>(oldLast, element, null);
            if (oldLast == null) {   // 这是链表添加的第一个元素
                // 此时链表的first,last都指向新结点
                first = last;
            } else { 
                // 再将原来的last指向现在的last
                oldLast.next = last;
            }
        } else { 
            // 获取当前要插入位置的结点
            Node<E> next = node(index);
            // 其上一个结点
            Node<E> prev = next.prev;
            // 创建一个新的结点(这个新结点的指向已经初始化好了)
            Node<E> node = new Node<>(prev, element, next);
            next.prev = node;
            if (prev == null) {  // index == 0
                // 也就是插入到第一个结点的位置
                first = node;
            } else { 
                prev.next = node;
            }
        }
        size++;
    }

### 5、删除结点 ###

跳转到目录

*  删除结点, 只需要让`被删除结点`的`前一个结点与后一个结点之间连接`, 同时去掉被删除结点`引用`即可。
 *  需要注意的是, 第`0`个结点和`最后一个`结点要特殊处理。

/** * 返回的是被删除元素的element */
    public E remove(int index) { 
        rangeCheck(index);
    
    	// 要被删除的结点
        Node<E> node = node(index);
        Node<E> prev = node.prev;	// 被删除结点的前驱结点
        Node<E> next = node.next;	// 被删除结点的后继节点
    
        if (prev == null) {  // index == 0
    	    // 表示被删除结点是第一个结点, 直接将其删除, 然后使用first执行它的后继节点即可
            first = next;	 
        } else { 
        	// 它的前驱直接指向它的后继
            prev.next = next;
        }
    
        if (next == null) {  // index == size - 1
            last = prev;
        } else { 
            next.prev = prev;
        }
    
        size--;
        return node.element;
    }

到此为止，我们即完成了从单向链表到双向链表的改造。

### 6、测试双向链表 ###

跳转到目录

*  测试工具类

public class AssertUtil { 
    	public static void test(boolean value) { 
    		try { 
    			if (!value) throw new Exception("测试未通过");
    		} catch (Exception e) { 
    			e.printStackTrace();
    		}
    	}
    }

*  Main方法

public class Main { 
        public static void main(String[] args) { 
            testList(new ArrayList<>());
            testList(new LinkedList<>());
        }
    
        static void testList(List<Integer> list){ 
            list.add(11);
            list.add(22);
            list.add(33);
            list.add(44);
    
            list.add(0, 55); // [55, 11, 22, 33, 44]
            list.add(2, 66); // [55, 11, 66, 22, 33, 44]
            list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]
    
            list.remove(0); // [11, 66, 22, 33, 44, 77]
            list.remove(2); // [11, 66, 33, 44, 77]
            list.remove(list.size() - 1); // [11, 66, 33, 44]
    
            System.out.println(list);
    
            AssertUtil.test(list.indexOf(44) == 3);
            AssertUtil.test(list.indexOf(22) == List.ELEMENT_NOT_FOUNT);
            AssertUtil.test(list.contains(33));
            AssertUtil.test(list.get(0) == 11);
            AssertUtil.test(list.get(1) == 66);
            AssertUtil.test(list.get(list.size() - 1) == 44);
        }
    }

# 六、双向链表和动态数组比较 #

跳转到目录  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

### 附录: 双向链表完整代码 ###

// List接口
    // AbstractList抽象类
    // 参考上一篇单向链表中的
    
    /** * Description: 双向链表实现 * * @author zygui * @date 2020/3/19 21:22 */
    public class DoubleLinkedList<E> extends AbstractList<E> { 
    
        /** * 指向第一个结点 */
        private Node<E> first;
    
        /** * 指向最后一个结点 */
        private Node<E> last;
    
    
        /** * 结点类;为链表的内部类 * * @param <E> */
        private static class Node<E> { 
    
            //存储元素的信息
            E element;
    
            //指向下一个结点
            Node<E> next;
    
            // 指向上一个结点
            Node<E> prev;
    
            // 结点构造器
            public Node(Node<E> prev, E element, Node<E> next) { 
                this.prev = prev;
                this.element = element;
                this.next = next;
            }
    
            @Override
            public String toString() { 
                StringBuilder sb = new StringBuilder();
                if (prev != null) { 
                    sb.append(prev.element);
                }
                sb.append("_").append(element).append("_");
                if (next != null) { 
                    sb.append(next.element);
                } else { 
                    sb.append("null");
                }
                return sb.toString();
            }
        }
    
        @Override
        public void clear() { 
            size = 0;
            first = null;
            last = null;
        }
    
        @Override
        public E get(int index) { 
            // 通过node方法找到结点,通过结点的element来获取元素
            return node(index).element;
        }
    
        @Override
        public E set(int index, E element) { 
            // 获取index处的结点
            Node<E> node = node(index);
            E oldElement = node.element;
            node.element = element;
            // 返回的是没覆盖之前的结点元素信息
            return oldElement;
        }
    
        @Override
        public void add(int index, E element) { 
    
            rangeCheckForAdd(index);
    
            if (index == size) {     // 往最后添加元素
                Node<E> oldLast = last; // 之前的最后一个结点
                last = new Node<E>(oldLast, element, null);
                if (oldLast == null) {   // 这是链表添加的第一个元素
                    // 此时链表的first,last都指向新结点
                    first = last;
                } else { 
                    // 再将原来的last指向现在的last
                    oldLast.next = last;
                }
            } else { 
                // 获取当前要插入位置的结点
                Node<E> next = node(index);
                // 其上一个结点
                Node<E> prev = next.prev;
                // 创建一个新的结点(这个新结点的指向已经初始化好了)
                Node<E> node = new Node<>(prev, element, next);
                next.prev = node;
                if (prev == null) {  // index == 0
                    // 也就是插入到第一个结点的位置
                    first = node;
                } else { 
                    prev.next = node;
                }
            }
            size++;
        }
    
        @Override
        /** * 返回的是被删除元素的element */
        public E remove(int index) { 
            rangeCheck(index);
    
            Node<E> node = node(index);
            Node<E> prev = node.prev;
            Node<E> next = node.next;
    
            if (prev == null) {  // index == 0
                first = next;
            } else { 
                prev.next = next;
            }
    
            if (next == null) {  // index == size - 1
                last = prev;
            } else { 
                next.prev = prev;
            }
    
            size--;
            return node.element;
        }
    
        @Override
        public void remove(E element) { 
            remove(indexOf(element));
        }
    
        @Override
        /** * element是保存在node里的,传入element,返回该结点的索引 */
        public int indexOf(E element) { 
            Node<E> node = first;
            if (element == null) { 
                // 因为element都在node中,所以通过next来遍历node
                for (int i = 0; i < size; i++) { 
                    if (node.element == null) return i;
                    node = node.next;
                }
            } else { 
                for (int i = 0; i < size; i++) { 
                    if (element.equals(node.element)) return i;
                    node = node.next;
                }
            }
            return ELEMENT_NOT_FOUNT;
        }
    
        /** * 传入一个index,返回该index位置的结点对象 * * @param index * @return */
        private Node<E> node(int index) { 
            // 当传入非法index就会报异常
            rangeCheck(index);
    
            if (index < (size >> 1)) { 
                /* 通过first去寻找结点,看需要next几次,找到该结点; 可以发现,next的次数和index有关系,index为几,就需要next几次 */
                Node<E> node = first;
                for (int i = 0; i < index; i++) { 
                    node = node.next;
                }
                return node;
            } else { 
                /* 从后往前找, 因为是双向链表; */
                Node<E> node = last;
                for (int i = size - 1; i > index; i--) { 
                    node = node.prev;
                }
                return node;
            }
        }
    
        @Override
        public String toString() { 
            // 打印格式: size=3, [10, 20, 30]
            // 使用StringBuilder 效率高一些
            StringBuilder string = new StringBuilder();
            string.append("size=").append(size).append(", [");
            Node<E> node = first;
            for (int i = 0; i < size; i++) { 
                string.append(node.toString());
                if (i != size - 1) { 
                    string.append(", ");
                }
                node = node.next;
            }
            string.append("]");
            return string.toString();
        }
    }

[LinkedList]: https://github.com/coderZYGui/linked-list
[Link 1]: https://blog.csdn.net/m0_37989980/article/details/105212254
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20230528/265efdfcdb8c426e9e678ff717882dd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20230528/645cb4a0bedb49c597dc03a8f2360ee7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20230528/5c9855b69d044f8cb46027f8f4f984f0.png