【算法篇】四种链表总结完毕，顺手刷了两道面试题

今日目录：
1：能够说出链表的存储结构和特点
2：能够说出链表的几种分类及各自的存储结构
3：能说出链表和数组的差异
4：完成实战演练题目
5：完成综合案例
1、概念及存储结构

问题：思考一下动态数组ArrayList存在哪些弊端？
1：插入，删除时间复杂度高
2：可能会造成内存空间的大量浪费
3：需要一块连续的存储空间，对内存的要求比较高，比如我们要申请一个1000M的数组，如果内存中没有连续的足够大的存储空间则会申请失败，即便内存的剩余可用空间大于1000M，仍然会申请失败。
结论：能否做到用多少内存空间就申请多少内存？

链表（Linked list）是一种物理存储单元上非连续、非顺序的存储结构，链表中的每一个元素称之为结点（Node），结点之间用指针（引用）连接起来，指针的指向顺序代表了结点的逻辑顺序，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表能解决数组不能解决的事情吗？
1：链表天生就具备动态扩容的特点，不需要像动态数组那样先申请一个更大的空间，然后将原空间内的数据拷贝到新空间；能够避免内存空的大量浪费
2：链表不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来使用，所以如果我们申请一个1000M大小的链表，只要内存剩余的可用空间大于1000M，便不会出现问题。
但是需注意：存储同样的数据，链表要比数组耗费内存！

2、链表分类

链表根据其结点之间的连接形式我们又可分为：单链表，双向链表，循环链表，双向循环链表
2.1、单链表

单链表就是我们刚刚讲到的链表的最基本的结构，链表通过指针将一组零散的内存块串联在一起。。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next ，如果链表中的某个节点为p，p的下一个节点为q，我们可以表示为：p.next=q

链表中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址,有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

与数组一样，链表也支持数据的查找、插入和删除操作。
在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是 O(n)。而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的。
如图所示，针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以插入删除的时间复杂度是 O(1)。


但是，有利就有弊。链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据针一个结点一个结点地依次遍历，直到找到相应的结点，所以，链表随机访问的性能没有数组好，查询的时间复杂度是O(n)。
2.2、双向链表

单向链表只有一个方向，结点只有一个后继指针 next。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点，如图所示

从图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性，比如
1：可以在O(1)时间内找到给定结点的前驱节点，而对于单链表则需要O(n)的时间
2：根据索引来查找元素时可极大提升查找效率
.....
在很多场景下双向链表都比单向链表更加高效，这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。如果你熟悉 Java 语言，你肯定用过LinkedHashMap 这个容器。如果你深入研究 LinkedHashMap 的实现原理，就会发现其中就用到了双向链表这种数据结构。
实际上，这里有一个更加重要思想就是用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机等存储容量小的设备上，这个时候，就要反过来用时间换空间的设计思路。比如最典型的缓存系统就是一个用空间换时间的思想。

2.3、循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表，和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表，循环链表的结构如图所示

2.4、双向循环链表

了解了循环链表和双向链表，如果把这两种链表整合在一起就是一个双向循环链表

3、小结&实战

3.1、链表数组对比

数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反，下图表明了链表和数组在插入删除和随机访问上时间复杂度的对比

3.2、206. 反转链表

字节跳动，腾讯，阿里，美团点评最近面试题，206. 反转链表
高频题
双指针迭代

1. class Solution {
2.     public ListNode reverseList(ListNode head) {
3.         
4.         ListNode prev = null;
5.         ListNode curr = head;
6.         while (curr !=null) {
7.             ListNode temp = curr.next;
8.             curr.next = prev;
9.             prev = curr;
10.             curr = temp;
11.         }
12.         return prev;
13.     }
14. }

复制代码

3.3、141. 环形链表

阿里，腾讯，百度最近面试题，141. 环形链表
快慢指针

1. public class Solution {
2.     public boolean hasCycle(ListNode head) {
3.         //特殊判断
4.         if (head == null || head.next == null) {
5.             return false;
6.         }
7.         ListNode fast = head;
8.         ListNode slow = head;
9.         //两个指针分别下后走
10.         while (true) {
11.             fast = fast.next.next;
12.             slow = slow.next;
13.             
14.             if (fast == null || fast.next == null) {
15.                 return false;
16.             }
17.             if (fast == slow) {
18.                 break;
19.             }
20.         }
22.         return true;
23.     }
24. }

复制代码

4、综合案例

4.1、需求

​        在学习数组的时候我们基于数组实现了一个List容器，支持数据的添加，修改，删除，查询等操作，今天学习完链表之后能够基于链表来实现一个LinkedList容器呢？
要求：
1：要求和动态数组ArrayList具备相同的功能
2：请基于双向链表实现，
4.2、实现

（1）定义接口，com.itheima.linkedlist.inf.List，接口方法跟之前实现ArrayList时一样，只不过添加上泛型

1. package com.itheima.linkedlist.inf;
3. /**
4. * Created by 传智播客*黑马程序员.
5. */
6. public interface List<E> {
9.     /**
10.      * 返回容器中元素的个数
11.      * @return
12.      */
13.     int size();
15.     /**
16.      * 判断容器是否为空
17.      * @return
18.      */
19.     boolean isEmpty();
20.     /**
21.      * 查询元素在容器中的索引下标
22.      * @param o 元素对象
23.      * @return  在容器中的下标 不存在则返回-1
24.      */
25.     int indexOf(E o);
26.     /**
27.      * 判断容器是否包含某个特定的元素
28.      * @param e
29.      * @return
30.      */
31.     boolean contains(E e);
33.     /**
34.      * 将元素添加到容器结尾
35.      * @param e 要添加的元素
36.      * @return  是否添加成功
37.      */
38.     boolean add(E e);
40.     /**
41.      * 向指定位置添加元素
42.      * @param index    位置下标
43.      * @param element  元素对象
44.      */
45.     void add(int index, E element);
47.     /**
48.      * 用指定的元素替换指定位置的数据
49.      * @param index    指定的位置索引下标
50.      * @param element   新的元素
51.      * @return          原始的元素
52.      */
53.     E set(int index, E element);
55.     /**
56.      * 获取指定位置的元素
57.      * @param index   索引下标
58.      * @return        该位置的元素
59.      */
60.     E get(int index);
62.     /**
63.      * 移除指定位置的元素
64.      * @param index 索引下标
65.      * @return      被移除的元素
66.      */
67.     E remove(int index);
70.     /**
71.      * 清除容器中所有元素
72.      */
73.     void clear();
74. }

复制代码

（2）创建接口实现：com.itheima.linkedlist.LinkedList，实现对应接口
（3）容器要基于双向链表实现，链表是由一个一个结点构成的，因此定义链表结点对象，编写一个静态的内部类

1. //定义链表结点对象
2. private static class  Node<E>{
3.     E val;
4.     Node<E> prev;
5.     Node<E> next;
7.     //定义构造
8.     public Node(Node<E> prev,E val,Node<E> next){
9.         this.prev = prev;
10.         this.val = val;
11.         this.next = next;
12.     }
14. }

复制代码

（4）定义相关的成员变量

1. //定义容器中元素的个数
2. int size;
3. //定义链表的头结点
4. Node<E> first;
5. //定义链表的尾结点
6. Node<E> last;

复制代码

（5）完成size,isEmpty,indexOf,contains等方法的编写

1. @Override
2. public int size() {
3.     return size;
4. }
6. @Override
7. public boolean isEmpty() {
8.     return size == 0;
9. }
11. @Override
12. public int indexOf(E o) {
13.     int index = 0;
14.     //分情况 o是否为null，为null和不为null判断的方式不一样，null是用==，不为null用equals
15.     if (o == null) {
17.         for ( Node x = first;x!=null;x=x.next) {
18.             if (x.val == null) {
19.                 return index;
20.             }
21.             index++;
22.         }
23.     }else {
24.         for ( Node x = first;x!=null;x=x.next) {
25.             if (o.equals(x.val)) {
26.                 return index;
27.             }
28.             index++;
29.         }
30.     }
31.     return -1;
32. }
34. @Override
35. public boolean contains(E e) {
36.     return indexOf(e) != -1;
37. }

复制代码

（6）完成add方法的编写

1. @Override
2. public boolean add(E e) {
3.     //添加是将元素值添加到链表尾部
4.     linkLast(e);
5.     return true;
6. }
8. private void linkLast(E e) {
9.     Node l = last;
10.     Node newNode = new Node(l,e,null);
11.     last = newNode;
13.     if (l==null) {
14.         //第一次添加
15.         first = newNode;
16.     }else {
17.         l.next = newNode;
18.     }
19.     size++;
20. }
22. @Override
23. public void add(int index, E element) {
24.     //检查索引
25.     checkIndex(index);
26.     if (index == size) {
27.         linkLast(element);
28.     }else {
29.         linkBefore(element,node(index));
30.     }
31. }
33. /**
34.      * 在指定结点前添加一个元素
35.      * @param element
36.      * @param node
37.      */
38. private void linkBefore(E element, Node<E> node) {
39.     Node<E> prev = node.prev;
40.     Node<E> newNode = new Node<E>(prev,element,node);
41.     node.prev = newNode;
43.     if (prev == null) {
44.         first = newNode;
45.     }else {
46.         prev.next = newNode;
47.     }
48.     size++;
49. }
51. /**
52.      * 查找索引为index的结点
53.      * @param index
54.      * @return
55.      */
56. private Node<E> node(int index){
57.     //折半查找
58.     if ( index < (size >> 1)) {
59.         //从头开始查找
60.         Node<E> f = first;
61.         for (int i = 0;i< index;i++) { //i<index注意不能是i<=index 因为当i=index-1时 f=f.next其实f已经指向了索引为index位置的元素了
62.             f = f.next;
63.         }
64.         return f;
65.     }else {
66.         //从尾开始查找
67.         Node<E> l = last;
68.         for (int i=size-1;i> index;i--) {//同上
69.             l = l.prev;
70.         }
71.         return l;
72.     }
73. }
75. private void checkIndex(int index) {
76.     if (index < 0 || index > size) {
77.         throw new IndexOutOfBoundsException("index"+index+",size="+size);
78.     }
79. }

复制代码

（7）完成set，get方法的编写

1. /**
2.      * 替换指定索引位置的元素
3.      * @param index    指定的位置索引下标
4.      * @param element   新的元素
5.      * @return
6.      */
7. @Override
8. public E set(int index, E element) {
9.     isElementIndex(index);
10.     Node<E> oldNode = node(index);
11.     E oldVal = oldNode.val;
12.     oldNode.val = element;
13.     return oldVal;
14. }
16. private void isElementIndex(int index) {
17.     if (index < 0 || index >=size) {
18.         throw new IndexOutOfBoundsException("index="+index+",size="+size);
19.     }
20. }
22. @Override
23. public E get(int index) {
24.     isElementIndex(index);
25.     return node(index).val;
26. }

复制代码

（8）完成remove方法的编写

1. @Override
2. public E remove(int index) {
3.     isElementIndex(index);
4.     Node<E> node = node(index);
5.     return unlink(node);
6. }
8. private E unlink(Node<E> node) {
9.     Node<E> prev = node.prev;
10.     Node<E> next = node.next;
11.     E val = node.val;
12.     node.val = null;
14.     //node是头结点
15.     if (prev == null) {
16.         first = next;
17.     }else {
18.         prev.next = next;
19.         node.prev = null;
20.     }
22.     //node是尾结点
23.     if (next == null) {
24.         last = prev;
25.     }else {
26.         next.prev = prev;
27.         node.next = null;
28.     }
29.     size--;
30.     return val;
31. }

复制代码

（9）完成clear，toString方法的编写

1. @Override
2. public void clear() {
3.     for (Node l = first;l!=null;) {
4.         Node next = l.next;
5.         l.val = null;
6.         l.prev = null;
7.         l.next = null;
8.         l = next;
9.     }
11.     first = last = null;
12.     size=0;
13. }
14. @Override
15. public String toString() {
16.     //输出 1->2->Null格式的数据
17.     StringBuilder stringBuilder = new StringBuilder();
18.     for (Node l=first;l!=null;l = l.next) {
19.         stringBuilder.append(l.val).append("->");
20.     }
21.     stringBuilder.append("Null");
22.     return stringBuilder.toString();
23. }

复制代码

（10）编写测试类：com.itheima.linkedlist.LinkedListTest

1. public static void main(String[] args) {
2.     List list = new LinkedList();
3.     list.add(1);
4.     list.add(2);
5.     list.add(3);
6.     System.out.println("容器内元素为:"+list); // 1->2->3->Null
7.     System.out.println("容器内元素个数:"+list.size()+"容器是否为空:"+list.isEmpty());
8.     System.out.println("容器中是否包含3:"+list.contains(3));
9.     list.add(0,4);// 4->1->2->3->Null
10.     System.out.println("容器内元素为:"+list);
11.     list.add(3,5);//4->1->2->5->3->Null
12.     System.out.println("容器内元素为:"+list);
13.     list.add(2,6);//4->1->6->2->5->3->Null
14.     System.out.println("容器内元素为:"+list);
15.     System.out.println("获取索引为0的元素:"+list.get(0));
16.     System.out.println("获取索引为5的元素:"+list.get(5));
17.     System.out.println("获取索引为2的元素:"+list.get(2));
18.     list.remove(0);//1->6->2->5->3->Null
19.     System.out.println("容器内元素为:"+list);
20.     list.remove(3);//1->6->2->3->Null
21.     System.out.println("移除后容器内元素为:"+list);
22.     list.clear();
23.     System.out.println("清空后为:"+list);
24. }

复制代码

查看输出结果！

容器内元素为:1->2->3->Null
容器内元素个数:3容器是否为空:false
容器中是否包含3:true
容器内元素为:4->1->2->3->Null
容器内元素为:4->1->2->5->3->Null
容器内元素为:4->1->6->2->5->3->Null
获取索引为0的元素:4
获取索引为5的元素:3
获取索引为2的元素:6
容器内元素为:1->6->2->5->3->Null
移除后容器内元素为:1->6->2->3->Null
清空后为:Null

本文由传智教育博学谷 - 狂野架构师教研团队发布
如果本文对您有帮助，欢迎关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力
转载请注明出处！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！