Java中双链表的操作
- 双链表根据内容添加结点
- 双链表根据内容删除结点
- 双链表根据内容修改（新内容替换旧内容）
- 双链表根据内容查找结点索引 索引从0开始
- 根据下标添加结点内容
- 根据下标删除
- 根据下标查找值
- 根据下标修改值
public class DBNode {
// 双向链表和单链表
// 三个域
// 值域
String value;
// 前结点
DBNode pre;
// 后结点
DBNode next;
// 构造方法
public DBNode(String value, DBNode pre, DBNode next) {
this.value = value;
this.pre = pre;
this.next = next;
}
// 重写
@Override
public String toString() {
return "{" +
"value='" + value + '\'' +
", next=" + next +
'}';
}
}
public class MyDBLinked {
// 头结点
private DBNode top;
// 尾结点
private DBNode end;
private int size;
/**
* 双链表根据内容添加结点
*
* @param str 添加内容
*
* @return 添加成功返回true，失败则返回false
*/
public boolean add(String str) {
// 判断原本的链表是不是空链表
if (top == null) {
// 原本的链表为空
top = new DBNode(str, null, null);
// 此时链表只有一个结点，尾结点头结点均为同一个结点；
end = top;
// 链表长度加一
size++;
return true;
}
// 程序走到这里就代表原本的链表不为空
// new一个链表结点，新结点的前驱结点为end;
DBNode node = new DBNode(str, end, null);
// 在双链表的末尾加上node结点
end.next = node;
end = node;
size++;
return true;
}
/**
* 双链表根据内容删除结点
*
* @param str 需要删除的内容
*
* @return 返回删除结点的内容
*/
public String remove(String str) {
// 判断双链表是否为空
if (size == 0) {
// 为空则抛出异常
throw new RuntimeException("双链表为空");
}
// 判断删除的结点是否为头结点
if (top.value.equals(str)) {
// 删除头结点
top = top.next;
// 如果双链表原本就一个结点
if (size == 1) {
end = null;
} else {
// 只有原本的链表多于一个结点的时候，才需要把后移的top的前指向去除
top.pre = null;
}
size--;
return str;
}
// 删除的不是头结点
DBNode mid = top;
// 对结点进行遍历判断,mid=top 即mid为头结点
// mid.next为当前结点
while (mid.next != null && !mid.next.value.equals(str)) {
mid = mid.next;
}
// 程序走到这里，说明结点为尾结点，或者是符合删除要求的结点,或者是未找到符合删除条件的结点
if (mid.next == null) {
// 未找到结点
return null;
}
// 单独对尾结点进行删除处理
// mid.next.next即为当前结点的下一个结点
// mid.next.next == null 即当前结点mid.next为尾结点
if (mid.next.next == null) {
//即要删除的结点为尾结点
// 先记录尾结点旧值
String oldValue = mid.next.value;
// 把当前的尾结点置为null
mid.next = null;
// 当前尾结点mid.next已被置为null，所以需要把尾结点标记迁移
end = mid;
// 整体size-1;
size--;
// 返回删除的值
return oldValue;
}
// 程序走到这，说明mid.next一定就是被找到的符合删除条件的结点
// mid则为符合删除条件结点的前一个结点
// 要删除的目标结点
DBNode targetNode = mid.next;
// 要删除结点的前驱结点的后继结点=要删除结点的后继结点
targetNode.pre.next = targetNode.next;
// 要删除结点的后继结点的前驱结点=要删除结点的前驱结点
targetNode.next.pre = targetNode.pre;
// 到此为止，结点删除成功
size--;
return targetNode.value;
}
/**
* 双链表根据内容修改（新内容替换旧内容）
*
* @param oldStr 旧结点内的内容
* @param newStr 修改之后的内容
*
* @return 修改成功返回true，失败则返回false
*/
public boolean set(String oldStr, String newStr) {
// 参数校验
// 判断双链表是否为空
if (top == null) {
throw new RuntimeException("Linked is null");
}
// 声明遍历链表时的记录结点mid
DBNode mid = top;
//对结点进行遍历，如果结点不为空，即不为尾结点
//或结点不符合替换条件，就继续向后遍历链表
while (mid != null && !mid.value.equals(oldStr)) {
mid = mid.next;
}
// 程序走到这里，说明此时的结点为以下两种情况之一
// 1，mid为null，即未找到符合修改条件的结点
// 2，结点符合修改条件
// 先对mid为null，即未找到符合修改条件的结点 进行判断
if (mid == null) {
// 未找到符合修改条件的结点
return false;
}
// 此时只剩下结点符合修改条件这一种情况，直接替换修改即可
mid.value = newStr;
return true;
}
/**
* 双链表根据内容查找结点索引 索引从0开始
*
* @return 返回结点的索引
*/
public int getIndex(String str) {
//判断链表是否为空
if (top == null) {
throw new RuntimeException("Linked is null");
}
// 记录结点
DBNode mid = top;
//定义变量，记录索引值
int count = 0;
// 对结点进行遍历，直到查到尾结点或者找到符合要求的结点
while (mid != null && !mid.value.equals(str)) {
mid = mid.next;
count++;
}
// 未找到符合要求的结点
if (mid == null) {
return -1;
}
// 程序走到这里，说明已经找到符合要求的结点，返回索引记录值
return count;
}
/**
* 根据下标添加结点内容
*
* @param index 添加元素位置
* @param str 添加内容
*
* @return 添加成功返回true，失败则返回false
*/
public boolean addByIndex(int index, String str) {
// 校验需要添加的位置是否合法
if (index > size || index < 0) {
throw new RuntimeException("index is Illegal");
}
// 参数合法，继续执行
// 创建需要添加的结点的对象
DBNode dbNode = new DBNode(str, null, null);
// 需要添加的结点是头结点，即index为0，size=0
if (index == 0) {
// 新结点的下一个结点指向原结点的头结点
dbNode.next = top;
if (top != null) {
// 如果原链表不为空，原结点的前驱结点指向新节点
top.pre = dbNode;
} else {
// 原链表为空，尾结点指向新节点
end = dbNode;
}
// 把头结点标记前移
top = dbNode;
// 结点长度+1
size++;
return true;
}
// 程序既然执行到这里，size就不会为0
// 如果需要添加的结点为尾结点，即index=size
if (index == size) {
// 新结点的前驱指向原旧结点
dbNode.pre = end;
// 原尾结点的后继指向该添加到尾部的结点
end.next = dbNode;
// 尾结点后移
end = dbNode;
size++;
return true;
}
// 程序走到这里就说明需要添加的位置在头结点和尾结点之间
// mid用来标记要添加位置的前一个位置
DBNode mid = top;
// 声明count记录链表位置
int count = 1;
// 对链表进行遍历
while (index != count) {
mid = mid.next;
count++;
}
// 当index==count时，就会跳出循环，即满足添加条件
// 把新结点添加到mid和mid.next中间
dbNode.next = mid.next;
dbNode.pre = mid;
dbNode.next.pre = dbNode;
mid.next = dbNode;
size++;
return true;
}
/**
* 根据索引删除
*
* @param index 需要删除位置的索引
*
* @return 返回被删除的内容
*/
public String removeByIndex(int index) {
// 对链表进行参数校验
if (top == null) {
throw new RuntimeException("linked is null");
}
// 校验要查找的索引是否合法(索引从0开始)
if (index < 0 || index > size - 1) {
throw new RuntimeException("param is Illegal");
}
//为提高查找效率，获取元素所属的范围
int midIndex = size / 2;
// 判断需要查找元素所属的范围
// 声明一个空结点
DBNode mid = null;
if (midIndex > index) {
// 要删除的元素在链表的前半部分
// 头结点
mid = top;
int count = 0;
while (count != index) {
count++;
mid = mid.next;
}
} else {
// 要删除的元素在后半部分
mid = end;
int count = size - 1;
while (count != index) {
count--;
mid = mid.pre;
}
}
// mid 就是要删除的结点
// 如果mid是头结点
if (mid == top) {
// 使头结点后移
top = top.next;
// 如果后移之后结点变为null
if (top == null) {
// 代表原链表仅有一个结点
end = null;
} else {
// 代表链表不仅仅只有一个结点
top.pre = null;
}
size--;
return mid.value;
}
// 如果删除的是尾结点
if (mid == end) {
end = end.pre;
// 链表和原尾结点断开连接
end.next = null;
size--;
return mid.value;
}
// 删除的既不是头结点，也不是尾结点
mid.pre.next = mid.next;
mid.next.pre = mid.pre;
size--;
return mid.value;
}
/**
* 根据下标查找值
* @param index 提供的下标
* @return 返回查找到的值
*/
public String get(int index){
// 参数效验
if (top == null) {
throw new IllegalArgumentException("mylinked is null");
}
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("param is Illegal");
}
// 获取中间位置下标
int midIndex = size/2;
DBNode mid = null;
if (index < midIndex){
// 查找值在前半部分
mid = top;
int tag = 0;
// 从头结点向后遍历
while (tag != index){
mid = mid.next;
tag++;
}
} else {
// 查找值在后半部分
mid = end;
int tag = size - 1;
// 从尾结点向前遍历
while (tag != index){
mid = mid.pre;
tag--;
}
}
return mid.value;
}
/**
* 根据下标修改值
* @param index 需要修改的下标位置
* @param str 修改的新值
* @return 被覆盖的旧值
*/
public String set(int index, String str){
// 参数效验
if (top == null) {
throw new IllegalArgumentException("mylinked is null");
}
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("param is Illegal");
}
// 获取中间位置下标
int midIndex = size/2;
DBNode mid = null;
if (index < midIndex){
// 查找值在前半部分
mid = top;
int tag = 0;
// 从头结点向后遍历
while (tag != index){
mid = mid.next;
tag++;
}
} else {
// 查找值在后半部分
mid = end;
int tag = size - 1;
// 从尾结点向前遍历
while (tag != index){
mid = mid.pre;
tag--;
}
}
// 保存旧值
String oldValue = mid.value;
// 替换新值
mid.value = str;
return oldValue;
}
@Override
public String toString() {
return "DemoLinked1{" +
"top=" + top +
", end=" + end +
", size=" + size +
'}';
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/181129.html
