一、ArrayList的缺陷
在上一篇文章中我们已经熟悉了ArrayList的使用，并且进行了简单模拟实现。通过源码知道，ArrayList底层使用数组来存储元素
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// ...
// 默认容量是10
private static final int DEFAULT_CAPACITY = 10;
//...
// 数组：用来存储元素
transient Object[] elementData; // non-private to simplify nested class access
// 有效元素个数
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
}
}
// ...
}由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java 集合中又引入了LinkedList，即链表结构。
二、链表
1、链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
#注：
（1）从上图可以看出，链表结构在逻辑上是连续的，但在物理上不一定连续
（2）现实中的结点一般都是从堆上申请出来的
（3）从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
实际中的链表结构有很多种，但是重点掌握两种就可以了
（1）无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
（2）无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。
2、链表的实现
// 1、无头单向非循环链表实现
public class SingleLinkedList {
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
node.next = head;
head = node;
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null) {
head = node;
return;
}
ListNode cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
int len = size();
if(index < 0 || index > len) {
System.out.println("index位置不合法");
return;
}
if(index == 0) {
addFirst(data);
return;
}
if(index == len) {
addLast(data);
return;
}
//中间插入
ListNode cur = head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
if(head == null) {
return;
}
if(head.val == key) {
head = head.next;
return;
}
ListNode cur = findNodeOfKey(key);
if(cur == null) {
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
private ListNode findNodeOfKey(int key) {
ListNode cur = head;
while (cur.next != null) {
if(cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//删除所有值为key的节点
public void removeAllKey(int key){
if(head == null) {
return;
}
ListNode prev = head;
ListNode cur = head.next;
while (cur != null) {
if(cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
if(head.val == key) {
head = head.next;
}
}
//得到单链表的长度
public int size(){
int len = 0;
ListNode cur = head;
while (cur != null) {
len++;
cur = cur.next;
}
return len;
}
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode curN = cur.next;
cur.next = null;
cur = curN;
}
head = null;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
3、练习
对于链表而言，懂得是怎样实现的之后最好的方法也就是去做习题进行练习！！！
（1）删除链表中等于给定值 val 的所有结点。（203. 移除链表元素 - 力扣（LeetCode））
对于这个题，很简单，但是要记得考虑链表为空的情况。
然后去比较即可，若是相等就把其前一个结点的地址改为它后一个结点的地址，直接将相等的跳过即可（如第2个结点，就让第1个结点去存储第3个结点的地址）
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return head;
}
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
（2）反转一个单链表。（206. 反转链表 - 力扣（LeetCode））
这一题给了我们头结点（head），我们就可以依次找到后面的所有结点将我们所找到的结点依次进行头插入就可以完成（因为给了1，我们会依次得到2345，但是最终要得到54321，所以进行头插入）
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}（3）给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。（876. 链表的中间结点 - 力扣（LeetCode））
这里，我们需要用到一个新的解题方式----快慢指针（就是用两个指针同时出发）
在这个题里面要找到中间结点，那么就用两个指针，快指针一次走两步，慢指针一次走一步，那么当快指针走到末尾无法再走时，慢指针恰好走到中间（至于奇偶情况可以自行画图验证）
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}（4）将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。（21. 合并两个有序链表 - 力扣（LeetCode））
这里说到有序链表，所以可以先建立一个新的链表，再将两个旧链表从头依次开始比较，谁小谁就尾插进新链表，而其所在的链表就要拿出下一个结点进行下一轮的比较，直到一方为空（即比完了），那么让非空的链表将剩余部分尾插到新链表，再返回新链表头结点的下一个结点即可
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
（5）编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。（链表分割_牛客题霸_牛客网）
创建四个空表，两两一组，先比较与x的大小关系，（bs是小于x的头记录，be记录小于x的尾），第一次找到大于等于或小于的结点时都是先同时等于头结点，然后e依次去记录后面的，直到遍历完整个链表。这时要考虑小于x的链表为空的情况，若是为空直接返回大于x的链表，否则把小于x的链表的尾连接上大于x的链表的头（并且将大于x的链表尾结点置为null）
public ListNode partition(int x) {
// write code here
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = head;
while (cur != null) {
if(cur.val < x) {
//第一次插入
if(bs == null) {
bs = be = cur;
}else {
be.next = cur;
be = be.next;
}
}else {
if(as == null) {
as = ae = cur;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
if(bs == null) {
return as;
}
be.next = as;
//不管第二部分是否最后一个节点为空 都手动置为空
if(as != null) {
ae.next = null;
}
return bs;
}（6）链表的回文结构。（链表的回文结构_牛客题霸_牛客网）
和前面一样，先使用快慢指针找到中间结点，再用第二题的方法将整个链表进行反转，再依次进行比较，看是否完全相同
public boolean chkPalindrome() {
// write code here
if(head == null) return true;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//slow 指向的位置 就是中间节点
//2.进行翻转
ListNode cur = slow.next;
while (cur != null) {
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}
//3.判断回文
while (head != slow) {
if(head.val != slow.val) {
return false;
}
if(head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}（7）输入两个链表，找出它们的第一个公共结点。（160. 相交链表 - 力扣（LeetCode））
这里首先要清楚，两个链表如果有着公共结点，那么一定是Y字行的关系
小技巧：如果两个链表相交，那么同时出发，依次向后走一步，若是为空下一步走到另一个链表的头结点上，他们相遇时一定是在公共结点位置。（不相交则同时为null）
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = ((pA == null) ? headB : pA.next);
pB = ((pB == null) ? headA : pB.next);
}
return pA;
}
}（8）给定一个链表，判断链表中是否有环。（141. 环形链表 - 力扣（LeetCode））
这里依旧采用快慢指针，如果有环，那么一定会相遇，若是没有环，则快指针一定会先null
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}（9）给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL（142. 环形链表 II - 力扣（LeetCode））
依旧使用快慢指针操作，当两个指针相遇时，快指针走的距离是a+n(b+c)+b=a+(n+1)b+nc
快指针的速度是慢指针的一倍，所以a+(n+1)b+nc=2(a+b)==>a=c+(n−1)(b+c)，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}三、LinkedList
1、LinkedList的模拟实现
// 2、无头双向链表实现
public class MyLinkedList {
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(head == null) {
head = last = node;
}else {
node.next = head;
head.prev = node;
head = node;
}
}
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if(head == null) {
head = last = node;
}else {
last.next = node;
node.prev = last;
last = last.next;
}
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
int len = size();
if(index < 0 || index > len) {
return;
}
if(index == 0) {
addFirst(data);
return;
}
if(index == len) {
addLast(data);
return;
}
ListNode node = new ListNode(data);
ListNode cur = findIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
private ListNode findIndex(int index) {
ListNode cur = head;
while (index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
if(cur.val == key) {
//开始删除
if(cur == head) {
head = head.next;
if(head != null) {
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 != null) {
head.prev = null;
}
}else {
cur.prev.next = cur.next;
if(cur.next == null) {
last = last.prev;
}else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}
//得到单链表的长度
public int size() {
ListNode cur = head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
public void display() {
ListNode cur = head;
while (cur != null) {
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
public void clear() {
ListNode cur = head;
while (cur != null) {
ListNode curN = cur.next;
cur.prev = null;
cur.next = null;
cur = curN;
}
head = last = null;
}
}2、LinkedList的使用
2.1什么是LinkedList
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的结点中，然后通过引用将结点连接起来了，因此在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
2.2LinkedList的使用
（1）LinkedList的构造
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}（2）LinkedList的其他常用方法介绍
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
System.out.println(list);
// 在起始位置插入0
list.add(0, 0); // add(index, elem): 在index位置插入元素elem
System.out.println(list);
list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
list.removeFirst(); // removeFirst(): 删除第一个元素
list.removeLast(); // removeLast(): 删除最后元素
list.remove(1); // remove(index): 删除index位置的元素
System.out.println(list);
// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
if(!list.contains(1)){
list.add(0, 1);
}
list.add(1);
System.out.println(list);
System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
int elem = list.get(0); // get(index): 获取指定位置元素
list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
List<Integer> copy = list.subList(0, 3);
System.out.println(list);
System.out.println(copy);
list.clear(); // 将list中元素清空
System.out.println(list.size());
}（3）LinkedList的遍历
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1); // add(elem): 表示尾插
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
System.out.println(list.size());
// foreach遍历
for (int e:list) {
System.out.print(e + " ");
}
System.out.println();
// 使用迭代器遍历---正向遍历
ListIterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
System.out.println();
// 使用反向迭代器---反向遍历
ListIterator<Integer> rit = list.listIterator(list.size());
while (rit.hasPrevious()){
System.out.print(rit.previous() +" ");
}
System.out.println();
}4、ArrayList和LinkedList的区别
