链表的结构及概念:
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
单向、双向
带头、不带头
循环、非循环
虽然有这么多的链表的结构，但是我们重点掌握两种:
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如 哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表
链表是由一个一个 节点构成的 ，每一个节点有两个域一个叫做数值域，一个叫做next域
data：数值域 里面存储的是数据
next：引用变量 - 存下一个节点的地址
从上图发现当前节点的next域存放的都是下一个节点的地址
那么最后那个没有存放下一个的地址叫做什么呢？
其实这个叫做尾巴节点：当这个next节点域为null的时候
有尾巴节点还会有头节点：整个链表当中的第一个节点叫做头节点
我们刚刚写的下面这个就是 不带头非循环的单链表
区分带头不带头，我给你画个图就知道了：
红色的那个就是头节点：它里面可以存放一个无效的data。
带头：其实就是标识当前链表的头
如果不带头：这个链表的头节点，在随时发生改变，
如果带头：这个链表的头节点不会发生改变。
什么是循环的：最后一个节点的next域引用 第一个节点的地址 ，必须是第一个，不可以是第二个，不然不叫循环了
单链表的实现:
我们把整链表抽象为一个类：
把节点抽象为一个类：这个类里面包含data 字段 和next字段
先抽象出来节点类：
/
节点类
/
public class Node {
public final int data; // 数据域
public Node next; // 引用域
public Node(int data) {
this.data = data;
this.next = null; // 引用类型，默认null
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
为什么要给data搞个构造方法，因为如果不设置，那么我们不知道节点的next域要存什么地址，为什么不给next赋值呢？ 因为next 是一个引用类型，默认是null，这就是我们的节点类 。
而且当我们实例化对象也发方便：
Node node = new Node（5）;
在抽象出来整个链表的类：
对于链表，我们还需要一个属性 head，这东西是一个引用，指向当前链表的头，因为当前是不带头的，头一直发生改变，要一个来一直标识单链表的头结点
/
链表类
/
public class MyLinkedList {
// 标识 单链表的头结点
public Node head;
}
例如，我们创建一个链表:
public void creatList() {
Node node1 = new Node(13);
Node node2 = new Node(2);
Node node3 = new Node(5);
node1.next = node2;
node2.next = node3;
head = node1;
}
我们知道链表是 当前节点后面跟着一个节点
node1.next = node2;
可以看见node2的地址是0x456 ，所以为了成为链表node1的next要被node2赋值，这样才是一个链表。
node2.next = node3; 原理也是一样，只不过是我们的node3 没有引用，因为它是最后一个节点，后面没有下一个节点了，而且它是引用类型默认就是null了，所以不需要写node3的代码。
this.head = node1;
目前的头是node1 ，使用head指向node1所指的对象，13就是head
链表类的全部代码:
/
链表类
/
public class MyLinkedList {
// 标识 单链表的头结点
public Node head;
// 穷举的方式创建链表,
public void createList() {
Node node1 = new Node(13);
Node node2 = new Node(2);
Node node3 = new Node(5);
node1.next = node2;
node2.next = node3;
head = node1;
}
}
常见面试题:
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
输入：【 1 , 2 , 3 , 4 】
输出：【 4 , 3 , 2 , 1 】
分析：该链表是单链表，反转后的链表的每个结点都指向前一个结点，即第一个指向空，最后一个指向倒数第二个。
整个过程大致可以概括为：断开当前结点指向 ，让该结点指向前一个结点，以此类推到最后一个节点。
先看看Node节点吧
package link.list;
/
节点类
/
public class Node {
public final int data; // 数据域
public Node next; // 引用域
public Node(int data) {
this.data = data;
this.next = null; // 引用类型，默认null
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
这里使用 迭代, 栈, 循环 三种方式分别实现了一遍
package link.list;
import java.util.Stack;
public class LinkListTest {
public static Node head; //标识单链表的头结点
public static void main(String【】 //代码效果参考：http://www.jhylw.com.cn/303424589.html
args) {System.out.printf("创建链表");
creatList();
// 链表创建后, 打印链表
printLinkList(head);
System.out.printf("开始反转链表");
// 反转后打印链表
// 通过迭代的方式实现
// Node reverserNode = reverserLinkedList(head);
// 通过栈的方式实现
// Node reverserNode = reverserLinkByStack(head);
// 通过循环的方式实现
Node reverserNode = reverserLinkByLink(head);
printLinkList(reverserNode);
}
public static void creatList() {
Node node1 = new Node(13);
Node node2 = new Node(2);
Node node3 = new Node(5);
//代码效果参考：http://www.jhylw.com.cn/015322359.html
node1.next = node2;node2.next = node3;
head = node1;
}
// 打印链表
public static void printLinkList(Node node) {
System.out.println("开始打印head");
while (node != null) {
System.out.println(node.data + "");
node = node.next;
}
}
/*
递归反转链表
这个递归,返回值只是为了控制返回的是最后一个节点
然后通过递归, 通过栈的特性, 这里就是让它可以从最后一个节点开始把自己的子节点的子节点改成自己
自己子节点改成null
@param node
@return
/
public static Node reverserLinkedList(Node node) {
if (node == null || node.getNext() == null) {
return node;
}
Node nextNode = reverserLinkedList(node.getNext());
node.getNext().setNext(node);
node.setNext(null);
return nextNode;
}
// 使用栈的方式, 把递归变成循环
public static Node reverserLinkByStack(Node node) {
Stack nodeStack = new Stack();
Node head = null;
// 存入栈中, 模拟递归开始的栈状态
while (node!=null) {
nodeStack.push(node);
node = node.getNext();
}
/
特殊处理第一个栈顶元素(也就是反转前的最后一个元素, 因为它位于最后, 不需要反转,
如果它参参与下面的while, 因为它的下一个节点为空, 如果getNode(), 会引发空指针)
/
if (!nodeStack.isEmpty()) {
head = nodeStack.pop();
}
// 排除以后就可以快乐的循环了
while(!nodeStack.isEmpty()) {
Node tempNode = nodeStack.pop();
tempNode.getNext().setNext(tempNode);
tempNode.setNext(null);
}
return head;
}
// 第三种方式反转链表
public static Node reverserLinkByLink(Node node) {
// 指向空, 可以想象成位于第一个节点之前
Node newNode = null;
// 指向第一个节点
Node curNode = node;
// 循环中, 使用第三变量事先保存curNode的后面一个节点
while (curNode != null) {
Node tempNode = curNode.getNext();
// 把curNode反向往前指
curNode.setNext(newNode);
newNode = curNode;
curNode = tempNode;
}
return newNode;
}
}
