什么是链表：
1.和数组一样，链表也是一种线性表。
2.从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
3.链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。
- 链表的特点
1.插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。
2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。
示例代码：
public static void main(String[] args) {
//生成链表
Node<Integer> first=new Node<>(1,null);
Node<Integer> second=new Node<>(2,null);
Node<Integer> third=new Node<>(3,null);
Node<Integer> four=new Node<>(4,null);
Node<Integer> five=new Node<>(5,null);
//生成链表
first.next=second;
second.next=third;
third.next=four;
four.next=five;
}1.单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。链表的头结点的数据域不存储数据，指针域指向第一个真正存储数据的结点。
性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。
代码实现：
public class LinkList<T> {
//头结点
private Node head;
//链表长度
private int N;
//初始化头结点
public LinkList(){
head=new Node(null,null);
N=0;
}
//清空链表 只需要将头结点清空即可 即断开后面的指针
public void Clean(){
head.next=null;
head.item=null;
N=0;
}
//获取链表长度
public int getLength(){
return N;
}
//判断链表是否为空
public boolean isEmpty(){
return N==0;
}
/**
* 获取指定位置i处的元素
* 需要先遍历到i处
* @return
*/
public T get(int index){
if (index<0||index>=N){
throw new RuntimeException("位置不符合");
}
Node node=head.next; //head结点的下一个节点才是存储数据的首节点
for (int i = 0; i < index; i++) {
node=node.next;
}
return node.item;
}
/**
* 向链表中添加元素
* 插入最后面
*/
public void insert(T t){
Node n=head;
while (n.next!=null){ //当找到最后一个节点时 其next为null 就会跳出循环 此时n为最后一个节点
n=n.next;
}
Node newNode=new Node(t,null);
n.next=newNode;//添加新节点 到最后一个节点处
N++; //链表长度+1;
}
/**
* 向指定位置i处 添加元素
* 需要移动指定位置的前一节点 和后一节点
*/
public void insert(T t,int index){
Node n=head;
for (int i = 0; i <= index-1; i++) { //指定位置的上一个节点
n=n.next;
}
Node temp=n.next; //先要将 上一节点保存的下一节点临时保存
Node newNode=new Node(t,temp); //创建新节点 并将新节点地址赋值给上一个
n.next=newNode; //将新节点 添加到指定位置
N++; //链表长度增加
}
/**
* 删除指定位置i处元素 并返回删除的元素
* 删除就只需要将指定位置的节点的前一个节点，将其地址指向删除位置的下一个节点即可
*/
public T delete(int index){
if (index<0||index>=N){
throw new RuntimeException("位置不合法");
}
Node n=head;
for (int i = 0; i <= index-1; i++) { //找到i的上一个节点
n=n.next;
}
Node node=n.next; //第i处
Node curr=node.next;//删除位置节点的下一个节点处
n.next=curr; //将i处的上一个节点指向i处的下一个节点
N--;
return node.item; //删除的元素
}
private class Node{
//存储数据
T item;
//下一个结点
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}2.双向链表
双向链表也叫双向表，也是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针为null，指向后继结点的指针域指向的第一个真正存储数据的结点。
性能特点：
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
代码实现：
public class LinkedList<T> implements Iterable<T>{
//头结点
private Node head;
//尾节点
private Node last;
//链表长度
private int N;
public LinkedList() {
last=null;
N=0;
head=new Node(null,null,null);
}
//清空链表
public void clear(){
last=null;
head.next=last;
head.item=null;
head.pre=null;
N=0;
}
//获取链表长度
public int getLength(){
return N;
}
//判断链表是否为空
public boolean isEmpty(){
return N==0;
}
/**
* 插入元素
* 尾插法
*/
public void insert(T t){
if (last==null){ //如果尾节点为空 代表此时链表内无数据
last=new Node(t,head,null); //那么直接将插入元素当做尾部元素
//头尾节点双向绑定
head.next=last;
}else { //如果链表节点不为空
Node oldLast=last;
Node node=new Node(t,oldLast,null);
oldLast.next=node;
last=node;
// Node node1=new Node(t,last,null);
// last.next=node;
// last=node1;
}
N++;
}
/**
* 指定位置插入元素
*/
public void insert(T t,int index){
if (index<0||index>=N){
throw new RuntimeException("索引不合法");
}
Node n=head;
for (int i = 0; i < index; i++) { //找到i位置的前一个结点
n=n.next;
}
Node oldNext=n.next; //i位置原本节点
Node newNode=new Node(t,n,oldNext);//新节点 的前置节点为i位置的前一个节点 后置节点为原本位置的节点
n.next=newNode; //前一节点的后置节点为新节点
oldNext.pre=newNode;//原本位置节点的前节点改为新节点
N++;
}
/**
* 获取指定位置i的元素
*/
public T get(int index){
if (index<0||index>=N){
throw new RuntimeException("索引不合法");
}
Node n=head;
//或者
//Node n=head.next 这样找到的n就是指定位置i处 而不是i-1处
for (int i = 0; i < index; i++) {
n=n.next;
}
Node node=n.next; //指定位置i处
return node.item;
}
/**
* 删除指定i处元素 并且返回
*/
public T remove(int index){
if (index<0||index>=N){
throw new RuntimeException("索引不合法");
}
//先遍历元素
Node n=head;
for (int i = 0; i < index; i++) {
n=n.next; //遍历至i的前一个元素
}
Node removeNode=n.next; //需要删除的i处的 元素
n.next=removeNode.next; //将i-1处的 next指针指向删除的i处的 next结点
Node newLastNode=removeNode.next; //i+1处元素
newLastNode.pre=n; //将i+1处的前指针 指向i-1处元素结点
N--;
return removeNode.item;
}
@Override
public Iterator<T> iterator() {
return new TIterator();
}
private class TIterator implements Iterator{
private Node n=head;
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next() {
n=n.next;
return n.item;
}
}
private class Node{
//数据域
public T item;
//上一节点
public Node pre;
//下一节点
public Node next;
public Node(T item, Node pre, Node next) {
this.item = item;
this.pre = pre;
this.next = next;
}
}
}链表复杂度分析：
get(int i):每一次查询，都需要从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多，时间复杂度为O(n)
insert（int i,T t）:每一次插入，需要先找到i位置的前一个元素，然后完成插入操作，随着数据元素N的增多，查找的元素越多，时间复杂度为O(n)；
remove同理;
相比顺序表，链表插入和删除的时间复杂度虽然一样，但任然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，同时没有涉及到元素的交换。
但链表的查询操作性能会比较低，所以查询操作多建议顺序表，增删操作比较多建议用链表。
链表反转：
链表反转是面试中比较高频的一个考点。
原链表：1->2->3->4
反转后：4->3->2->1
思路：使用递归可以完成反转，从链表的第一个数据结点开始，依次递归调用反转每一个结点，直到最后一个结点反转完毕，整个链表反转完毕。
代码：
/**
* 链表反转
* 递归
*/
public void reserve(){
if (N==0){
return; //如果链表为空 则返回
}
reserve(head.next);
}
//1---》2---》3----》4
//假设此时递归到第3节点
public Node reserve(Node node){
if (node.next==null){ //表示此时已经递归至最后一个元素
head.next=node; //将head结点 指向最后一个结点
return node; //然后将该节点返回
}
Node reserveNode = reserve(node.next); //如果不是最后一个结点 则继续递归下一个节点 并返回该节点
reserveNode.next=node; //将该节点的下一节点 指向该节点的上一节点 实现反转
node.next=null; //然后上一节点的next改为null
return node;
}流程讲解：
首先从第一个节点开始遍历，发现还有后续节点，然后递归至最后一个节点。
那么此时执行至
当结点4反转完毕后，返回结点4，此时对结点3进行反转。
同理：
运行时栈内存示意图：
快慢指针：
快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。比如可以利用快慢指针来找到中间值问题。
快指针每次移动2步，慢指针每次移动一步，当快指针移动到尾部时，此时慢指针所在位置即为中间值。
代码：
/**
* 获取中间值 --快慢指针
* 快指针：一次走2步
* 慢指针：一次走1步
* 那么当快指针走到最后一个元素时，此时慢指针所在位置即是中间值。
*/
public String getMid(){
Node first=head.next; //快指针先指向第一个数据结点
Node slow=head.next; //慢指针也同样先指向第一个数据结点
//奇偶判断优化版本
while (first.next!=null){
if (first.next.next==null){ //此时 表示是偶数 并且已经是走到最后一步
Node nextSlow=slow.next; //此时slow为左中间值 slow.next为右中间值
String mid=String.valueOf(slow.item)+String.valueOf(nextSlow.item);
return mid+"/2"; //左中间值+右中间值 / 2
}
first=first.next.next;//快指针一次性移动两步
slow=slow.next; //慢指针一次性移动1步
}
return String.valueOf(slow.item);
}单链表环问题：
如果链表有环，那么可以利用快慢指针来解决，快指针迟早会追上慢指针从而判断是否有环（可以看做一个圆形跑道，快的迟早会追上慢的）
代码：
public static void main(String[] args) {
//生成链表
Node<Integer> first=new Node<>(1,null);
Node<Integer> second=new Node<>(2,null);
Node<Integer> third=new Node<>(3,null);
Node<Integer> four=new Node<>(4,null);
Node<Integer> five=new Node<>(5,null);
Node<Integer> six=new Node<>(6,null);
//生成链表
first.next=second;
second.next=third;
third.next=four;
four.next=five;
five.next=six;
/**
* 快慢指针————检查链表是否有环问题
* 思路：如果链表有环，那么快指针迟早会追上慢指针（比作圆形跑道一快一慢）
*/
six.next=second; //成环
boolean circle = isCircle(first);
System.out.println("是否有环："+circle);
//判断链表是否有环
public static boolean isCircle(Node<Integer> node){
Node<Integer> fast=node; //快指针
Node<Integer> slow=node; //慢指针
while (fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if (fast.equals(slow)){
return true; //如果有环 则返回true
}
}
return false; //没有环 则返回false
}有环链表入口问题：
当快慢指针相遇时，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样 为1，则慢指针与“新”指针相遇的地方就是环的入口。
代码实现：
/**
* 有环链表入口问题
* @param node
* @return
*/
public static Integer getCircleEntry(Node<Integer> node){
Node<Integer> fast=node; //快指针
Node<Integer> slow=node; //慢指针
while (fast.next!=null&&fast.next.next!=null){
fast=fast.next.next;
slow=slow.next;
if (fast.equals(slow)){ //如果相等 则表示发现环
Node<Integer> temp=node; //定义一个临时标记 从头结点开始
while (temp!=null&&temp.next!=null){ //此时temp节点和 slow节点每次都移1步
temp=temp.next;
slow=slow.next;
if (temp.equals(slow)){ //当临时节点和slow节点相遇时 那么此时就是入口节点
return temp.item;
}
}
}
}
return 0; //无环则返回0
}3.循环链表
循环链表，顾名思义，链表整体要形成一个圆环状。那么只需要将单向链表的最后一个指针指向头结点即可。
适用于存储有循环特点的数据，比如约瑟夫问题。
约瑟夫问题：
思路：
1.构建含有41个单节点的单向循环链表，分别存储1-41的值，分别代表这41个人。
2.使用计数器count，记录当前报数的值；
3.遍历链表，每循环一次，count++;
4.如果判断count是3，则从链表中删除这个结点并打印值，然后将count重置为0；
public static void main(String[] args) {
Node<Integer> first=null;
Node<Integer> pre=null ;//上一个节点
for (int i = 1; i <=41; i++) {
if (i==1){
first=new Node<>(i,null); //第一个节点 初始化 然后进行下一次循环
pre=first;
continue;
}
Node<Integer> node=new Node<>(i,null);
pre.next=node;
pre=node;
if (i==41){
//最后节点 指向头结点
node.next=first;
}
}
//到此元素初始化完毕
int count=0; //使用count计数当前报数
Node<Integer> n=null;
Node<Integer> before=null; //记录前一个节点 删除元素时的临时节点
n=first;
while (n!=n.next){
count++;
if (count==3){ //当计数为3时 删除当前节点
before.next=n.next;//删除元素 使被删除元素的上一个节点指向被删除的元素的下一个节点即可
System.out.println("删除元素为："+n.t);
n=n.next; //从下一个元素 重新从1计数
count=0;
}else {
before=n; //记录上一个节点 方便删除
n=n.next;
}
}
//最后剩下的
System.out.println("最后活下来的："+n.t);
}
private static class Node<T> {
public T t; //元素
public Node next; //下一个元素
public Node(T t, Node next) {
this.t = t;
this.next = next;
}
}
}