Java 实现双向链表的基本操作
Node cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
return cur;
}
public void addIndex(int index,int data){
checkIndex(index);
if(index == 0){
addFirst(data);
return;
}
if(index == len()){
addLast(data);
return;
}
Node node = new Node(data);
Node cur = searchIndex(index);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
[](()5.查找链表中是否包含关键字 key
比较简单，直接贴代码：
public boolean containKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}
[](()6.删除第一次出现关键字为 key 的节点
思考：
直接上图解：
代码实现：
public void deleteKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
//头节点
if(cur == this.head){
this.head = this.head.next;
this.head.prev = null;
}
//中间节点
else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//删除的是尾节点,只需要移动 tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
[](()7.删除所有出现关键字为 key 的节点
思考：
根据删除第一次出现关键字为 key 的节点，修改代码即可，考虑特殊情况
代码实现：
public void deleteAllKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
//头节点
if(cur == this.head){
this.head = this.head.next;
if(this.head != null){
this.head.prev = null;
}
}
//中间节点
else{
cur.prev.next = cur.next;
if(cur.next != null){
cur.next.prev = cur.prev;
}
//删除的是尾节点,只需要移动 tail
else{
this.tail = cur.prev;
}
}
}
cur = cur.next;
}
}
[](()8.链表长度
比较简单，直接贴代码：
public int len(){
int count = 0;
Node cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
[](()9.链表清空
首先会想到以下代码：
public void clear(){
this.head = null;
}
测试打断点调试：
System.out.println("===============");
DoubleLinkedList doubleLinkedList3 = new 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 DoubleLinkedList();
doubleLinkedList3.addLast(1);
doubleLinkedList3.addLast(2);
doubleLinkedList3.addLast(3);
doubleLinkedList3.addLast(4);
doubleLinkedList3.print();
doubleLinkedList3.clear();
System.out.println("!!!!!!!!!!!!!!!!!!!!!");
然后打开 cmd：
输入 jps
重定义到一个文本文件
找到 log.txt 所在目录，打开 log.txt
双击打开后，ctrl + f，搜索 Node
仍然有4个，说明插入的4个数据没有被回收掉！
**故：仅仅将 head 置为null，不能实现链表清空**
解决方法：
大家可以按照上述调试检测，数据是否被回收~
public void clear(){
//一个一个节点进行释放
while(this.head != null){
Node cur = this.head.next;
this.head.prev = null;
this.head.next = null;
this.head = cur;
}
this.tail = null;
}
[](()附全部代码：
class Node{
public int data;//数据
public Node next;//后继信息
public Node prev;//前驱信息
//提供构造方法
public Node(int data){
this.data = data;
}
}
public class DoubleLinkedList {
public Node head; //表示双向链表的头
public Node tail; //表示当前双向链表的尾
//1.打印链表
public void print(){
Node cur = this.head;
while(cur != null){
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
//2.头插法
public void addFirst(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
//3.尾插法
public void addLast(int data){
Node node = new Node(data);
//第一次插入
if(this.head == null){
this.head = node;
this.tail = node;
}
//不是第一次插入
else{
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
}
private void checkIndex(int index){
if(index < 0 || index > len()){
throw new RuntimeException("index 不合法！！");
}
}
private Node searchIndex(int index){
Node cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//4.任意位置插入，第一个数据节点为 0 号下标
public void addIndex(int index,int data){
checkIndex(index);
if(index == 0){
addFirst(data);
return;
}
if(index == len()){
addLast(data);
return;
}
Node node = new Node(data);
Node cur = searchIndex(index);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
//5.查找链表中是否包含关键字 key
public boolean containKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
return true;
}
cur = cur.next;
}
return false;
}
//6.删除第一次出现关键字为 key 的节点
public void deleteKey(int key){
Node cur = this.head;
while(cur != null){
if(cur.data == key){
//头节点
if(cur == this.head){
this.head = this.head.next;
还未添加个人签名 2022.04.13 加入
还未添加个人简介
评论