链表的详细介绍

目录

链表的简单定义：

链表的分类

单项带头非循环

单向不带头循环链表

实现单向非循环无头链表

定义链表：

实现链表方法

打印链表

头插法：

尾插法：

指定插入：

通过对应值删除节点：

删除所有对应值节点：

?编辑

LinkedListd的介绍

LinkedList的定义：

LinkedList的有参构造方法：

LinkedList的打印：

ArrayList和LinkedList的简单区别：

---

链表相对于数组优点：?插入或者删除元素的时候不需要移动其他的数据，且也不需要扩容

链表的简单定义：

链表中每个元素称为节点，每个节点由两部分组成（单向链表）：数值和next域，next域存储下一个节点的地址，例如下图，可知链表在内存上不一定连续

链表的分类

单向（双向） 非循环（循环） 不带头（带头）链表，三者排列组合后可知有8种链表；

我们主要学习两种：单项不带头非循环链表(笔试和面试的考量对象)以及双向不带头非循环链表(LinkedList的底层逻辑)

简单认识一下：

单向带头非循环

头结点的数值域没有实际作用

单向不带头循环链表

这个head不是指0x112处这个节点而是只存放0x112这个地址值。

实现单向非循环无头链表

定义链表：

链表又节点和头节点组成，每个节点又由数值和next域组成，那么我们可以把节点定义做内部类‘

定义成静态内部类比较方便应用，再者为什么next的类型时ListNode呢，因为每个节点的nxet域是指向下一个节点的，因此头节点和next的类型均为ListNode；同时因为每个链表的头结点只有一个，所以应该定义在LIstNode之外。

实现链表方法

方法的实现方法有很多，一下只是讲述提供案例而已，只要能完整实现即可

在实现链表方法之前我们首先要学会如何将链表的节点连起来：

如图创建了四个节点，通过next将每个节点连起来；

所需要实现的方法：

  //头插法
        public void addFirst(MyStringLeList.ListNode node);
        //尾插法
        public void addLast(MyStringLeList.ListNode node);
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, MyStringLeList.ListNode node);
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key);
        //删除第一次出现关键字为key的节点
        public void remove(int key);

        //删除所有值为key的节点
        public void removeAllKey(int key);
        //得到单链表的长度
        public int size();
        //清空链表
        public void clear();
        //打印链表
        public void display();

打印链表

打印链表的时候只需要判断循环的结束条件和节点的传递即可；图中把head赋给cur是为了不遗失头节点

记数链表中节点个数；判断链表中是否有某个值：

这两个方法同打印类似较为简单，不多赘述。

头插法：

注意二者赋值顺序即可。

尾插法：

首先要判断链表是否为空；同时要注意循环的判断条件是cur.next而不是cur。cur.next !=null时，cur指向是最后一个节点。

指定插入：

指定插入我们要分情况，如果越界我们会抛出异常，如果是头，尾插那直接调用方法；这里需要注意的是，如果我们需要插入第三个位置，那么应该找到第二个位置的节点，因为单向链表只能向后传递，如果找到的是第三个节点那么就无法访问到第二个节点，从而不能通过第二个节点的next去连接插入的节点。相反当找到第二个节点之后可以通过next访问第三个节点；通常我们要先连接好后面的节点再来管前面的

通过对应值删除节点：

我们要考虑链表是否为空，如果为空那么return即可，如果不为空那我们就进行删除；即将所需删除节点的前一个节点的next指向所删除节点的下一个节点（上图最后一行）；因此我们首先要找到前一个节点，实现过上述方法可知想要找到当前节点那么while条件为cur.val;那么显而易见若想循环结束时cur是前一个节点，条件自然为：cur.next.val;写完后分析代码可知，这无法删除第一个节点，因此要另外写一个条件。

如果观察深入可知，起始对应值的节点并未正真删除只是之前的节点不再指向它，但是它依然存在并指向原本的下一个节点，此时我们要想真正删除，只有一个cur是不行的，因为我们一旦改变了对应值前一个节点的引用那我们就无法找到对应值的节点，因此我们的做法是再增添一个curNext去指向它，将curNext,next设置为空即可。

在上图基础上增添两行代码即可。

删除所有对应值节点：

和上个写法大致相同，有一点需要注意，此时必须将头节点值判断放在后面；因为删除节点1后，节点2又变成了头部，那么我们又需要去单独判断该头部是否需要被删除。因此我们可以先将头部后面的都整理完再回头看头部节点即可。

同时要注意判断链表是否为空。

我在刷题专栏中精选了而多道链表题并附有讲解，大家可以去检验一下自己学的如何

LinkedListd的介绍

LinkedList的定义：

链表的集合类；

LinkedList是个双向不带头非循环链表。

包含数值域，next域(指向下一个节点)，prev域(指向前一个节点)

LinkedList的常见方法：

在前面已经实现过了单向链表，双向链表就会很简单，把方法过一遍就可以了；

我们实现方法时默认链表是int，这只是为了方便起见，实际上LinkedList是一个泛型类；

我们为了更好的认识LinkedList来看一下其部分源码：

LinkedList的有参构造方法：

LinkedList里的参数是Collection<? extends E>c,这里我在ArrayList有讲过：

ArrayList实现了Collection这个接口，同时我们定义的arrayList是Integer，所以满足上诉条件；简而言之就是说在实例化LinkedList时我们可以传入一个集合(已经实现过Collection接口)，将这个集合类型转为LinkedList类型(LinkedList也是一种集合，即一种集合类型转为另一种集合类型)。

LinkedList的打印：

LinkedList可以用foreach打印也可以用迭代器打印，如上图，在这里不多赘述。

ArrayList和LinkedList的简单区别：

从插入，查找，修改，删除来区分

1 二者均为List接口下的两个集合，二者内部实现方面不同：ArrayList的底层是由数组实现的，通过索引访问数组元素，可以快速访问，二LinkedList的底层是由双向链表实现的，适合插入和删除元素；

2? 数据访问的时间复杂度不同：ArrayList的访问时间复杂度时O(1)LinkedList时O(n)

3? 空间占用，ArrayList的占用空间是连续的，但会产生空间碎片，即扩容出来的空间是多余的，而LinkedList不是连续的，但需要通过前后的引用，占用空间相对较大。