1.链表
1.1为什么要引入链表
上一篇文章中我们介绍了ArrayList，ArrayList的底层是通过数组实现的，具有随机访问效率高等特点，那么我们为什么还需要引入链表呢?
这是因为ArrayList底层通过数组实现，当在ArrayList任意位置(除了最后一位)进行插入和删除操作时，就需要将后续的元素整体向前或者向后进行搬移，时间复杂度为O(n)，效率比较低，由此可见ArrayList很不适合在一些插入或者删除操作较多的场景，而java集合中引入了链表，可以很好改善这个问题
1.2链表的概念和结构
链表是一种物理存储上非连续的存储结构，数据元素上的逻辑顺序是通过链表中的引用实现的。不同于数组，链表的物理存储单元可以分散在内存中的任意位置，通过节点(每个节点包含两部分：数据域和指针域。数据域用于存储数据元素，指针域则存储指向下一个节点的引用)之间的引用将它们连接起来形成一个线性序列
在Java中用对象引用代替指针
链表的结构多种多样，主要分为以下6种结构：
1.单向链表或双向链表
2.带头链表或者不带头链表
3.循环链表或者非循环链表
1.3实现一个单链表
public class SingleLinkedList{//头插法public void addFirst(int data){}//尾插法public void addLast(int data){}//任意位置插入public void addIndex(int index,int data){}//查询链表中是否含有关键字keypublic boolean contains(int key){}//删除第一次出现关键字key的节点public void remove(int key){}//删除所有值为key的节点public void removeAllKey(int data){}//得到单链表的长度public int size(){}//清空所有节点，清空单链表public void clear(){}//打印单链表public void display(){}
}实现思路：
1.addFirst(int data)在单链表头部进行插入操作，只需要创建一个新的节点将新节点的value属性赋值为data，并将新节点的next指向原来链表的头部节点即可
2.addLast(int data)在单链表尾部进行插入操作，只需要创建一个新的节点将新节点的value属性赋值为data，并将原链表尾部的节点的next指向新的节点即可
3.addIndex(int pos,int data)在链表指定位置插入元素，首先要判断插入的位置是否合法，如果合法则分别需要修改要将原来插入位置的元素的next指向新节点，并且新节点的next要指向插入位置后面的那个节点
4.contains(int key)判断链表是否包含元素key，只需要依次遍历链表，获取到每个节点的元素并进行判断
5.remove(int key)删除元素key，遍历链表，找到key所在的位置，将key前一个元素的next指向key后面的元素即可
6.removeAllKey(int key)删除元素值为key的所有元素，每找到一个值为key的元素要进行判断key是否有前后节点，再进行相应的删除操作
7.size()返回链表中的节点个数，可以通过遍历链表并设置计数器，通过计数器统计链表中结点的个数
8.display()打印链表，遍历并依次打印每个节点的元素
2.LinkedList
2.1什么是LinkedList
LinkedList是Java集合框架中的链表，LinkedList是基于双向链表实现的，由于链表中没有将元素存储在连续的空间内，元素存储在单独的节点中，然后通过引用将节点连接起来，因此在任意位置插入或者删除元素，不需要搬移元素，效率比较高。
LinkedList中的节点结构：
说明：
1.LinkedList实现了List接口
2.LinkedList的底层使用了双向链表
3.LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.LinkedList的任意位置插入和删除操作效率比较高，时间复杂度为O(1)
5.LinkedList比较适合插入删除比较多的场景
6.LinkedList的访问效率比较低，时间复杂度为O(n)
2.2LinkedList的构造方法
| 方法 | 解释 |
| LinkedList() | 无参构造 |
| public LinkedList(Collection<? extends E> c) | 使用其他集合容器种的元素构造List |
代码演示：
public class Test {public static void main(String[] args) {//构造一个空的LinkedListList<Integer> list1=new LinkedList<>();System.out.println(list1);List<String> list=new java.util.ArrayList<>();list.add("hajimi");list.add("hahaha");list.add("lalala");//使用ArrayList构造LinkedListList<String> list2=new LinkedList<>(list);System.out.println(list2);}
}
2.3LinkedList的常用方法
| 方法 | 解释 |
| boolean add(E,e) | 在尾部插入元素e |
| void add(int index,E e) | 将元素e插入到index的位置 |
| boolean addAll(Collection<? extends E> c) | 在尾部插入c中的所有元素 |
| E remove(int index) | 删除index位置的元素 |
| boolean remove(Object o) | 删除第一个o元素 |
| E get(int index) | 获取下标为index位置元素 |
| E set(int index,E e) | 将下标为index位置的元素设置为e |
| void clear() | 清空链表中的所有元素 |
| boolean contains(Object o) | 判断o是否在线性表中 |
| int indexOf(Object o) | 返回第一个o所在的下标 |
| int lastIndexOf(Object o) | 返回最后一个o所在的下标 |
| List<E> subList(int fromIndex,int toIndex) | 截取部分list |
代码演示：
import java.util.*;public class Test {public static void main(String[] args) {List<String> list=new LinkedList<>();//在链表末尾插入元素list.add("My");list.add("name");list.add("hajimi");System.out.println(list);//在指定位置插入元素list.add(2,"is");System.out.println(list);list.add(4,"king");System.out.println(list);//删除指定位置的元素list.remove(4);System.out.println("进行删除操作后的链表"+list);//删除指定元素list.remove("My");System.out.println("进行删除操作后的链表"+list);//获取指定位置的元素System.out.println(list.get(2));//将指定位置下标的元素设置为eSystem.out.println(list.set(0,"Your name"));System.out.println(list);//判断线性表中是否包含某元素System.out.println(list.contains("hajimi"));list.add("hajimi");//返回指定元素第一个出现的下标System.out.println(list.indexOf("hajimi"));//返回指定元素最后一次出现的下标System.out.println(list.lastIndexOf("hajimi"));//截取部分链表内容List<String> partList;partList=list.subList(0,3);System.out.println("截取的部分："+partList);//在链表尾部插入其他容器的所有元素list.addAll(partList);System.out.println(list);//清空链表中的所有元素list.clear();System.out.println(list);}
}
2.4LinkedList的遍历
LinkedList遍历主要有3中方式：
1.使用for循环搭配链表长度进行遍历
2.使用foreach循环
3.使用迭代器进行遍历
代码演示：
import java.util.*;public class Test {public static void main(String[] args) {List<String> list=new LinkedList<>();list.add("My");list.add("name");list.add("is");list.add("hajimi");list.add("king");list.add("!");//使用for循环搭配链表长度进行遍历链表for (int i=0;i<list.size();i++){System.out.print(list.get(i)+" ");}System.out.println();//使用foreach循环遍历链表for(String s:list){System.out.print(s+" ");}System.out.println();//使用迭代器遍历链表//正向遍历ListIterator<String> it= list.listIterator();while(it.hasNext()){System.out.print(it.next()+" ");}System.out.println();//反向遍历ListIterator<String> rit= list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous()+" ");}}
}2.5实现一个LinkedList
LinkedList原码中节点的结构如下：
实现一个泛型为Integer的链表，代码演示：
public class MyLinkedList2 {static class ListNode{private ListNode prev;private int val;private ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode tail;public MyLinkedList2(){}//头插法public void addFirst(int data){ListNode newNode=new ListNode(data);if(head==null){head=tail=newNode;}else {newNode.next=head;head.prev=newNode;head=newNode;}}//尾插法public void addLast(int data){ListNode newNode=new ListNode(data);if(head==null){head=tail=newNode;}else {newNode.prev=tail;tail.next=newNode;tail=newNode;}}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){if(index<0||index>size()){System.out.println("要插入的位置不合法");return false;}if(index==0){addFirst(data);return true;}if(index==size()){addLast(data);return true;}ListNode cur=head;while(index!=0){cur=cur.next;index--;}ListNode newNode=new ListNode(data);newNode.next=cur;newNode.prev=cur.prev;cur.prev.next=newNode;cur.prev=newNode;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){if (head==null){System.out.println("链表为空");return false;}ListNode cur=head;while (cur!=null){if(cur.val==key){System.out.println("找到了!");return true;}cur=cur.next;}System.out.println("没找到");return false;}//删除第一次出现关键字为key的节点public void remove(int key){if (head==null){System.out.println("链表中没有元素，无法进行删除");return;}ListNode cur=head;while (cur!=null){if(cur.val==key){//判断是否是链表尾部删除if(cur.next==null){cur.prev.next=null;tail=tail.prev;}//删除中间节点操作cur.prev.next=cur.next;cur.next.prev=cur.prev;}cur=cur.next;}//判断首节点情况if(head.val==key){//如果链表只有一个节点，需要进行特殊处理if(head.next!=null){head=head.next;head.prev=null;}else {head=null;}}}//删除所有值为key的节点public void removeAllKey(int key){if(head==null){return;}ListNode cur=head.next;while(cur!=null){if(cur.val==key){if(cur.next==null){cur.prev.next=null;tail=tail.prev;}else{cur.prev.next=cur.next;cur.next.prev=cur.prev;}}cur=cur.next;}if(head.val==key){if(head.next==null){head=null;}else{head=head.next;head.prev=null;}}}//得到单链表的长度public int size(){int count=0;ListNode cur=head;while(cur!=null){cur=cur.next;count++;}return count;}public void display(){ListNode cur=head;if(head==null){return;}while(cur!=null){System.out.print(cur.val+" ");cur=cur.next;}System.out.println();}public void clear(){ListNode cur=head;if(head==null){return;}while(cur!=null){ListNode curNext=cur.next;cur.prev=null;cur.next=null;cur=curNext;}//处理还在引用的head和tailhead=null;tail=null;}
}
对上述代码进行运行测试：
public class Test {public static void main(String[] args) {MyLinkedList2 myLinkedList2=new MyLinkedList2();myLinkedList2.addLast(1);myLinkedList2.addLast(2);myLinkedList2.addFirst(3);myLinkedList2.addIndex(2,6);myLinkedList2.addIndex(0,5);myLinkedList2.addIndex(1,4);myLinkedList2.display();System.out.println(myLinkedList2.contains(6));myLinkedList2.remove(6);myLinkedList2.display();myLinkedList2.addFirst(1);myLinkedList2.display();myLinkedList2.removeAllKey(1);myLinkedList2.display();System.out.println(myLinkedList2.size());myLinkedList2.clear();myLinkedList2.display();}
}
3.LinkedList的特点
LinkedList的特点主要体现在以下几个方面：
1.数据存储的方式
LinkedList是通过一系列节点组成的，每个节点都包含三个部分，数据元素，指向前一个节点的引用和指向后一个节点的引用，链表的内存是动态分配的，每个节点的内存空间是独立分配的，使得链表的大小灵活可调
2.操作效率
在链表头部或者尾部插入和删除元素操作的时间复杂度为O(1)，如果已经获得目标节点的引用，进行插入和删除操作的时间复杂度为O(1)，但如果没有则需要从头遍历找到目标位置，时间复杂度为O(n)
链表不支持随机访问，方位任意元素都需要从头开始进行遍历，时间复杂度为O(n)
3.内存使用
每个节点除了存取数据元素外，还需要存储引用，有额外的内存开销。链表的内存分配时动态的，不会像数组那样分配固定的大小
4.适用场景
适合插入和删除频繁的场景，不适合随机访问的场景，适合数据量不确定的场景(动态扩展，不过多浪费空间)
4.LinkedList和ArrayList的区别
| 不同点 | ArrayList | LinkedList |
| 存储空间上 | 物理上连续的 | 逻辑上连续，物理上不一定连续 |
| 随机访问 | 支持，时间复杂度O(1) | 不支持，时间复杂度O(n) |
| 插入/删除 | 需要搬运元素，效率低，时间复杂度O(n) | 只需要修改引用的指向，时间复杂度O(1) |
| 扩容机制 | 当数组空间不足时，会创建一个更大的数组并复制原数据 | 动态分配内存，每次插入时动态分配新节点 |
| 内存使用 | 内存分配连续，可能有空间浪费（预留空间），但内存使用效率较高。 | 每个节点需要额外存储指针，内存使用相对较高。 |
| 适用场景 | 元素频繁访问的场景 | 插入删除频繁的场景 |
