链表的底层实现方式

￡神魔★判官ぃ 2022-05-29 03:40 218阅读 0赞

[链表的底层实现方式][Link 1]

链表在我们日常的开发过程中应该说是非常常见，做移动开发的更可以说是每天都在接触。比如MessageQueue，底层就是单链链表，各种网络框架用到的队列，底层用到的都是链表。而说到链表，就不得不提到另外一种数据结——集合。相信有一句话大家都听书过：集合更适合查询操作，链表更适合频繁的插入，删除操作。这究竟是为什么呢？今天我就从理论和代码的角度分析一下其中的原因。

首先，集合的底层是数组，数组会为每一个元素分配相同的内存空间，而数组一旦声明以后长度又是不可变的，因此，计算机只需根据你提供的具体查询数值，就可以根据该数值去查询相应的那一片内存空间，因此查找十分迅速。当然，这里只是简单的铺垫，因为我们今天重点要说的是链表。链表与集合的不同之处就是，链表底层并不是数组。它的数据结构，举一个简单的例子，像是有很多个人，手拉手排成一队，当然，这个“队”不一定是一条直线，也可以是一个环形等等的形状。而形成这种数据结构的重中之重，就是我刚才提到的——手拉手。

既然链表的要实现手拉手的数据结构，那么链表中的每一个元素肯定知道他的上一个节点元素和下一个节点元素分别是谁，在java中，弱化了指针的概念，因此，每一个节点元素持有上一个节点元素和下一个节点元素的对象的引用。也就是说，每一个节点对象应该有3个属性：1，value值；  2，上一个节点的引用；  3，下一个节点的引用。这三个属性是链表数据结构的核心，有了这三个属性，基本雏形就已经完成了。接下来，我们在每次添加或者删除或者插入一个新的节点的时候，只需要做2件事情：1，将前一个节点的next引用改变；2，将后一个节点的last引用改变。即大功告成！理论的东西就将这么多，接下我手写一个循环链表，也就是环形链表，结合着讲解。

首先创建一个MyLinkedList类，在MyLinkedList内部，创建一个内部类Node，作为节点元素，其中有三个属性，分别是泛型element，也就是实际的value值，上一个节点last和下一个节点next。如下图

![SouthEast][]

这里比较简单，不详细说。接下来，我们需要在MyLinkedList中声明一个头节点，作为我们的开头的节点，并且头节点在MyLinkedList的构造函数中初始化，如下图

![SouthEast 1][]

在构造函数中，让头节点的上一个节点引用和下一个节点引用都指向自己，形成一个自己跟自己的闭环。至此，初始化的工作就已经完成了，接下来就可以写添加的方法了，我定义一个offer()函数作为添加节点元素的方法，如下图

![SouthEast 2][]

我们在调用添加函数的时候，传入一个泛型为E的值e，而该函数实际做了这么几件事：1，创建一个新的节点元素newNode，让该节点的next引用指向头节点headNode，last引用指向链表的出headNode节点以外的最后一个节点；2，让上一个节点的next引用指向新节点newNode；3，让headNode节点的last引用指向新节点newNode。听起来好像很复杂，但是我给大家举一个简单的生活中的例子大家就明白了。比如现在有10个人手拉手围城了一个圈，现在你自己要加入进去，是不是要把原来拉在一起的两个人先分来，分别拉住你的左右手，然后才能形成一个新的环。循环链表的原理其实跟这个是一模一样的。同样的，我写了一个poll()函数来移除最后一个节点元素，如下图

![SouthEast 3][]

这里就不多做讲解了，道理跟添加是一样的。有了添加删除，再写个查询吧，查询相对就简单多了，根据传入的index，遍历得到相应的node节点，取出该节点的element值返回即可，如下图

![SouthEast 4][]

好了，这样链表的基本功能就完成了，当然，你可以接着去丰富相关的函数，我这里只举例增删改查，过几天我会接着发表ArrayList和HashMap的原理，也会手写实现自己的List和Map，如果感兴趣的话可以关注我，谢谢！最后贴出完成代码

/** * 手写链表 * Created by xrc on 2017/6/21. */ public class MyLinkedList<E> {
    
        private int size;
        //头元素
        private Node<E> headNode;
    
        public MyLinkedList() {
            headNode = new Node<>(null, null, null);
            headNode.last = headNode;
            headNode.next = headNode;
        }
    
        /** * 链表的元素数 */ public int size() {
            return size;
        }
    
        /** * 根据传入的index查找对应元素的value值 */ public E get(int index) {
            return node(index).element;
        }
    
        /** * 根据传入的index查找相应的Node元素对象 */ private Node<E> node(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException("size = " + size + ",but index = " + index);
            }
            Node<E> node = headNode;
            for (int i = 0; i <= index; i++) {
                node = node.next;
            }
            return node;
        }
    
        /** * 在链表的最后添加一个新的元素 */ public void offer(E e) {
            Node<E> last = headNode.last;
            Node<E> newNode = new Node<>(e, headNode, last);
            last.next = newNode;
            headNode.last = newNode;
            size++;
        }
    
        /** * 将链表的最后一个元素移除 */ public void poll() {
            Node<E> last = headNode.last;
            last.last.next = headNode;
            headNode.last = last.last;
            size--;
        }
    
        /** * 链表中的Node元素类 */ private class Node<E> {
            //实际数值
            E element;
            //该元素持有下一个元素的对象
            Node<E> next;
            //该元素持有上一个元素的对象
            Node<E> last;
    
            Node(E element, Node<E> next, Node<E> last) {
                this.element = element;
                this.next = next;
                this.last = last;
            }
        }
    }

[Link 1]: http://blog.csdn.net/xu404741377/article/details/73526955
[SouthEast]: /images/20220529/b38aa9202b214a4aa84b12f35924e481.png
[SouthEast 1]: /images/20220529/9ccc86bf0f524e96b397d7a2c96e807f.png
[SouthEast 2]: /images/20220529/91aad8e6413549da8c6c7d45041e0af3.png
[SouthEast 3]: /images/20220529/3de263d0c0b748d086046eb50f43dfd8.png
[SouthEast 4]: /images/20220529/040025be3b344174a07670b1dfc65523.png