链表概念：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
单向链表：
-
概念：
链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构
-
存储方式：
- 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）
- 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）
下图描述了单向链表存储情况。存储是分散的，每一个节点只要记录下一节点，就把所有数据串了起来，形成了一个单向链表。
节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。下面图是具体的说明：
-
头节点，头指针和首元节点:
- 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
- 节点：链表中的节点又细分为头节点、首元节点和其他节点：
- 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
- 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
- 其他节点：链表中其他的节点；
因此，一个存储 {1,2,3} 的完整链表结构如图所示：
注意：链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。
单向链表的实现：
链表中节点
package linkedList;
/**
* @ClassName: Node
* @Description: 链表中节点，相当于火车的车厢
* @author pms
* @date 2021年4月16日
*
*/
public class Node {
/**
* 数据域
*/
protected long data;
/**
* 指针域
*/
protected Node next;
/**
* 构造其初始化参数
* 创建一个新的实例 Node
*
* @param value
*/
public Node(long value){
this.data = value;
}
/**
*
* @Title: display
* @Description: 显示方法
* @param 参数
* @return void 返回类型
* @throws
*/
public void display(){
System.out.println(data + " ");
}
}
单向链表
/**
* @ClassName: LinkedList
* @Description: 单向链表，相当于火车，定义里面之定义了头节点，就是因为可以通过指针域找到火车的车厢，即其他节点
* @author pms
* @date 2021年4月16日
*
*/
public class LinkedList {
/**
* 链表头节点
*/
private Node first;
/**
* 初始化链表，不初始化也可以，因为编译器默认会给没初始化的属性赋值
* 创建一个新的实例 LinkedList
*
*/
public LinkedList(){
first = null;
}
/**
*
* @Title: empty
* @Description: 判断单链表是否为空
* @param @param value 新节点的值
* @return void 返回类型
* @throws
*/
public boolean empty(){
return first.next == null;
}
/**
*
* @Title: insertFirst
* @Description: 在头节点后面插入新节点
* @param @param value 新节点的值
* @return void 返回类型
* @throws
*/
public void insertFirst(long value){
//构建新节点
Node temp = new Node(value);
//插入逻辑，next这个属性是protected类型，只能子类或者同包下可以引用
temp.next = first;
first = temp;
}
/**
*
* @Title: addNode
* @Description: 添加节点到链表尾部
* @param @param value 参数
* @return void 返回类型
* @throws
*/
public void addNode(long value){
//实例化一个节点
Node newNode = new Node(value);
//判断链表的头节点，如果为空，直接将新增的放到头节点
if(first == null){
first = newNode;
return;
}
Node temp = first;
//找到链表的末尾
while(temp.next != null){
temp = temp.next;
}
//找到末尾，添加新节点
temp.next = newNode;
}
/**
*
* @Title: deleteNode
* @Description: 删除第index个节点
* @param @param index
* @param @return 参数
* @return boolean 返回类型
* @throws
*/
public boolean deleteNode(int index){
//参数不合理，直接返回false
if(index < 0 || index > length() - 1){
return false;
}
//删除头节点
if(index == 0){
first = first.next;
return true;
}
int i = 0;
Node preNode = first;
Node curNode = preNode.next;
while(curNode != null){
if(i == index){
preNode.next = curNode.next;
return true;
}
preNode = curNode;
curNode = curNode.next;
i++;
}
return false;
}
/**
*
* @Title: delete
* @Description: 删除指定节点
* @param @param n
* @param @return 参数
* @return boolean 返回类型
* @throws
*/
public boolean delete(Node n){
//判断节点是否为空，或者是头节点，是则返回false
if(n == null || n.next == null){
return false;
}
long temp = n.data;
n.data = n.next.data;
n.next.data = temp;
n.next = n.next.next;
return true;
}
/**
*
* @Title: length
* @Description: 返回链表的长度
* @param @return 参数
* @return int 返回类型
* @throws
*/
public int length(){
int length = 0;
Node temp = first;
while(temp != null){
length ++;
temp = temp.next;
}
return length;
}
/**
*
* @Title: printLinkedList
* @Description: 输出该链表的各个节点
* @param 参数
* @return void 返回类型
* @throws
*/
public void printLinkedList(){
Node temp = first;
while(temp != null){
System.out.print(temp.data + ", ");
temp = temp.next;
}
}
}