每博一文案
马德写过一段话 ,我慢慢明白了为什么我不快乐,因为我总是期待一个结果,
看一本书,期待它会让我变得深刻,跑一会儿步,期待它让我瘦下来,
发一条微信,期待他回复.对别人好,期待被回代以好,这些预设的期待,如果实现了,
我长舒一口气,如果没有实现呢,就自怨自艾.
我们这一生漫长而孤独.
身边的人走走停停,匆匆忙忙
我们终究要一个人面对,别觉得谁会一直在意你,别期待谁会英雄登场,拯救我们水深火热之中,
陪我们到最后的只有自己.
________________ 一禅心灵庙语
文章目录
- 双向不带头链表 —— Java（附有源码）
- 每博一文案
- 双向不带头链表
- 双向不带头链表的实现
- 双向不带头链表的类的定义
- 头插法
- 打印链表
- 尾插法
- 数值 key 是否存在与该链表当中
- 计算该双向链表中存在多少个数值
- 在序号为 index 的位置插入数值节点
- 删除 n个 第一个数值为 key 的节点
- 删除全部 key 数值的节点,没有计数，全部删除
- 清空链表
- 完整的双向链表的实现 代码
- MyLinkedList.java
- TestDemo.java
- 最后:
双向不带头链表
- 关于链表的一些理论知识就不多介绍了，大家可以参考 双向循环带头节点链表 —— C语言_
- 还有这里 单链表的实现 —— Java_
- 双向不带头链表的图示
双向不带头链表的实现 双向不带头链表的类的定义
- 这里我们通过 构造方法 为后面创建节点,做好准备
class Node { // 创建双向不循环的链表的类
public int data; // 存放的数值
public Node prev; // 前驱节点
public Node next; // 后继节点
public Node(int data) { // 构造方法，赋值数值，创建节点
this.data = data;
this.next = null;
this.prev = null;
}
}
头插法
- 对于 头插法 我们需要 注意 的是其存在这 两种情况:
- 该链表中只有一个节点 (首节点) 的存在,我们可以直接赋值
- 该链表存在 多个节点
public class MyLinkedList {
private Node head = null; // 标记双向链表的头节点
private Node tail = null; // 标记双向链表的尾节点
public void addFirst(int data) {
Node node = new Node(data); // 通过双向链表的构造方法，创建节点
Node cur = this.head; // 拷贝头节点，代替移动
if(null == this.head) {
// 只有一个节点
this.head = node; // 头尾都是自身
this.tail = node;
} else { // 注意 else 不可以省略，非要省略的话，需要在 head == null 的时候，return 停止程序继续向下执行
cur.prev = node;
node.next = head;
head = node;
}
}
}
打印链表
- 我们通过循环遍历的方式打印链表的存在
- 注意 链表结束循环的 条件 是 (head != null) ,不是 (head.next !=null) ,因为 就算 (head.next == null) 了,其该位置存在着数值,这个数值你总不可以不要吧,而 (head == null) 没有存放数值,都 空 了,还怎么存呀 ,所以这点需要注意
- 还有就是 我们在移动节点的时候,定义(拷贝)一个代替移动 防止后面的节点丢失,找不到了,这里我们使用 cur 代替移动节点
// 遍历打印双向循环链表
public void disPlay() {
Node cur = this.head; // 拷贝头节点，代替头节点移动
while(null != cur) {
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
尾插法
- 我们透过改变我们自行一开始定义的 尾节点, 实现尾插法
public void addList(int data) {
Node node = new Node(data); // 通过双向链表的构造方法，创建节点
Node cur = this.head; // 拷贝头节点，代替头节点的移动
if(null == cur) {
this.head = node;
this.tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = node;
}
}
数值 key 是否存在与该链表当中
- 循环遍历链表并判断
- 同样 注意: 循环结束的条件: (head != null) ,不是 (head.next != null) ,因为当 (head.next == null)后继 为空的时候,其该位置的节点是有存放着数值的,你总不可以丢弃吧, 而 (head == null) 就没有数值了
- 同样我们在移动节点的时候,定义(拷贝)一个代替移动 防止后面的节点丢失,找不到了,这里我们使用 cur 代替移动节点
// 判断数值 key 是否存在与该链表当中循环遍历
public boolean contain(int key) {
Node cur = this.head; // 拷贝头节点，代替头节点的移动
while(null != cur) { // 注意是 cur 不等于 null,不是 cur.next ，
if(key == cur.data) { // cur.next == null其后继为空了，但是它本身的数值是存在的
return true; // 存在，找到，返回 true;
}
cur = cur.next;
}
return false; // 双向链表遍历完，还没有找到，不存在，返回 false
}
计算该双向链表中存在多少个数值
- 循环遍历链表并定义一个计数器 计数
- 同样 注意: 循环结束的条件: (head != null) ,不是 (head.next != null) ,因为当 (head.next == null)后继 为空的时候,其该位置的节点是有存放着数值的,你总不可以丢弃吧, 而 (head == null) 就没有数值了
- 同样我们在移动节点的时候,定义(拷贝)一个代替移动 防止后面的节点丢失,找不到了,这里我们使用 cur 代替移动节点
// 计算该双向链表中存在多少个数值
public int size() {
Node cur = this.head; // 拷贝头节点，代替头节点的移动
int count = 0;
while(null != cur) { // 注意是 cur 不为空，不是 cur.next 因为 next == null其数值需要拿出来的，
cur = cur.next; // cur.next == null,不代表没有数值，
count++;
}
return count;
}
在序号为 index 的位置插入数值节点
- 其实在某某序号插入节点,就是在该序号的前面插入数据节点,因为你看,当在该序号前插入节点的成功后,其原来在该序号的位置的节点就会被后移了,而我们插入的节点就成了该序号的节点位置了
- 首先看判断该 index序号 是否合理
- 在找出该 index序号 的地址
- 根据 index序号 的地址,插入节点
- 移动节点时的 注意 拷贝,复制一份,代替原来的节点移动
// 内部判断该序号 index
private boolean checkIndex(int index) {
if(0 > index || index > size()) {
return false;
}
return true;
}
// 内部查找该序号 index 的节点的地址
private Node searchIndex(int index) {
Node cur = this.head; // 头节点拷贝，代替头节点的移动
if(null == this.head) {
throw new RuntimeException(""链表为空不用找了"");
}
if(checkIndex(index)) {
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur; // 返回该序号的节点的地址
}
return null; // 该序号不合理，返回 null
}
public void addIndex(int index, int data) {
Node cur = searchIndex(index);
if(null == cur) { // 该index 序号不合法
return;
}
if(cur == this.head) { // 等于头节点 ，复用头插法
addFirst(data);
return; // 执行完毕，停止，防止继续执行
}
if(cur == tail) { // 等于尾节点，复用尾插法
addList(data);
return ; // 执行完毕，停止。防止继续执行
}
// 位于中间节点的插入
Node node = new Node(data); // 创建该插入的数值节点
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
删除 n个 第一个数值为 key 的节点
- 循环遍历,对于删除对应数值的节点,考虑该节点出现的位置,处理
- 头节点上,我们移动标识的 首节点 的位置
- 中间位置,尾节点的位置
- 尾节点的 特殊 处理,因为尾节点没有下一个节的地址了
- 对于删除的数值的节点个数计数,到达个数后,停止执行程序 return
- 但是这种方式，当数值存在尾节点上时，因为尾节点next.prev 是没有的，为null
当我们对尾节点使用 next.prev,访问尾节点下一个节点的前驱，就是空引用了，报错
所以我们需要对其判断，不是尾节点，才可以执行 next.prev,
是尾节点的话，就重新标记(尾节点)tial的位置在尾节点的前驱(prev)
public void remove(int key,int n) {
Node cur = this.head; // 头节点的拷贝，代替头节点的移动
while(null != cur) { // 注意是 cur != null,不是 cur.next ,因为 cur.next == null,但是其，是有数值存在的
if(key == cur.data) { // cur == null; 才是没有数值存在的
if(this.head == cur) { // 位于头节点的位置
this.head = cur.next;
head.prev = null;
} else { // 位于中间，尾部
cur.prev.next = cur.next;
if(null != cur.next){ // 位于中间节点的处理
cur.next.prev = cur.prev;
} else { // 位于尾节点的处理
tail = tail.prev;
}
}
System.out.println(key+" 删除成功");
if(1 == n--) { // 计数删除到规定的个数停止
return ; // 只是删除一个数值为key 的节点，删除停止程序，继续执行，防止再删除
}
}
cur = cur.next; // 移动节点
}
System.out.println(key+" 该数值的节点不存在，删除失败");
return; // 链表遍历完了，还没有找到该数值的节点，该数值的节点不存在，停止执行
}
删除全部 key 数值的节点,没有计数，全部删除
- 使用重载方法 对 删除 n个 第一个数值为 key 的节点 进行重载,没有计数,循环 直到 遍历完链表,全部删除
// 删除全部 key 数值的节点,没有计数，全部删除
public void remove(int key) {
Node cur = this.head; // 头节点的拷贝，代替头节点的移动
while(null != cur) { // 注意是 cur != null,不是 cur.next ,因为 cur.next == null,但是其，是有数值存在的
if(key == cur.data) { // cur == null; 才是没有数值存在的
if(this.head == cur) { // 位于头节点的位置
this.head = cur.next;
head.prev = null;
} else { // 位于中间，尾部
cur.prev.next = cur.next;
if(null != cur.next){ // 位于中间节点的处理
cur.next.prev = cur.prev;
} else { // 位于尾节点的处理
tail = tail.prev;
}
}
System.out.println(key+" 删除成功");
}
cur = cur.next; // 移动节点
}
}
清空链表
- Java可以自动回收内存空间,而自动回收空间,有要求 :没有人对其引用,才会被自动回收,如果存在对其引用是不会回收该空间的
- 这里清空链表不像处理单链表一样,只要删除头节点 置为 null ,就没有其他节点对其 引用操作 了 单链表的实现 —— Java_
- 这里是 双向链表 没有了 后继节点 对其的引用,还存在着 前驱节点 求其的引用.
- 所以我们需要 循环遍历 一个一个的释放(置为 null) ,最后跳出循环还有一个尾节点没有置为 null,把他置为null
public void clear() {
while(null != this.head) { // 注意：是 head != null 不是 head.next,head.next == null 也是一个有数值的节点,
Node cur = this.head.next; // 拷贝 代替，防止丢失后面的节点位置
this.head.next = null;
this.head.prev = null;
this.head = cur; // 移动节点
}
this.tail.prev = null; // 最后跳出循环，还有尾节点的前驱，没有置为 null
}
完整的双向链表的实现 代码 MyLinkedList.java
- 双向链表的类,双向链表的功能实现方法
package Project.BothList;
import javax.management.relation.RoleInfoNotFoundException;
class Node { // 创建双向不循环的链表的类
public int data; // 存放的数值
public Node prev; // 前驱节点
public Node next; // 后继节点
public Node(int data) { // 构造方法，赋值数值，创建节点
this.data = data;
this.next = null;
this.prev = null;
}
}
public class MyLinkedList {
private Node head = null; // 标记双向链表的头节点
private Node tail = null; // 标记双向链表的尾节点
public void addFirst(int data) {
Node node = new Node(data); // 通过双向链表的构造方法，创建节点
Node cur = this.head; // 拷贝头节点，代替移动
if(null == this.head) {
// 只有一个节点
this.head = node; // 头尾都是自身
this.tail = node;
} else { // 注意 else 不可以省略，非要省略的话，需要在 head == null 的时候，return 停止程序继续向下执行
cur.prev = node;
node.next = head;
head = node;
}
}
// 遍历打印双向循环链表
public void disPlay() {
Node cur = this.head; // 拷贝头节点，代替头节点移动
while(null != cur) {
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
public void addList(int data) {
Node node = new Node(data); // 通过双向链表的构造方法，创建节点
Node cur = this.head; // 拷贝头节点，代替头节点的移动
if(null == cur) {
this.head = node;
this.tail = node;
} else {
tail.next = node;
node.prev = tail;
tail = node;
}
}
// 判断数值 key 是否存在与该链表当中循环遍历
public boolean contain(int key) {
Node cur = this.head; // 拷贝头节点，代替头节点的移动
while(null != cur) { // 注意是 cur 不等于 null,不是 cur.next ，
if(key == cur.data) { // cur.next == null其后继为空了，但是它本身的数值是存在的
return true; // 存在，找到，返回 true;
}
cur = cur.next;
}
return false; // 双向链表遍历完，还没有找到，不存在，返回 false
}
// 计算该双向链表中存在多少个数值
public int size() {
Node cur = this.head; // 拷贝头节点，代替头节点的移动
int count = 0;
while(null != cur) { // 注意是 cur 不为空，不是 cur.next 因为 next == null其数值需要拿出来的，
cur = cur.next; // cur.next == null,不代表没有数值，
count++;
}
return count;
}
// 内部判断该序号 index
private boolean checkIndex(int index) {
if(0 > index || index > size()) {
return false;
}
return true;
}
// 内部查找该序号 index 的节点的地址
private Node searchIndex(int index) {
Node cur = this.head; // 头节点拷贝，代替头节点的移动
if(null == this.head) {
throw new RuntimeException(""链表为空不用找了"");
}
if(checkIndex(index)) {
for (int i = 0; i < index; i++) {
cur = cur.next;
}
return cur; // 返回该序号的节点的地址
}
return null; // 该序号不合理，返回 null
}
public void addIndex(int index, int data) {
Node cur = searchIndex(index);
if(null == cur) { // 该index 序号不合法
return;
}
if(cur == this.head) { // 等于头节点 ，复用头插法
addFirst(data);
return; // 执行完毕，停止，防止继续执行
}
if(cur == tail) { // 等于尾节点，复用尾插法
addList(data);
return ; // 执行完毕，停止。防止继续执行
}
// 位于中间节点的插入
Node node = new Node(data); // 创建该插入的数值节点
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
public void remove(int key,int n) {
Node cur = this.head; // 头节点的拷贝，代替头节点的移动
while(null != cur) { // 注意是 cur != null,不是 cur.next ,因为 cur.next == null,但是其，是有数值存在的
if(key == cur.data) { // cur == null; 才是没有数值存在的
if(this.head == cur) { // 位于头节点的位置
this.head = cur.next;
head.prev = null;
} else { // 位于中间，尾部
cur.prev.next = cur.next;
if(null != cur.next){ // 位于中间节点的处理
cur.next.prev = cur.prev;
} else { // 位于尾节点的处理
tail = tail.prev;
}
}
System.out.println(key+" 删除成功");
if(1 == n--) { // 计数删除到规定的个数停止
return ; // 只是删除一个数值为key 的节点，删除停止程序，继续执行，防止再删除
}
}
cur = cur.next; // 移动节点
}
System.out.println(key+" 该数值的节点不存在，删除失败");
return; // 链表遍历完了，还没有找到该数值的节点，该数值的节点不存在，停止执行
}
// 删除全部 key 数值的节点,没有计数，全部删除
public void remove(int key) {
Node cur = this.head; // 头节点的拷贝，代替头节点的移动
while(null != cur) { // 注意是 cur != null,不是 cur.next ,因为 cur.next == null,但是其，是有数值存在的
if(key == cur.data) { // cur == null; 才是没有数值存在的
if(this.head == cur) { // 位于头节点的位置
this.head = cur.next;
head.prev = null;
} else { // 位于中间，尾部
cur.prev.next = cur.next;
if(null != cur.next){ // 位于中间节点的处理
cur.next.prev = cur.prev;
} else { // 位于尾节点的处理
tail = tail.prev;
}
}
System.out.println(key+" 删除成功");
}
cur = cur.next; // 移动节点
}
}
public void clear() {
while(null != this.head) { // 注意：是 head != null 不是 head.next,head.next == null 也是一个有数值的节点,
Node cur = this.head.next; // 拷贝 代替，防止丢失后面的节点位置
this.head.next = null;
this.head.prev = null;
this.head = cur; // 移动节点
}
this.tail.prev = null; // 最后跳出循环，还有尾节点的前驱，没有置为 null
}
}
TestDemo.java
- main 测试使用
package Project.BothList;
import Project.BothList.MyLinkedList;
public class TestDemo {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList(); // 静态的方法，无法直接访问非静态的方法，需要实例化
myLinkedList.addFirst(9); // 头插法
myLinkedList.addFirst(99); // 头插法
myLinkedList.addFirst(999);
myLinkedList.disPlay(); // 打印链表
myLinkedList.addList(10);
myLinkedList.addList(100); // 尾插法
myLinkedList.addList(1000); // 尾插法
myLinkedList.disPlay(); // 打印链表
System.out.println(myLinkedList.size()); // 计算链表数据的个数
System.out.println(myLinkedList.contain(999)); // 数值，是否存在该链表中
System.out.println(myLinkedList.contain(9999)); // 数值，是否存在该链表中
myLinkedList.addIndex(0,0); // 在 index 序号中插入数据节点
myLinkedList.addIndex(6,0); // 在 index 序号中插入数据节点
myLinkedList.addIndex(3,0); // 在 index 序号中插入数据节点
myLinkedList.disPlay(); // 打印链表
myLinkedList.remove(0,3); // 删除 n 个 数值为 key 的节点的数值
// myLinkedList.remove(0);
myLinkedList.remove(0);
myLinkedList.disPlay(); // 打印链表
myLinkedList.clear(); // 清空链表
System.out.println("test");
System.out.println("test");
myLinkedList.disPlay(); // 打印链表
}
}
最后:
限于自身水平,其中存在的错误,希望大家可以给予指教,韩信点兵 ------ 多多益善.谢谢大家,后会有期,江湖再见!
