数据结构(2):单链表学习使用java实现

package com.Exercise.DataStructure_Algorithm.SingleList;import java.util.Stack;public class SingleTest1 {
public static void main(String[] args) {
Node node1 = new Node(1, "admin1");
Node node2 = new Node(2, "admin2");
// Node node3 =new Node(3,"admin2");
Node_Manage node_manage = new Node_Manage();
// node_manage.list(); node_manage.add3(node1);
node_manage.add3(node2);
// node_manage.add3(node3);
System.out.println("显示数据:");
// node_manage.add3(node3);
node_manage.list();
// Node node4 =new Node(2,"admin3");
// Node node5 =new Node(4,"admin4");
// node_manage.update(node4);
// node_manage.update(node5);
// //修改后显示数据
// System.out.println();
// System.out.println("修改后的数据:");
// node_manage.list();
// System.out.println("删除后的数据显示:");
// //node_manage.delete(0);
// node_manage.list();
// int length = SingleTest1.getLength(node_manage.getHeader());
// //int length1 = SingleTest1.getLength(node_manage.getSignx());
// System.out.println("单链表长度是:"+length);
// System.out.println("倒数第一个节点数据内容:");
// //查找倒数第1个节点的数据
// Node node = SingleTest1.findNode(node_manage.getHeader(), 1);
// System.out.println(node);
// System.out.println("正向第一个数据节点数据内容:");
// //查找正向第一个节点数据
// Node nodeT = SingleTest1.find2Node(node_manage.getHeader(),3);
// System.out.println(nodeT);
System.out.println("翻转后数据内容:");
//翻转
// SingleTest1.reversalList(node_manage.getHeader());
// SingleTest1.reversalList(node_manage.getHeader());
SingleTest1.reverse2(node_manage.getHeader());
// node_manage.list();
} //求节点有效个数 从头节点开始 节点长度
public static int getLength(Node header) {
//如果节点为空,说明长度为0
if (header.next == null) {
return 0;
}
//辅助节点,从头节点的下一个节点开始
Node current = header.next;
int length = 0;
while (current != null) {
//如果节点没走到尾
length++;
current = current.next;
}
return length;
} //查找倒数第n个节点的数据
public static Node findNode(Node node, int index) {
if (node.next == null) {
System.out.println("单链表没有数据,无法进行节点查找");
}
Node current = node.next;
//获取长度
int size = getLength(node);
System.out.println(size);
if (index <= 0 || index > size) {
return null;
}
for (int i = 0; i < size - index; i++) {
current = current.next;
}
return current;
} //查找正向第n个节点的数据
public static Node find2Node(Node node, int index) {
if (node.next == null) {
System.out.println("单链表没有数据,无法进行节点查找");
}
Node current = node;
//获取长度
int size = getLength(node);
System.out.println(size);
if (index <= 0 || index > size) {
return null;
}
for (int i = 0; i < index; i++) {
current = current.next;
}
return current;
} //[] [1] [2] [3] old
//[] [3] [2] [1]
//new: [3] [2] [1]
//old.next = new.next
//old = [3] [2] [1]
//翻转
public static void reversalList(Node node) {
Node current = node.next;
Node next = null;
//初始化
Node reverseNode = new Node(0, "");
while (current != null) {
next = current.next;
current.next = reverseNode.next;
reverseNode.next = current;
current = next;
}
node.next = reverseNode.next;
} public static void reverse(Node head) {
//存储数据的
Node current = head.next;
//初始化 新的翻转节点
Node reverseNode = new Node(0,"");
Node next = null;
//如果不为空就翻转
while(current!=null){
//存储数据的下一个节点
next = current.next;
current.next = reverseNode.next;
//摘取current的数据内容给新的翻转节点
reverseNode.next = current;
//把current指向下一个节点
current = next;
}
head.next = current.next;
} //单链表反转使用堆栈 先进后出的原理逆序实现
public static void reverse2(Node head){
Node current = head.next;
Stack<Node> nodes = new Stack<Node>();
if(head.next == null){
System.out.println("单链表为空");
}
while(current!=null){
nodes.push(current);
current = current.next;
} while(nodes.size()>0){
Node pop = nodes.pop();
System.out.println(pop);
}
}}class Node_Manage{
//单链表初始化
Node signx =new Node(0,""); public Node getSignx() {
return signx;
} Node header = signx; public Node getHeader() {
return header;
} Node tail = header;
// header tail
// [] ---> [] ---> [] ---> [] ----> [] ---> []
//链表创建插入数据
//没有顺序的添加插入数据
public void add(Node new_node){
Node current = header;
while(true){
if(current.next==null){
break;
}
current = current.next; }
current.next = new_node;
} //没有顺序的添加插入数据
// t t --> t
// [] ---> [1]--->[2] --[3]
public void add2(Node new_node){
tail.next = new_node;
tail = tail.next;
} //按顺序插入数据
// 1 2 3
// [] --> [*] --> []
public void add3(Node new_node){
Node current = header;
//标识符
boolean flag = false;
while(true){
if(current.next==null){
break;
}else if(current.next.id > new_node.id){
break;
}else if(current.next.id == new_node.id){
flag = true;
break;
}
current = current.next;
} if(flag){
System.out.println("链表里面已经有这个节点了,无法添加数据了");
}else{
// (代加入的数据*)
// [*]
//[] -- -- []
//新增数据
new_node.next = current.next;
current.next = new_node;
}
} //删除单链表节点
public void delete(int node){
if(header == null){
System.out.println("要删除的节点的单链表为空");
}
Node current = header;
boolean flag = false;
while(true){
//链表走到了最后
if(current.next==null){
break;
}
//如果找到了,标识符就为true
if(current.next.id == node){
flag = true;
break;
}
//向后移动
current = current.next;
}
/*如果找到了
current -> next -> next
//[1] [待删除的2] [3]*/
//[1] [3]
if(flag){
current.next = current.next.next;
}else{
System.out.println("这个节点不在单链表中,无法删除");
}
} //单链表修改 根据id进行修改
public void update(Node NewNode){
if(header.next==null){
System.out.println("当前单链表为空");
}
Node current = header.next;
boolean flag = false; //标识符 默认是false
while(true){
if(current==null){
break;
}
if(current.id == NewNode.id){
flag = true;
break;
}
current = current.next;
}
if(flag){
current.name = NewNode.name;
}else{
System.out.printf("单链表中不存在%d数字的节点,无法修改",NewNode.id);
} } //显示链表
public void list(){
Node current = header.next;
while(true){
System.out.println(current);
if(current == null){
break;
}
if(current.next==null){
break;
}
current = current.next;
}
}}class Node{
public int id;
public String name;
public Node next;
public Node(int id,String name){
this.id=id;
this.name=name;
} @Override
public String toString() {
return "Signx{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}

//[] [1] [2] [3] old
//[] [3] [2] [1]
//new: [3] [2] [1]
//old.next = new.next
//old = [3] [2] [1]
//翻转
public static void reversalList(Node node) {
Node current = node.next;
Node next = null;
//初始化
Node reverseNode = new Node(0, "");
while (current != null) {
next = current.next;
current.next = reverseNode.next;
reverseNode.next = current;
current = next;
}
node.next = reverseNode.next;
}