admin
Java之线性表的链式存储——单链表
线性表的存储结构分为顺序存储结构和链存储结构两种类型。线性表的分类可以参考下图来学习内存。
今天我们主要来学习一下链式存储结构。一、链式存储介绍
"链式存储结构，地址可以连续也可以不连续的存储单元存储数据元素"——来自定义。
其实，你可以想象这样一个场景，你想找一个人（他的名字叫小谭）,于是你首先去问 A ， A 说他不知道，但是他说 B 可能知道，并告诉了你 B 在哪里，于是你找到 B ，B 说他不知道，但是他说 C 可能知道，并告诉了你 C 的地址，于是你去找到 C ，C 真的知道小谭在何处。
上面场景其实可以帮助我们去理解链表，其实每一个链表都包含多个节点，节点又包含两个部分，一个是数据域（储存节点含有的信息），一个是指针域（储存下一个节点或者上一个节点的地址），而这个指针域就相当于你去问B，B知道C的地址，这个指针域就是存放的 C 的地址。
链表下面其实又细分了3种：单链表、双向链表和循环链表。今天我们先讲单链表。
二、单链表介绍
什么是单链表呢？单链表就是每一个节点只有一个指针域的链表。如下图所示，就是一个带头节点的单链表。下面我们需要知道什么是头指针，头节点和首元节点。
头指针：指向链表节点的第一个节点的指针
头节点：指在链表的首元节点之前附设的一个节点
首元节点：指在链表中存储第一个实际数据元素的节点（比如上图的 a1 节点）
三、单链表的创建
单链表的创建有两种方式，分别是头插法和尾插法。
1、头插法
头插法，顾名思义就是把新元素插入到头部的位置，每次新加的元素都作为链表的第一个节点。那么头插入法在Java中怎么实现呢。首先我们需要定义一个节点，如下
public class Listnode {
public int val; //数据域
public ListNode next;//指针域
}
然后我们就创建一个头指针（不带头节点）
//元素个数
int n = 5;
//创建一个头指针
ListNode headNode = new ListNode();
//头插入法
headNode= createHead(headNode, n);
然后创建一个私有方法去实现头插法，这里我们插入5个新元素，头插入的核心是要先断开首元节点和头指针的连接，也就是需要先将原来首元节点的地址存放到新节点的指针域里，也就是 newNode.next = ，然后再让头指针指向新的节点 = newNode，这两步是头插入的核心，一定要理解。
/**
* 头插法
* 新的节点放在头节点的后面，之前的就放在新节点的后面
* @param headNode 头指针
* @return
*/
private static ListNode createHead(ListNode headNode, int n) {
//插入5个新节点
for (int i = 1; i <= n; i++) {
ListNode newNode = new ListNode();
newNode.val = i;
//将之前的所有节点指向新的节点（也就是新节点指向之前的所有节点）
newNode.next = ;
//将头指针指向新的节点
= newNode;
}
return headNode;
}
最后我把链表打印输出一下（其实也是单链表的遍历），判断条件就是只有当指针域为空的时候才是最后一个节点。
private static void printLinkedList(ListNode headNode) {
int countNode = 0;
while ( != null){
countNode++;
Sy(.val);
headNode = ;
}
Sy("该单链表的节点总数：" +countNode);
}
最后的输出结果显然是逆序，因为没一个新的元素都是从头部插入的，自然第一个就是最后一个，最后一个就是第一个：
2、尾插法
尾插法，顾名思义就是把新元素插入到尾部的位置（也就是最后一个位置），每次新加的元素都作为链表的第最后节点。那么尾插法在 Java 中怎么实现呢，这里还是采用不带头节点的实现方式，头节点和头指针和头插入的实现方式一样，这里我就直接将如何实现：
/**
* 尾插法
* 找到链表的末尾结点，把新添加的数据作为末尾结点的后续结点
* @param headNode
*/
private static ListNode createByTail(ListNode headNode, int n) {
//让尾指针也指向头指针
ListNode tailNode = headNode;
for (int i = 1; i <= n; i++) {
ListNode newNode = new ListNode();
newNode.val = i;
newNode.next = null;
//插入到链表尾部
= newNode;
//指向新的尾节点，tailer永远存储最后一个节点的地址
tailNode = newNode;
}
return headNode;
}
和头插入不同的是，我们需要声明一个尾指针来辅助我们实现，最开始，尾指针指向头指针，每插入一个元素，尾指针就后移一下，这里我们来讲一下原理：每次往末尾新加一个节点，我们就需要把原来的连接断开，那怎么断开呢，我们首先需要让尾指针指向新的节点，也就是 = newNode; 然后再让尾指针后移一个位置，让尾指针指向最后一个节点。也就是尾指针始终指向最后一个节点，最后将头指针返回，输出最后结果：
四、单链表的删除
既然单链表创建好了，怎么在链表里面删除元素呢，单链表的删除，我分为了两种情况删除，分别是删除第i个节点和删除指定元素的节点。
1、删除第i个节点
我们可以先来理一下思路：在单链表里，节点与节点之间都是通过指针域链接起来的，所以如果我们想实现删除的操作，实际上是需要我们去改变相应指针域对应得地址的。当想去删除第i个元素的时候，比如要删除上图的第3个元素（也就是3），实际上我们要做的就是要让2号元素指向4号元素（其实就是需要修改2号元素的指针域，让2号元素的指针域存储4号元素）。那么怎么做才能实现这一步呢？很显然，要实现这个步骤，我们必须要找到4号元素和2号元素，但是再仔细想一下，其实我们只需要找到2号元素就可以了，因为4号元素的地址存储再2号的下一个元素的指针域里面。
所以综上所述分析我们可以得出删除的两个核心步骤：
1.删除第i个节点，需要先找到第 i-1 个个节点，也就是第i个节点的前一个节点；
2.然后让第 i-1 个节点指向第 i-1 个节点的下下个节点
下面的代码具体实现了怎么删除第i个元素。
/**
* 删除第i个节点
* 1,2 4,4,5
* 删除之后应该是1,2,4,5
* @param headNode
* @param index
* @return
*/
public static ListNode deleteNodeByIndex(ListNode headNode, int index) {
int count = 1;
//将引用给它
ListNode preNode = headNode;
//看计数器是不是到了i-1，如果到了i-1,就找到了第i-1个节点
while != null && count <= index -1){
//寻找要删除的当前节点的前一个节点
count++;
preNode = ;
}
if (preNode != null){
= .next;
}
return headNode;
}
2、删除指定元素的那个节点
删除指定元素节点的实现方法有两种，第一种就是先找到指定元素对应的链表的位置（ index ），然后再按照删除第 i 个节点的思路删除即可。实现方法如下图所示：
/**
* 删除链表指定数值的节点
* @param headNode
* @param val
* @return
*/
private static ListNode deleteNodeByNum(ListNode headNode, int val) {
ListNode deleteOne = headNode;
int countByDeleteOne = 1;
while != null){
if .val == val){
deleteOne = dele;
break;
}
countByDeleteOne ++;
deleteOne = dele;
}
return deleteNodeByIndex(headNode, countByDeleteOne);
}
第二种方法的实现就很精妙（前提是此节点不是尾节点）
public void deleteNode(ListNode node) {
//删除node即通过将后面的值赋给node，然后更改node的指针指向下下一个结点即可
node.val = node.next.val;
node.next = node.next.next;
}
五、单链表的查询（及修改）
单链表的查询实现很简单，就是遍历当前单链表，然后用一个计数器累加到当前下标，那么当前的这个节点就是要查询的那个节点，然后再返回即可，当然需要判断传过来的这个下标是否合法。当然如果需要修改，就需要把当前找到的节点的数据域重新赋上需要修改的值即可，这里就不上代码了。具体实现如下：
private static ListNode searchLinkedList(ListNode headNode, int index) {
//如果下标是不合法的下标就表示找不到
if (index < 1 || index > getLinkedListLength(headNode)){
return null;
}
for (int i = 0; i < index; i++) {
headNode = ;
}
return headNode;
}
获取单链表的长度（注意我这里定义的 headNode 是头指针不是头节点）
/**
* 求单链表长度
* @param headNode
* @return
*/
private static int getLinkedListLength(ListNode headNode) {
int countNode = 0;
while ( != null){
countNode++;
headNode = ;
}
return countNode;
}
六、小结
单链表的相关操作就讲解完了，其实通过上面对单链表的相关操作，我们不难发现，单链表的删除和插入其实很方便，只需要改变指针的指向就可以完成，但是查找元素的时候就比较麻烦，因为在查找的时候，需要把整个链表从头到尾遍历一次。