JAVA-链表

1.链表的概念及结构

链表是一种物理存储结构上非连续存储结构(逻辑上连续)，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

注意：

根据上图可看出，链表是在逻辑结构连续的，但是在物理结构上不一定
现实中的结点一般都是通过堆上申请出来的
从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能是连续的，也可能不连续

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.无头单向非循环链表的实现

2.1 创建类

java">public class MySingleLinkedList {static class ListNode{public int val;public ListNode next;public ListNode(int val) {//创建链表时赋值this.val = val;}}public ListNode head;//代表链表的头节点//创建链表public void createNode() {//默认存在这么多链表ListNode node1 = new ListNode(12);ListNode node2 = new ListNode(34);ListNode node3 = new ListNode(45);ListNode node4 = new ListNode(56);ListNode node5 = new ListNode(78);//创建好后，将他们连接起来node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;//将表头，赋值给head标记this.head = node1;}
}

那么此时链表大概是这样的，地址是我随意编的：

2.2 addLast

尾插

java">//尾插public void addLast(int val) {//如果还没有创建节点，就把node做为首节点ListNode node = new ListNode(val);if(head == null) {head = node;return;}//遍历到末尾并连接//因为不能移动头结点，让一个引用指向头结点ListNode cur = head;//cur.next刚好走到最后一个结点while(cur.next != null) {cur = cur.next;}//循环出来刚好是最后一个结点，直接连接cur.next = node;}

注意：

循环遍历的时候一定注意循环判断条件的区别

如果是cur != null

cur会遍历到这里才结束

如果是cur.next != null

刚好遍历到最好一个结点，这样就可以直接和新结点连接

2.3 addFirst

头插

java">//头插public void addFirst(int val) {ListNode node = new ListNode(val);//1.链表是否为空if(head == null) {head = node;return;}//2.正常情况node.next = head;head = node;}

如果不是第一个结点，直接将新结点的next指向头结点，就连接起来了，再把新结点做为新的头结点

2.4 size

计算结点个数

java">//计算链表大小public int size() {int count = 0;ListNode cur = head;while(cur != null) {count++;cur = cur.next;}return count;}

唯一注意的依然是循环判断条件：必须是cur ！= null , 否则最后一个结点不会被统计到

2.5 addIndex

指定位置插入

java">//指定位置插入public void addIndex(int index, int val) {//1.判断index的合法性try {checkIndex(index);} catch (IndexNotLegalException e) {e.printStackTrace();}//2.index == 0 || index == size()if(index == 0) {//头插addFirst(val);return;}if(index == this.size()) {//尾插addLast(val);return;}//3.找到index前一个位置ListNode cur = findIndexSubOne(index);//4.链接//顺序不能改,不然就找不到后驱结点了ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}//找到要插入位置的前一个结点private ListNode findIndexSubOne(int index) {int count = 0;//写0就是把首地址默认为0下标，写1计算默认1下标ListNode cur = head;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) {if(index < 0 || index > this.size()) {throw new IndexNotLegalException("index不合法");}}

涉及到下标越界访问最好设计一个异常：

java">public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {super();}public IndexNotLegalException(String e) {super(e);}
}

为了更好的让你们理解画一图：

假设我要插入的位置是3

插入后：

2.5 contains

是否有值为val的结点

java">public boolean contains(int val) {ListNode cur = head;while(cur != null) {//依次遍历，找到了就返回trueif(cur.val == val) {return true;}cur = cur.next;}return false;
}

2.6 remove

删除val值为key的第一个结点

java">public void remove(int key) {//1.null链表情况if(head == null) {return;}//2.删除首if(head.val == key) {head = head.next;return;}//3.正常情况ListNode cur = head;while(cur.next != null) {if(cur.next.val == key) {ListNode cN = cur.next;cur.next = cN.next;return;}cur = cur.next;}
}

正常情况可能难以理解，画个图解释一下：

假设我们要找到的是56

我估计会有人看迷糊循环条件，不是说cur.next不会算上最后一个结点吗？那最后一个结点怎么删除啊？

注意看我们的判断条件，我们判断的是cur.next.val == key 也就是下一个结点的值。如果刚好是最好一个结点的值，想象一下，cur会直接指向null。所以最后一个节点不会有问题，但是第一个节点是判断不到的。所以我们在前面就判断是否为第一个节点。

2.7 removeAllKey

删除所有key

java">public void removeAllKey(int key) {//正常处理ListNode prev = head;ListNode cur = head.next;while(cur != null) {if(cur.val == key){prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//处理头节点,什么的程序没有探测头节点if(head.val == key) {head = head.next;}}

解析：

2.8 clear

关闭链表

直接让head为空，那就没有引用指向链表了他们都会被JVM回收

java">public void clear() {this.head = null;
}

2.9 display

这并不是链表里面有的一个方法，为了方便看结构，写的输出方法

java"> //显示public void display() {ListNode cur = head;while(cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}

我就不带着大家看最终结构了，自己复制过去看看吧

3.什么是LinkedList

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList也实现了List接口，具体如下：

【说明】

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList没有实现RandomAccess接口

4. LinkedList的任意位置插入和删除元素时效率比较高，删除的时间复杂度为O(n)不需要移动元素，插入的复杂度还是O(n)但依然因为不需要移动元素比顺序表快

5. LinkedList比较适合任意位置插入的场景

3.1 LinkedList实现

大部分代码都很简单我就不啰嗦了，有了前面的基础这个很简单。

java">// 2、无头双向链表实现
public class MyLinkedLIst {static class ListNode {int val;public ListNode prev;//前驱public ListNode next;//后驱public ListNode(int val){this.val = val;}}public ListNode head;//头节点public ListNode last;//尾节点//得到单链表的长度public int size(){ListNode cur = head;int count = 0;while (cur != null) {cur = cur.next;count++;}return count;}public void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//头插法public void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {//1.还没有节点head = last = node;} else {//2.正常情况node.next = head;head.prev = node;head = node;}}//尾插法public void addLast(int data){ListNode node = new ListNode(data);if(last == null) {//1.没有节点情况head = last = node;}else {last.next = node;node.prev = last;last = node;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data) {//1.index是否合法try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//2.是否是头插或尾插if(index == 0) {addFirst(data);return;}if (index == size()) {addLast(data);return;}//3.正常情况ListNode node = new ListNode(data);//找到目标位置的前面位置ListNode tmp = findIndex(index);node.next = tmp.next;tmp.next = node;node.prev = tmp;node.next.prev = node;}private void checkIndex(int index) {if(index < 0 || index > size()) {throw new IndexNotLegalException("双向链表插入位置不合法: " + index);}}private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}//删除第一次出现关键字为key的节点public void remove(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;if(head.next == null) {//说明现在链表中只有一个节点last = null;}else {head.prev = null;}}else {//正常情况下cur.prev.next = cur.next;if(cur.next == null) {//已经是最后一个节点last = last.prev;}else {cur.next.prev = cur.prev;}}return;//删完一个就走}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {if(cur == head) {head = head.next;if(head.next == null) {//说明现在链表中只有一个节点last = null;}else {head.prev = null;}}else {//正常情况下cur.prev.next = cur.next;if(cur.next == null) {//已经是最后一个节点last = last.prev;}else {cur.next.prev = cur.prev;}}//return;//删完一个就走}cur = cur.next;}}public void clear(){
//        last = head = null;  暴力版ListNode cur = head;while(cur != null) {ListNode curN = cur.next;cur.prev = null;cur.next = null;cur = curN;}}
}

3.2 remove和removeAllKey详解

唯一可能看不懂的就是remove，有太多判断条件了，那我就给大家一步步解释一下：

java">public void remove2(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {//把前驱结点的后驱，指向cur的后驱cur.prev.next = cur.next;//把后驱结点的前驱，指向cur的前驱cur.next.prev = cur.prev;return;}cur = cur.next;}
}

如果没有一些特殊情况这也就删完了。但是还有如果是最后一个结点，或者第一个结点就不能这么写。

处理删除最后一个结点情况：

java">public void remove(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {//把前驱结点的后驱，指向cur的后驱cur.prev.next = cur.next;//如果删除最后一个结点if(cur.next == null) {//让last直接往后走一步，就没有引用指向他了last = last.prev;}else {//把后驱结点的前驱，指向cur的前驱cur.next.prev = cur.prev;}return;}cur = cur.next;}
}

处理删除头结点的情况：

java">public void remove2(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {//删除头的情况if (cur == head) {//直接让head向后走一步head = head.next;//再将head前驱置为nullhead.prev = null;}else {//把前驱结点的后驱，指向cur的后驱cur.prev.next = cur.next;//如果删除最后一个结点if(cur.next == null) {//让last直接往后走一步，就没有引用指向他了last = last.prev;}else {//把后驱结点的前驱，指向cur的前驱cur.next.prev = cur.prev;}}return;}cur = cur.next;}
}

肯定很多人觉得差不多了，特殊情况都处理完了。但其实如果只有一个结点这里会报错：

处理一个结点情况：

java">public void remove2(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {//删除头的情况if (cur == head) {//直接让head向后走一步head = head.next;//处理只有一个结点的情况if (head == last) {head = last = null;}else {//再将head前驱置为nullhead.prev = null;}}else {//把前驱结点的后驱，指向cur的后驱cur.prev.next = cur.next;//如果删除最后一个结点if(cur.next == null) {//让last直接往后走一步，就没有引用指向他了last = last.prev;}else {//把后驱结点的前驱，指向cur的前驱cur.next.prev = cur.prev;}}return;//删完一个就走}cur = cur.next;}
}

那如果是removeAllKey，就是删除所有key。直接把return屏蔽就可以了，他会遍历完所有的结点。

3.2 LinkedList的使用

3.2.1 LinkedList的构造

java">public static void main(String[] args) {LinkedList<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(2);LinkedList<Integer> list2 = new LinkedList<>(list1);System.out.println(list2);//1 , 2ArrayList<Integer> list3 = new ArrayList<>();list3.add(12);list3.add(34);LinkedList<Integer> list4 = new LinkedList<>(list3);System.out.println(list4);//12 , 34
}

3.2.2 常用方法介绍

java">public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();//默认为尾插list.add(1);//1list.add(2);//1 2list.add(3);//1 2 3//指定位置插入list.add(2,10);//1 2 10 3ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(12);//12arrayList.add(34);//12 34//尾插所有元素list.addAll(arrayList);//1 2 10 3 12 34//删除下标为1的list.remove(1);// 1 10 3 12 34//删除值为3的结点//需要装箱,才好和int类型的remove做区分list.remove(Integer.valueOf(3));//1 10 12 34}

java">public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(12);//12list.add(23);//12 23list.add(34);//12 23 34list.add(45);//12 23 34 45list.add(56);//12 23 34 45 56//访问下标为2的元素System.out.println(list.get(2));//34//将下标为3的元素改为10list.set(3,10);//12 23 34 10 56//查找链表中是否有56System.out.println(list.contains(56));//true//返回元素为23的下标System.out.println(list.indexOf(23));//1list.add(12);//12 23 34 10 56 12//倒叙往前遍历，返回第一个访问到12的下标System.out.println(list.lastIndexOf(12));//5}

3.2.3 subList

截取代码中的指定区域

java">public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(12);//12list.add(23);//12 23list.add(34);//12 23 34list.add(45);//12 23 34 45list.add(56);//12 23 34 45 56List<Integer> list1 = list.subList(1,4);System.out.println(list1);//23 34 45list1.set(0,100);//100 34 45System.out.println(list);//12 100 34 45 56
}

他返回的是指定区域的首地址，所以对list1修改也会影响到list

4. LinkedList打印遍历

java">public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);System.out.println("===foreach===");for(Integer e : list) {System.out.print(e + " ");}System.out.println();System.out.println("===for===");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();System.out.println("===Iterator===");//返回的是一个新的结点指向链表头，数组中-1位置Iterator<Integer> it1 = list.iterator();//判断下一个是否有结点while (it1.hasNext()) {//移动到下一个结点并返回值System.out.print(it1.next() + " ");}System.out.println();System.out.println("===ListIterator===");//专门给List打印的ListIterator<Integer> it2 = list.listIterator();while (it2.hasNext()) {System.out.print(it2.next() + " ");}System.out.println();System.out.println("===listIterator(list.size())===");//倒叙打印ListIterator<Integer> it3 = list.listIterator(list.size());while (it3.hasPrevious()) {System.out.print(it3.previous() + " ");}}

结果：