实际：位于链表头部的节点 ； 自己定义（也可以不定义该变量）：链表头部的节点自定义为head（first）； 官方定义：若只有指针为头节点 否则为普通节点 ；
实际：位于链表尾部的节点 ； 自己定义（也可以不定义该变量）：链表尾部的节点自定义为tail（last） ； 官方定义：若只有指针为尾节点 否则为普通节点 ；
1：单向链表
先进行无头节点的单向链表的练习 熟悉一个单向链表的写法
核心要点：
1：链表采用一直递归的方式 进行节点与节点的连接
2：新节点初始化时 其next的指向都是不确定的 需要其他节点赋予
3：每一个节点存放本节点的数据 data 的时候，同时存放一个next ；
next的本质是什么，是一个变量名，也就是一个指针：指向的是下一个NodeSingly类型的节点；
位置位于链表的头部（自定义为head（first）），如果有数据为普通节点（称为位于头部的节点） 如果只有指针为头节点
位置位于链表的尾部（自定义为tail（last））， 如果有数据为普通节点（称为位于尾部的节点） 如果只有指针为尾节点
有头结点表示第一个结点不保存数据，与其他数据节点区别开来
无头结点表示第一个节点保存数据，与其他节点除了位置不同，其余一模一样
链表绝大情况下都不会定义头节点
在单向链表没有定义头节点的时候
所谓的head（first） 实际也是普通节点只不过他存放在开头而已（注意他的next可能为空）
2：节点
public class NodeSingly {
public int data;
public NodeSingly next ;
public NodeSingly(int data, NodeSingly next) {
this.data = data;
this.next = next;
}
}
3：无头节点的单向链表代码
public class SinglyLinkedList {
//初始化 无头节点（头节点为空）
private NodeSingly head = null;
//表头部插入
public void insertAsHead(int value) {
NodeSingly newNodeSingly = new NodeSingly(value, null);
insertToHead(newNodeSingly);
}
//表头部插入头节点
private void insertToHead(NodeSingly newNodeSingly) {
if (head == null) {
head = newNodeSingly;
} else {
newNodeSingly.next = head;
head = newNodeSingly;
}
}
//在某节点上前 插入新节点
public void insertBefore(NodeSingly originalNodeSingly, int value) {
NodeSingly newNodeSingly = new NodeSingly(value, null);
insertBefore(originalNodeSingly, newNodeSingly);
}
private void insertBefore(NodeSingly originalNodeSingly, NodeSingly newNodeSingly) {
if (originalNodeSingly == null) {
return;
}
//判断原有节点是否为头节点
if (head == originalNodeSingly) {
insertToHead(newNodeSingly);
return;
}
//以头节点开始 使用next进行遍历 一直到获取到
// 遍历节点 的下一个节点为需要查找的某节点为止
NodeSingly indexNodeSingly = head;
while (indexNodeSingly != null && indexNodeSingly.next != originalNodeSingly) {
indexNodeSingly = indexNodeSingly.next;
}
if (indexNodeSingly == null) {
return;
}
//最后顺序 遍历节点 新节点 某节点
//实现了 新节点插入到原节点之前的功能
newNodeSingly.next = originalNodeSingly;
indexNodeSingly.next = newNodeSingly;
}
//顺序插入
//链表尾部插入
public void insertTail(int value) {
NodeSingly newNodeSingly = new NodeSingly(value, null);
//空链表，可以插入新节点作为head，也可以不操作
if (head == null) {
head = newNodeSingly;
} else {
NodeSingly indexNodeSingly = head;
while (indexNodeSingly.next != null) {
indexNodeSingly = indexNodeSingly.next;
}
//获取到indexNode为最后一个节点
//遍历节点 新节点(尾节点) 空
indexNodeSingly.next = newNodeSingly;
}
}
public void deleteByNode(NodeSingly originalNodeSingly) {
if (originalNodeSingly == null || head == null) {
return;
}
if (originalNodeSingly == head) {
head = head.next;
return;
}
NodeSingly indexNodeSingly = head;
//以头节点开始 使用next进行遍历 一直获取到
// 遍历节点 的下一个节点为原节点为止
while (indexNodeSingly != null && indexNodeSingly.next != originalNodeSingly) {
indexNodeSingly = indexNodeSingly.next;
}
if (indexNodeSingly == null) {
return;
}
//获取到 遍历节点 某节点
//最后 遍历节点 直接指向 遍历节点的下个节点（原节点）的下一个节点
//实现了 被删除的某节点就会被跳过
indexNodeSingly.next = indexNodeSingly.next.next;
}
//根据value删除节点
public void deleteByValue(int value){
NodeSingly indexNodeSingly = head;
//外部接口调用 第一次为从 头节点进行遍历
deleteByValueRepetition(value, indexNodeSingly);
}
//通过递归 根据value 删除所有拥有该value的节点
public void deleteByValueRepetition(int value, NodeSingly indexNodeSingly) {
if (head == null) {
return;
}
NodeSingly beforeIndexNodeSingly = null;
// 以头节点开始 使用next进行遍历 一直到获取到为止
// 遍历节点 的 data 为所需要查找的data为止
// 该遍历节点是需要删除的 因此还需要查找出前一个节点
while (indexNodeSingly != null && indexNodeSingly.data != value) {
beforeIndexNodeSingly = indexNodeSingly;
indexNodeSingly = indexNodeSingly.next;
}
if (indexNodeSingly == null) {
return;
}
//查找到data的节点为 头节点
if (beforeIndexNodeSingly == null) {
head = head.next;
} else {
beforeIndexNodeSingly.next = beforeIndexNodeSingly.next.next;
}
//对于向媒体的value 可以进行递归删除
deleteByValueRepetition(value, beforeIndexNodeSingly);
}
//查找节点的data
public NodeSingly findByValue(int value) {
NodeSingly indexNodeSingly = head;
while (indexNodeSingly != null && indexNodeSingly.data != value) {
indexNodeSingly = indexNodeSingly.next;
}
return indexNodeSingly;
}
//打印所有数据
public void findAll() {
NodeSingly p = head;
while (p != null) {
System.out.print(p.data + " ");
p = p.next;
}
System.out.println();
}
}
4：测试代码
private static void SinglyLinkedListTest() {
SinglyLinkedList singlyLinkedList = new SinglyLinkedList();
singlyLinkedList.insertAsHead(1);
singlyLinkedList.insertAsHead(5);
singlyLinkedList.insertAsHead(7);
singlyLinkedList.insertAsHead(9);
singlyLinkedList.insertTail(10);
singlyLinkedList.findAll();
System.out.println("==============================================");
NodeSingly nodeSinglyTemp = singlyLinkedList.findByValue(5);
singlyLinkedList.insertBefore(nodeSinglyTemp,2);
singlyLinkedList.insertBefore(nodeSinglyTemp,3);
singlyLinkedList.insertBefore(nodeSinglyTemp,4);
singlyLinkedList.insertBefore(nodeSinglyTemp,4);
singlyLinkedList.insertBefore(nodeSinglyTemp,4);
singlyLinkedList.insertBefore(nodeSinglyTemp,4);
singlyLinkedList.findAll();
System.out.println("==============================================");
singlyLinkedList.deleteByNode(nodeSinglyTemp);
singlyLinkedList.findAll();
System.out.println("==============================================");
singlyLinkedList.deleteByValue(4);
singlyLinkedList.findAll();
System.out.println("==============================================");
NodeSingly nodeSinglyTemp9 = singlyLinkedList.findByValue(9);
singlyLinkedList.deleteByNode(nodeSinglyTemp9);
NodeSingly nodeSinglyTemp7 = singlyLinkedList.findByValue(7);
singlyLinkedList.deleteByNode(nodeSinglyTemp7);
singlyLinkedList.findAll();
System.out.println("==============================================");
}
项目连接
请配合项目代码食用效果更佳：
项目地址：
https://github.com/hesuijin/hesuijin-algo
Git下载地址：
https://github.com.cnpmjs.org/hesuijin/hesuijin-algo.git
linkedCollection包
网友评论