Java集合（二）如何实现一个LinkedList？

小鱼儿 2024-05-05 06:51 120阅读 0赞

> 不为失败找理由，只为成功找方法。所有的不甘，因为还心存梦想，所以在你放弃之前，好好拼一把，只怕心老，不怕路长。

#### 文章目录 ####

*  一、面试题：如何实现一个LinkedList？
 *  二、撸起袖子直接干
 *  三、小结

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

## 一、面试题：如何实现一个LinkedList？ ##

关于LinkedList如何实现的是一道面试题，本题考查了对LInkedLIst以及与之相关的数据结构的理解。而解答本题的关键就是需要了解LInkedList底层的使用双向链表实现的，同时也需要掌握双向链表最基本的添加节点和删除节点的操作。【提示：】关于双向链表的详细原理，可参考：[Java集合（一）][Java]。如果没有时间，我在这里介绍一下需要掌握的双向链表的知识点：

1）链表的每一个节点有三个数据域：指向前驱节点的引用（previous）、节点存储的数据（element）、指向后续节点（next）的引用。
    
    2）向链表中插入新的节点时需要调整新节点的previous与next的指向，同时还要调整新添加节点的前驱节点的next的指向以及其后续节点的previous的指向。当链表为空的时候要特殊考虑。
    
    3）当删除一个节点时，需要调整让它的前驱节点的next指向它的后续节点，让它的后续节点的previous指向它的前驱节点。当删除的节点是首节点或尾节点的时候需要特殊考虑。

总的来说双向链表核心的操作就是添加元素和删除元素。不过不同的程序员可能会给出不同的实现，而接下面，我们就开始写一个自己的LinkedList实现吧。

## 二、撸起袖子直接干 ##

废话不多说，直接上代码，代码里面也标注着解释。

/**
     * LinkedList的核心实现
     * @param <E>
     */
    public class MyLinkedList<E>{
        
        private Node<E> first; //链表头节点
        private Node<E> last; //链表尾节点
        private int size; //链表长度
    
        /**
         * 向链表添加数据
         */
        public void add(E e){
        
        	//创建链表节点对象（提示：以内部类的形式【模仿源码】在后面）
            Node<E> node = new Node<E>(null,e,null);
            //如果链表为空，这是添加的第一个节点
            if (first == null){
        
                first = node;
                last = node;
            }else{
        
                //否则把节点添加到last节点后面
                node.previous = last;
                last.next = node;
                //新添加的节点变成了链表的组后一个节点
                last = node;
            }
            size++;
        }
    
        /**
         * 获取链表的大小
         */
        public int size(){
        
            return size;
        }
    
        /**
         * 获取链表中第index个元素（下标从0开始）
         */
        public E get(int index){
        
            Node<E> temp = find(index);
            return temp == null ? null : temp.element;
        }
    
        /**
         * 根据索引查询元素
         * @param index
         * @return
         */
        private Node<E> find(int index){
        
            Node<E> temp = null;
            if (first != null){
        
                temp = first;
                for (int i=0; i<index && temp != null; i++){
        
                    temp = temp.next;
                }
            }
    
            //根据需求可以打印错误信息或者抛出异常
            if (temp == null){
        
                System.out.println("Invalid index");
            }
            return temp;
        }
    
        /**
         * 根据索引index删除元素
         */
        public void remove(int index){
        
            Node<E> temp = find(index);
            if (temp != null){
        
                Node<E> pre = temp.previous;
                Node<E> next = temp.next;
                //当被删除的节点没有前驱节点时，删除后，被删除节点的后续节点句变成了链表的首节点
                if(pre == null){
        
                    first = next;
                }else{
        
                    pre.next = next;
                }
    
                /*当被删除的节点没有后续节点时，删除后，
                	被删除的节点的前驱节点就变成了链表的最后一个节点*/
                if (next == null){
        
                    last = pre;
                }else {
        
                    next.previous = pre;
                }
                size--;
            }
        }
    
        /**
         * 根据已存在索引index插入元素
         */
        public void add(int index, E e){
        
            Node<E> temp = find(index);
            Node<E> newNode = new Node<>();
            newNode.element = e;
    
            if (temp != null){
        
                Node<E> pre = temp.previous;
                pre.next = newNode;
                newNode.previous = pre;
    
                newNode.next = temp;
                temp.previous = newNode;
    
                size++;
            }
        }
    
        /**
         * 打印
         * @return
         */
        public String toString(){
        
            StringBuilder stringBuilder = new StringBuilder("[");
            Node<E> p = first;
            if (p!=null){
        
                stringBuilder.append(p.element);
                p = p.next;
            }
    
            while (p != null){
        
                stringBuilder.append("," + p.element);
                p = p.next;
            }
            stringBuilder.append("]");
            return stringBuilder.toString();
        }
    
        /**
         * 内部类 节点类
         * 双向链表的节点
         * @param <E>
         */
        private class Node<E> {
        
            Node<E> previous; //用来指向前驱节点
            E element; //元素
            Node<E> next; //指向后续节点
    
            public Node(){
        }
    
            public Node(Node<E> previous, E element, Node<E> next) {
        
                this.previous = previous;
                this.element = element;
                this.next = next;
            }
        }
    }

以上就是自己实现一个LinkedList集合，不过这里只是实现了一些核心内容，如果需要了解更多，可查看源码。

接下来就是测试了，我们来定义一个测试类吧。

public class Test{
        
        public static void main(String[] args) {
        
            MyLinkedList<String> list = new MyLinkedList<String>();
            list.add("java");
            list.add("python");
            list.add("mysql");
            list.add(1,"javascript");
    
            System.out.println(list);
            list.remove(2);
            System.out.println(list);
        }
    }

执行结果图如下：  
![在这里插入图片描述][01b66c01d6124b99a4919b737c7d19a6.jpeg_pic_center]  
大功告成！

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

## 三、小结 ##

本章讲的是如何实现一个LinkedList，这也是一道面试题，涉及到了数据结构双向链表和你对应LinkedListAPI的基本理解。由此本篇文章的讲解就到处结束了，如果内容上与道友所思有所出入，欢迎畅谈技术的魅力。

[Java]: https://blog.csdn.net/weixin_54679968/article/details/127035042
[01b66c01d6124b99a4919b737c7d19a6.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/05/c0b6fa3aea8f4b6eb4297c3932866083.jpeg