Java学习05-链表
2021-05-28 22:03
标签：value 位置 外部 als rac 开始 改变 node节点 lock 单向链表中的节点由两部分组成： 节点储存的数据 data 指向下一个节点的地址 next 相比于数组，链表的增删操作不会影响过多数据的位置，易于进行增删操作 链表的各个节点在内存中的位置是无序的，每次进行查找时只能从头节点开始依次搜寻，检索效率慢 插入新节点时，使要插入位置的前一个节点指向新节点，使新节点指向后一个节点 代码实现： 删除节点时，仅需要把目标节点的前一个节点指向目标节点后的一个节点即可，未被指向的节点会被自动处理（head节点除外). 代码实现： Java学习05-链表 标签：value 位置 外部 als rac 开始 改变 node节点 lock 原文地址：https://www.cnblogs.com/TSCCG/p/14774451.html1. 单向链表
1.1 单向链表的结构
1.2 单向链表的特点
1.2.1 单向链表的优点：
1.2.2 单向链表的缺点
1.3 单向链表节点的插入
/**
* @author TSCCG
* @date 2021/5/16
* 在指定节点后面插入新节点
*/
/*
* 节点类：
*/
private class Node{
Object data;//每个节点的数据
Node next;//每个节点指向下一个节点的连接
public Node(Object data){
this.data = data;
}
}
/*
* 插入方法：
*/
public void addExactly(Object value,Object newObj){
if(size == 0){
return;
}
//定义一前一后两个搜索节点
Node previous = head;
Node current = head;
//判断previous是否是目标节点
while(previous.data != value){
/**
* 既然能进入while循环，说明此时previous不是目标节点，
* 当previous的next指向为null时，说明链表已经检索完毕，此链表没有找到目标节点
*/
if(previous.next == null){
return;
}else{
//使previous位于current前面一位
previous = current;
current = current.next;
}
size++;
}
/**
* 程序运行到此步，说明已经找到目标节点，此时previous就是目标节点，current是previous后一位节点
* 创建一个新节点，使previous指向新节点，使新节点指向current。如此，就实现了在目标节点后添加新的节点
*/
Node newNode = new Node(newObj);
previous.next = newNode;
newNode.next = current;
}
1.4 单向链表节点的删除
/**
* @author TSCCG
* @date 2021/5/16
* 删除指定节点
*/
/*
* 节点类：
*/
private class Node{
//节点的数据
Object data;
//下一个节点的地址
Node next;
public Node(Object data){
this.data = data;
}
}
/**
* 删除方法
*/
public void delete(Object value){
//判断链表是否为空
if(size == 0){
System.out.println("没有此节点！");
return;
}
//跟前面的插入一样，定义一前一后两个搜索节点，previous在前，current在后
Node current = head;
Node previous = head;
//判断current是否为目标节点
while(current.data != value){
//若current.next==null,说明程序已经检索完毕，仍没有找到目标节点，说明没有目标节点
if(current.next == null){
System.out.println("没有此节点！");
return;
}else{
//current将当前位置赋给previous,自身向后移动
previous = current;
current = current.next;
}
}
//此时current就是目标节点，previous位于目标节点的前一位
//如果删除的节点是第一个节点,直接使head的后一位节点成为新的头节点即可
if(current == head){
head = current.next;
}else{
//如果目标节点不是头节点，那么就将previous指向current的后一位即可
previous.next = current.next;
}
size--;
}
1.5 实现一个可进行增删查改的单向链表
Node节点类：
/**
* @author: TSCCG
* @date: 2021/5/16
*/
public class Node {
//为了不让外部类使用Node类，使用private修饰data和next
/**
* 节点储存的数据
*/
private Object data;
/**
* 节点存储的指向下一个节点的地址
*/
private Node next;
public Node(Object data) {
this.data = data;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
主类：
/**
* @author: TSCCG
* @date: 2021/5/16
*/
public class LinkedListPractice{
/**
* 定义头节点
*/
private Node head;
/**
* 定义链表长度，默认为0
*/
private int size;
/**
* 从链表头部添加节点
*/
public void addHead(Object data) {
//创建新节点
Node tempNode = new Node(data);
//当链表为空时，使新节点成为头节点
if (size == 0) {
head = tempNode;
} else {
//使新创建的节点指向旧的头节点
tempNode.setNext(head);
//使新创建的节点成为新的头节点
head = tempNode;
}
//链表长度加1
size++;
}
/**
* 从链表尾部添加节点
*/
public void addEnd(Object data) {
//创建新节点
Node newNode = new Node(data);
if (size == 0) {
//当链表为空时，使新节点成为头节点
head = newNode;
} else {
//当链表不为空时，找到当前链表的末节点，使其指向新节点，新节点成为新的末节点
findEnd(head).setNext(newNode);
}
//链表长度加1
size++;
}
/**
* 在指定位置后面插入新节点,
*/
public void addExactly(Object value,Object data){
if(size == 0){
return;
}
//定义一前一后两个搜索节点
Node previous = head;
Node current = head;
//判断previous是否是目标节点
while(previous.getData() != value){
/*
* 既然能进入while循环，说明此时previous不是目标节点，
* 当previous的next指向为null时，说明链表已经检索完毕，此链表没有找到目标节点
*/
if(previous.getNext() == null){
return;
}else{
//使previous在current位于前面一位
previous = current;
current = current.getNext();
}
}
/*
* 程序运行到此步，说明已经找到目标节点，
* 此时previous就是目标节点，current是previous后一位节点
* 创建一个新节点，使previous指向新节点，使新节点指向current。
*/
Node newNode = new Node(data);
previous.setNext(newNode);
newNode.setNext(current);
size++;
}
/**
* 删除指定节点
*/
public void deleteNode(Object value) {
//判断链表是否为空
if (size == 0) {
System.out.println("没有此节点！");
return;
}
//跟前面的插入一样，定义一前一后两个搜索节点，previous在前，current在后
Node current = head;
Node previous = head;
//判断current是否为目标节点
while (current.getData() != value) {
//若current.next==null,说明程序已经检索完毕，仍没有找到目标节点，说明没有目标节点
if (current.getNext() == null) {
System.out.println("没有此节点！");
return;
} else {
//current将当前位置赋给previous,自身向后移动
previous = current;
current = current.getNext();
}
}
//此时current就是目标节点，previous位于目标节点的前一位
//如果删除的节点是第一个节点,直接使head的后一位节点成为新的头节点即可
if (current == head) {
head = current.getNext();
} else {
//如果目标节点不是头节点，那么就将previous指向current的后一位即可
previous.setNext(current.getNext());
}
size--;
}
/**
* 找到尾节点
*/
public Node findEnd(Node node) {
if (node.getNext() == null) {
return node;
}
//使用递归
return findEnd(node.getNext());
}
/**
* 显示节点信息
*/
public void showList() {
if (size > 0) {
//为不改变链表真实长度，定义一个变量储存目前的链表长度，同理，定义一个临时头节点
int tempSize = size;
Node tempNode = head;
//当链表只有一个节点时，打印数据后直接返回
if (tempSize == 1) {
System.out.println("[" + tempNode.getData() + "]");
return;
}
while (tempSize > 0) {
if (tempNode.equals(head)) {
//打印头节点
System.out.print("[" + tempNode.getData() + "->");
} else if (tempNode.getNext() == null){
//打印尾节点
System.out.println(tempNode.getData() + "]");
} else {
//打印中间节点
System.out.print(tempNode.getData() + "->");
}
tempNode = tempNode.getNext();
tempSize--;
}
} else {
//空链表
System.out.println("[]");
}
}
}
测试类：
/**
* @author: TSCCG
* @date: 2021/5/16
*/
public class LinkedListPracticeTest {
public static void main(String[] args) {
LinkedListPractice link = new LinkedListPractice();
link.addEnd("AA");
link.addEnd("bb");
link.addEnd("CC");
link.addEnd("DD");
link.addExactly("CC","FFF");
link.showList();
link.deleteNode("bb");
link.showList();
}
}
结果：
[AA->bb->CC->FFF->DD]
[AA->CC->FFF->DD]
下一篇：Java 8 并行流与串行流