LinkedList底层实现（双向链表）（10）_linklist内部以双向链表的形式

前言：繁华的城市孤独的自己！

一、介绍

1、1 什么是LinkList

解释：LinkList是Collection接口下的List接口下的实现类。
示意图：

1、2 LinkList是用来解决什么的？

List特性：List底层是双向链表实现的,它的特点是：查询效率低，增删效率高，线程不安全。

1、当对数据存储后需要进行频繁的查询，使用ArrayList
2、但是数据是只用用来存储，增删元素比较频繁那LinkList是你非常好的选择！

1、3 如何实现LinkList

1、LinkList的底层本质是双向链表，而链表的本质是由一个一个的节点通过游标进行链接起来的。
2、因此我们要做的事就是创造节点（node）,然后存储的时候通过游标将它一个一个链接起来就成了。

二、设计

2、1 设计理念

设计理念：模仿它的原理来进行创建。本次我们进行的实现是双向链表。这种链表和单向不同，单向只能往下查寻，双向既能往上也能往下找。
步骤：
1、创建一个NODE类，作为节点。
2、将上一个和下个节点进行链接。

2、2 设计图

双向链表设计图：

三、实现

3、1 Node类

正如我所说，我们是一个链表由一个个节点进行拼凑而成，所以我们第一个件事情就是创建节点。

核心代码：

// 1、第一步 ：添加node
class Node{// 此类是一个内部`类`,内部类具有更好的封装，外部类不能够直接访问内部类的属性。如果该类只服务于本类，该类就使用内部类。
           // 双向链表：需要上一个节点，下一个节点以及中间存储的内容。用private将其封装，并使用get,set方法进行读取。
           // 实际上如果 体量过大还是不建议用内部类，占地方。
   private Node previous;
   private Object obj;
   private Node next;
   
    // 空构造函数
    public Node(){}
    
    // 有参构造函数
    public Node(Node previous,Object obj,Node next){
        this.previous=previous;
        this.obj = obj;
        this.next = next;
    }
    //此处省略get、set代码.
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、2 Add(增)

新增的时候我们其实只用关注两个点：1、怎么将上一个节点链接到下一个节点。2、怎么将下一个节点链接到上一个节点。

图示：

核心代码

  //第三步：添加（增删改查）。先做增加
    public void add(Object obj){
        Node node = new Node();
        //1、判断是否存在第一个节点
        if(frist==null){
            node.setPrevious(null);
            node.setObj(obj);
            node.setNext(node);
            //第一个节点 的 上一个节点肯定是空的，下一个节点就是当前节点
            frist=node;
            last=node;// 第一个也是最后一个 。没毛病吧？
            size++;   // 这不是数组，但是我们是有顺序的所以需要自己不停的增加一个
        }else{
            node.setPrevious(last);
            node.setObj(obj);
            node.setNext(null);
            // 对于最新的节点来说我们上一个节点肯定就是链表最后一个节点。
            // 最后一个节点是没有下一个节点的 。
            last.setNext(node); 
            // 最后一个节点的下一个节点就是当前的节点。
            last=node;
            // 覆盖掉最后一个节点为，最新得节点。
            size++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

图示：实际上我认为的数据是这样的。都在一个节点里面！

说实话我当时看完debug后的数据我就惊讶了，不是说好ONE BY ONE 吗？为啥都塞一起 ？我当时的心情和下面这位大妈一样。

可以看下我们的debug后的数据。


其次双向链表，我们可以从preious找也就是我们可以从后往前面找。完美啊！

3、3 Remove（删）

删除链表：简单的说法就是将中间的删除把上个节点的NEXT换成当前节点的下个节点。（有点绕！）
图示：

不过需要注意的是第一个节点和最后一个节点在删除的时候是有点特殊的！
核心代码：

 // 第四步：删除（增删改查）。先做删除
    public boolean remove (Object obj ){
        if(frist==null)
            return false;
        Node node = frist;
        // 思路:遍历整个链表，找到对应的 object删除 。然后 将 删除元素的上一个 和 删除元素的下一个给连起来 。Ok
        for(int i = 0 ; i < size; i++){ // 为什么用size进行判断 ？ 因为 ，我们增加一个就加1所以size就是正确的链表大小。
            if(node.getObj().equals(obj)){
                    Node lastNode = node.getPrevious(); 
                    // 当前节点的上一个节点。有问题如果是第一个不就没有吗？
                    Node nextNode = node.getNext();
                    // 当前节点的下一个节点。如果是最后一个不就没有吗？
                    node=null;
                    // 直接将这个Node搞没它。
                if(lastNode!=null && nextNode!=null){ // 删除既有上面节点的 ，又有下面节点的
                    nextNode.previous=lastNode;
                    lastNode.next=nextNode;
                }else if(lastNode==null && nextNode!=null) {  // 删除第一个节点
                    frist=nextNode;
                    nextNode.previous=null;
                }else if(nextNode==null && lastNode!=null){  //删除最后一个节点
                    last=lastNode;
                    lastNode.next=null;
                }
                size--;
                return true;
            }else{
                node=node.getNext();
            }

        }
        return false;

    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

看到自己写的代码真的惨不忍睹，按老毕的说法这就是一坨☝。（老毕，带我上黑船的老师~）

给大家看下JDK大神们写的源码（养养眼）。

记得 写代码一定要进行封装，一个功能就是个方法。不要一个方法里面干很多事，保证一个方法的原子性。这样有利于代码的可扩展以及维护。设计模式有说这个东西。但是还是需要经过大量的实践。

3、4 Get（查）

这个获取元素挺简单的 ，因为是获取对应的位置的链表，但是不同于数组我们可以直接用数组下标进行取值。我们不管是取第几个我们都得用便利去找元素。

    //第六步get方法
    public Object get(int index){
        //遍历 。首先要校验 index是否 超过size以及是否
        Node node = frist;
        if(index<0&&index>=size){

        }else {
            for(int i=0;i<size;i++){
                if(i==index)
                    return node.getObj();
                else
                    node=node.getNext();
            }

        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、5 Size（大小）

这个是LIST里面非常常用的方法，有序，可重复，size其实就是这个顺序。我们在链表中增加元素和删除元素的时候都需要进行size的加减。

    public int size(){
        return size;
    }
1
2
3

四、思考题以及面试题

4、1思考题

常用的方法还有，contains(obj)是否包含该元素，和add（index,obj）按照位置进行插入。希望有兴趣的小伙伴可以自己通过思路去写下。
add(index,obj)
图示：

contains(obj)思路：
循环遍历，找到有一样的返回true.没有false.

4、2面试题

1、LinkiList手写代码。
像这种：

2、LinkList的底层是怎么实现的啊？
答:底层是由双向链表实现，设计的思路是创建一个节点类。包含上节点，中内容，以及下节点。然后将每个节点互相链接。(此处容易设计到数据结构因此对应的数据结构也要有所了解。)
3、LinkList的优缺点：LinkList是由双向链表实现，增删效率高，查询效率低，线程不安全。
4、更深入的问题就是增删改查的实现，按照博客将思路回答即可。
5、深入一点的LinkList还实现了Queue接口，提供了一些队列的方法，offer(),peek(),poll();等多与一些线程池一起实现。

下面是关于其他集合类的博客有兴趣的小伙伴可以看看。

1. ArrayList底层实现
2. HashMap底层实现

总结

写给一些自己的想法，可以跳过

最近看了很多大佬的博客，才想起来自己还是以前那个坐井观天的