链表（Linked List）
动态数组（Dynamic Array Or ArrayList）有一个明显的缺点
- 可能会造成内存空间的大量浪费
能否用到多少内存就分配多少内存
- 链表可以做到这一点
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
链表的设计
链表LinkedList包括元素个数size以及头结点first两个成员变量
每一个节点中又包括本节点特征元素element以及对下一个节点的引用next
接口设计
链表的大部分接口和动态数组是一致的
- 由于ArrayList与LinkedList的方法基本一致，但是很多方法的实现是完全不同的。因此可以使用一个接口声明所有的方法，使得这两个类可以通过实现同一个List接口,实现同样的功能。
/**
* 列表方法接口
* 接口只是声明，不需要实现
* @author l
*
* @param <E>
*/
public interface List<E> {
//接口类由于供实现他的类使用，因此默认都是public
static final int ELEMENT_NOT_FOUND = 0;
/**
* 元素的数量
*/
int size();
/**
* 是否为空
* @return
*/
boolean isEmpty();
/**
* 是否包含某个元素
* @param element
* @return
*/
boolean contains(E element);
/**
* 添加元素到最后面
* @param element
*/
void add(E element);
/**
* 返回index位置对应的元素
* @param index
* @return
*/
E get(int index);
/**
* 设置index位置的元素
* @param index
* @param element
* @return
*/
E set(int index, E element);
/**
* 在index位置添加元素
* @param index
* @param element
*/
void add(int index, E element);
/**
* 删除index位置对应的元素
* @param index
* @return
*/
E remove(int index);
/**
* 查看元素的位置
* @return
*/
int indexOf(E element);
/**
* 清除所有元素
*/
void clear();
//====以下是一些工具方法=========//
/**
* 确保索引正确
*/
void ensureRangeInternal(int index);
/**
* 确保插入时索引正确
*/
void ensureRangeOnAdd(int index); - 由于List定义的方法中，有一些方法的实现是完全一样的，这些方法在两个类中重复实现很冗余，但是接口List又无法实现，这时我们就可以定义一个抽象类AbstractList实现接口List,并将在链表和动态数组中相同的实现方法在抽象类中实现，根据Java中抽象类的特性，其他不同实现的方法完全可以不用管，交给子类实现即可，因此可以让ArrayList与LinkedList都继承AbstractList,这样就只需要重写需要的方法即可。
/**
* 抽象类用于抽取公共代码，有些方法可以交给子类实现
* @author lidengyin
*
*/
public abstract class AbstractList<E> implements List<E>{
//也是公共代码的一部分要对子类可用
protected static int size = 0;
/**
* 元素数量
*/
@Override
public int size() {
return size;
// TODO Auto-generated method stub
}
/**
* 是否为空
*/
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return size == 0;
}
/**
* 是否包含某个元素
*/
@Override
public boolean contains(E element) {
// TODO Auto-generated method stub
return indexOf(element) == List.ELEMENT_NOT_FOUND;
}
/**
* 添加元素到最后面
*/
@Override
public void add(E element) {
add(size, element);
// TODO Auto-generated method stub
}
/**
* 确保索引正确
*/
@Override
public void ensureRangeInternal(int index) {
// TODO Auto-generated method stub
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("inex out of bound");
}
}
/**
* 确保添加时索引正确
* @param index
*/
@Override
public void ensureRangeOnAdd(int index) {
// TODO Auto-generated method stub
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("index out of bound");
}
} - 在动态数组的设计中，我们用到了常量ELEMENT_NOT_FOUND，这个常量现在应该放在哪里呢？首先抽象类abstract是不能new的，其次abstract抽象类只是为了抽取公共代码，对外界不可见的，但是常量如果是由子类调用，则对外可见，因此不能放在抽象类，，其次如果放在子类中，那么回造成冗余，因此最好还是放在接口List中，并且这样如果判断contiains,那么直接判断List.ELEMENT即可，不必自己在定义一个数字-1，List是一个接口，接口是供实现的，因此变量默认是public
- 其次对于变量size,由于我们抽取到abstract类中的代码需要size变量，因此需要将他放在抽象类中，又由于也是公共代码的一部分需要提供给子类使用，因此该变量不能私有，而是protected最好。
清空元素-clear()
实现方法
puvlic void clear(){
head = null;
size = 0;
} next需要设置为null吗;
不需要，因为head设置为null,则第一个元素不再被引用，则第一个元素可以被回收，同样第一个元素回收后，第二个元素不再被引用可以被回收，以此类推链表的内存都会被回收，不需要额外设置null;
添加元素 add(int index, E element)
添加元素考虑两种情况
添加首部情况
如果我们是添加首部，那么应该使得head指向新建的节点，并使得新建节点的指向的下一个节点是head,注意并不是head.next,我这里就是有点短路了，以为是head.next，我还在想怎么不考虑是空链表的情况，确实是傻了
if(index == 0){
head = new Node(element, head);
} 其他部分添加情况
其他部分的添加就比较简单了，只要获取index-1个节点，新节点指向index-1节点的下一个节点，index-1节点再指向新节点即可。
pre.next = new Node(element, pre.next); node方法用于获取index位置的节点
- 由于很多方法需要获取某一个index的节点，但是get返回的E类型的元素，因此就需要写一个私有方法，进行实现。这里我开始把检查索引的方法没有放在里面，在听老师讲了一遍才把他放了进来，也确实是这样。
- 这个循环是比较有意思的，因为不是数组没有序号，所以我们需要根据索引来判断循环多少次得到这个节点。
public Node<E> note(int index){
ensureRangeInternal(index);
Note newHead = head;
for(int i = 0; i < index; i ++){
newHead = newHead.next;
}
return newHead;
} 删除元素 remove(int index)
删除元素也要考虑两种情况
删除首部
删除首部我们就不需要考虑空链表的情况了阴我我们在ensureRangeInternal中可以保证排除空链表的情况，那么排除空链表后，我们只需要将链表首部指向该首部的引用即可。
if(index == 0){
head = head.next;
} 删除其他部分
其他部分的话还是先拿到prev,然后prev.next=prev.next.next即可
Node<E> prev = node(index-1);
prev.next = prev.next.next; 推荐神奇的网站
https://visualgo.net/zh
附上自己写的LinkedList代码
package com.ldy;
import java.awt.HeadlessException;
import java.security.PublicKey;
import java.util.Iterator;
/**
* 链表实现
* @author lidengyin
* 由于父类是抽象类，因此必须是实现父类没有实现的方法
*/
public class LinkedList<E> extends AbstractList<E>{
private Node<E> head;
/**
* 由于只是在Linkist内部使用，因此只需要实现一个内部类即可
* 内部类中不要声明private
* @author l
*
* @param <E>
*/
private static class Node<E>{
E element;
Node<E> next;
public Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
/**
* 返回index位置的元素
*/
@Override
public E get(int index) {
Node<E> node = node(index);
// TODO Auto-generated method stub
return node.element;
}
@Override
public E set(int index, E element) {
//获取节点
Node<E> node = node(index);
//获取旧元素
E oldElement = node.element;
//覆盖旧元素
node.element = element;
// TODO Auto-generated method stub
return oldElement;
}
@Override
public void add(int index, E element) {
// TODO Auto-generated method stub
//确保添加时索引正确
ensureRangeOnAdd(index);
//判断是否为空链表
//添加在首部
if (index == 0) {
head = new Node<E>(element, head);
}else {
//找到索引所在节点
Node<E> prev = node(index-1);
prev.next = new Node<E>(element, prev.next);
//如果是添加在尾部，也是可以满足的。
}
size ++;
}
/**
* 删除index位置对应的元素
*/
@Override
public E remove(int index) {
// TODO Auto-generated method stub
//确保索引正确
ensureRangeInternal(index);
size --;
//获取原有节点；
E oldElement;
//如果是第一个头部
if (index == 0) {
oldElement = head.element;
head = head.next;
}else {
//找到前驱节点
Node<E> prev = node(index-1);
//得到原有节点内容
oldElement= prev.next.element;
//删除原有节点
prev.next = prev.next.next;
}
return oldElement;
}
/**
* 查看元素位置
*/
@Override
public int indexOf(E element) {
// TODO Auto-generated method stub
//如果链表为空，就可以报错了
if (head == null) {
throw new NullPointerException();
}
//自定义链表则element是null是有可能的。
Node<E> newHead = head;
//如果链表为空
if(element == null) {
for(int i = 0; i < size; i ++) {
if (newHead.element == null) {
return i;
}
newHead = newHead.next;
}
}else {
//如果链表不为空
for(int i = 0; i < size; i ++) {
if (newHead.element.equals(element)) {
return i;
}
newHead = newHead.next;
}
}
//返回没有找到
return ELEMENT_NOT_FOUND;
}
/**
* 清除所有元素
*/
@Override
public void clear() {
// TODO Auto-generated method stub
//切断对第一个元素的引用，则第一个元素回收，
//那么第二个元素引用也会消失，则第二个元素回收
//以此类推，全都会回收。
head = null;
size = 0;
}
//===========内部工具类=============//
/**
* 获取该索引处Node
* @param index
* @return
*/
private Node<E> node(int index) {
ensureRangeInternal(index);
Node<E> newHead = head;
for(int i = 0; i< index; i ++) {
newHead = newHead.next;
}
return newHead;
}
@Override
public String toString() {
// TODO Auto-generated method stub
Node<E> newHead = head;
StringBuilder builder = new StringBuilder();
builder.append("size:").append(size).append(",[");
for(int i = 0;i<size; i ++) {
if(i != 0) {
builder.append(",");
}
builder.append(newHead.element);
newHead = newHead.next;
}
builder.append("]");
return builder.toString();
}
} leetcode_237_删除链表中的节点
https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
题目告诉我们无法访问head节点，就是在告诉我们，无法拿到目标节点的前驱节点， 只能通过用后继节点覆盖目标的节点的方式解题。
我们要覆盖一个节点不是说直接改变地址引用，这样是做不出来的，而是将节点中所有的元素实现覆盖。比如
public class ListNode{
int val;
ListNode next;
} 我们就需要用后继节点的val元素覆盖原来的val,同时用后继节点的next覆盖原来的地址引用。即，
public void deleteNode(ListNode node){
node.val = node.next.val;
node.next = node.next.next;
} _206_反转链表_递归
https://leetcode-cn.com/problems/reverse-linked-list/submissions/
根据题目描述，我们先选择用递归的方式解决。
我的思路是，既然整个链表都需要反转，那么每一段长度递减的链表也都需要反转，这就有了递归的理论基础，每一个反转后的小链表加上递增链表的头部作为字迹的尾部即可，这样不断反推就可以得到反转链表。
比如说1，加上递增链表21的头部2作为自己的尾部就是反转链表12，再比如说321，已经反转的12加上头部3作为自己的尾部就是反转链表123.
因此我们首先要做的就是递推到只剩一个节点，这样本身就已经翻转了，然后开始不断加尾部反推。代码如下：
public ListNode reverseList(ListNode head) {
//如果是空链表，或者只有一个节点的链表直接返回
if (head == null || head.next == null) {
return head;
}
//找到链表的尾部，作为新节点的头节点
//这里要知道，head.next才是尾节点，返回的就是尾节点
//也就是新链表的首节点
ListNode newHead = reverseList(head.next);
//设置尾节点
// ListNode oldEnd = head.next;
// ListNode newEnd = oldEnd.next = head;
//如果以后忘了就看上面的注释的两行，这样就可以避免从新的头部开始循环。
head.next.next = head;
//尾节点的后继肯定是null
head.next = null;
//返回新节点的头节点
return newHead;
} 这里还有几个关键点
- 首先当空链表和只有一个节点的链表本身就是反转的，直接返回就行
- 其次，反转链表增加自己的尾部，有两种方式，一种是利用while循环，从首部遍历到尾部；这样多了一个循环耗时；另一种方式是利用head节点，我们反转节点的尾部是oldEnd = head.next,我们需要新增的尾部是head节点，那么使得(head.next).next = head即可完成。减少时间损耗。
- 最后尾部即head，他的后继节点依旧是oldEnd,成了一个环形，因此必须将head的后继设置为null.
_206_反转链表_迭代
https://leetcode-cn.com/problems/reverse-linked-list/submissions/
老师这张图真的是非常形象了，看的很清楚，自己再把思路复述一遍。
迭代的思路也很简单，应该说是拆拆拆，
-
我们需要三个指针， head, second以及newHead
first指向链表头部，second指向head的后继节点，newHead作为新链表的首部。
- 开始的时候先让second指向first的后继节点，然后将head的后继节点指向newHead, newHead一开始为空，second一开始也为空，然后将newHead指向first节点，将first指向second节点
- 以上的文字说明就是不断拆原来的链表，构造新链表的过程，只要head不是null，就可以不断的循环，直到构造完成。
- 这里我开始的时候时second不是空，所以还在循环之外写了一些代码，现在看来是不必要的。
代码如下
/**
* 迭代的思路也很简单
* 应该说我们也还是需要三个指针，head,second,newHead
* first指针指向链表头部，second指针指向链表的第二个节点
* 开始的时候让first的后继节点置空，
* newFirst指向first节点，
* 然后让first指向second节点，second节点指向后继节点
* first节点的后继节点指向newFirst,NewFirst指向First
* 从这里开始就开始重复，直到first节点为空
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
//迭代性能一般都比递归要高，因为一个是O（N）一个是O(N^2)
if(head == null || head.next == null) return head;
ListNode second = null;
ListNode newHead = null;
while(head != null) {
second = head.next;
head.next = newHead;
newHead = head;
head = second;
}
return newHead;
} _141_环形链表
https://leetcode-cn.com/problems/linked-list-cycle/submissions/
环形链表用快慢指针解决，思路还是很简单的
我们将第一个指针指向头部，第二个指针指向头部后继节点，第一个指针一次走一个单位，第二个指针一次走两个单位，如果有环的话，就像是在跑圈，跑得快的和跑的慢的，总会套圈相遇
/**
* 环形链表
* 环形链表用快慢指针解决，思路还是很简单的
* 我们将第一个指针指向头部，第二个指针指向头部后继节点
* 第一个指针一次走一个单位，第二个指针一次走两三个单位，
* 如果有环的化，就像是跑圈，跑得快的和跑的慢的，总会套圈相遇
* @param head
* @return
*/
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) return false;
ListNode first = head;
ListNode second = head.next;
//只要两个指针指向节点的val相同就可以认为是有环
while(second != null && second.next != null) {
// if(second.val == first.val && second.next == first.next) {
// return true;
// }
if(first == second) return true;
first = first.next;
second = second.next.next;
}
return false;
} 快指针走两步，而不是走三步甚至四步的原因
- 可以想象一下，如果快慢指针间隔5步，那么下一轮次慢指针走一步，快指针走两步，双方距离缩短到4，那么继续下一轮双- 方轮次缩短到3，继续2，1直到相遇，也就是说快指针走两步可以保证一定相遇
- 如果快指针走三步，会发生什么呢？假设距离还是5，那么下一轮慢指针走一步，快指针走三步，距离缩短到3，再下一轮缩短到1，在下一轮缩短到-1，也就是说发生了套圈！相遇需要的时间就多了。
- 慢指针走两步，快指针走三步呢？这个效果好像是一样的，但是循环控制条件就要写的更多了。