一、理论
1 单链表结构
2 增、删、查 、改思路
- （增）直接添加放到最后即可。按顺序添加：找到要修改的节点的前一个节点，插入新节点（）。
- （改）要修改的节点修改内容即可。
- （删）找到待删除节点的前一个节点，把要删除节点的后一个节点信息存放到该节点的next即可
- （查==较容易）遍历依次打印即可。按编号查找，找到对应编号打印即可
二、代码实现
1、JAVA代码实现
package basicdata;
public class SingleLinkedListTest {
public static void main(String[] args) {
Node node1 = new Node(123, "Tom", "无极剑道");
//
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.addNode(node1);
singleLinkedList.list();
System.out.println("*******************");
singleLinkedList.addByOrder(new Node(234, "Jack", "断头斩杀"));
singleLinkedList.addByOrder(new Node(121, "Jack", "断头斩杀"));
singleLinkedList.addByOrder(new Node(121, "Jack", "断头斩杀"));
singleLinkedList.list();
//System.out.println("******修改后*******");
//singleLinkedList.alter(new Node(121, "Bob", "无形之刃"));
//singleLinkedList.list();
// System.out.println("**************");
//singleLinkedList.delNode(234);
System.out.println("***反转后***");
singleLinkedList.reverSetList();
singleLinkedList.list();
}
}
//
class SingleLinkedList{
// 先初始化一个头结点,头节点不存放数据
private Node head = new Node(0,"表头","领导单链表");
// 返回表头
public Node getHead(){
return head;
}
public SingleLinkedList() {
}
// 添加节点到单链表，按添加顺序排列
public void addNode(Node node){
// 思路：把头结点的地址给temp
// 直到next = null时，让next存放添加的节点
Node temp = head;
while (true){
if (temp.next == null) {
break;
}
else {
temp = temp.next;
}
}
// 退出while 循环时 temp.next = null
temp.next = node;
}
// 遍历单链表
public void list(){
Node temp = head;
if (head == null) {
System.out.println("链表为空");
return;
}
while (true){
if (temp == null) {
break;
}
else {
// 输出节点信息
System.out.println(temp);
// 指针后移
temp = temp.next;
}
}
}
// 根据编号顺序插入节点 ，链表内容按编号从小到大排列
public void addByOrder(Node node){
// 需要先找到要添加位置的前一个节点
// 链表为空不需要单独考虑
Node temp = head;
// 为找到插入位置 需要一个 flag
boolean flag = false;
while (true){
// 此情况可以添加，添加到表头后
if (temp.next == null) { // 到链表末端
break;
}
// 此情况不可以添加，要添加的编号已经存在
if (temp.next.number == node.number) {
flag = true;
break;
}
//此情况为找到要添加位置的前一个节点，可以添加
if (temp.next.number > node.number) {
break;
}
else {
temp = temp.next;
}
}
if (flag ) {
System.out.printf("你要插入的节编号%d已经存在",node.number);
System.out.println();
}
else {
node.next = temp.next ;
temp.next=node;
}
}
// 修改节点信息（根据编号）,编号不变，修改内容
public void alter(Node node){
if (head.next == null) {
System.out.println("链表为空");
return;
}
// 和按编号插入(Node temp = head;)稍微有点区别
// Node temp = head.next;
Node temp = head.next;
boolean flag = false;
while (true){
if (temp == null) {
break;
}
// 找到要修改的节点，可以修改
if (temp.number == node.number) {
flag = true;
break;
}
else {
temp = temp.next;
}
}
if (flag) {
// 修改
temp.name = node.name;
temp.skill= node.skill;
}
else {
System.out.println("没有找到要修改的节点");
}
}
// 根据编号删除节点
public void delNode(int number){
//需要找到待删除的前一个节点
Node temp = head;
boolean flag = false;
while (true){
if (temp.next == null) {
break;
}
//找到待删除的前一个节点
if (temp.next.number == number) {
flag = true;
break;
}
else {
temp = temp.next;
}
}
if (flag ) {
//
temp.next = temp.next.next;
}
else {
System.out.println("要删除的元素不存在");
}
}
// 反转单链表
public void reverSetList(){
if (this.head.next== null||this.head.next.next==null) {
return;
}
Node tempCur = this.head.next; // 辅助变量
Node tempNext = null; // 指向tempCur，不然会丢失
Node reverSetHead = new Node(0, "", ""); // 新链表
while (tempCur != null){
tempNext = tempCur.next; //存储当前节点的下一节点
tempCur.next = reverSetHead.next;// 头插法 把当前节点接到到reverSetHead
reverSetHead.next = tempNext;
tempCur=tempNext;// 后移
}
this.head.next = reverSetHead.next;
}
}
// 定义Node
class Node{
public int number;
public String name;
public String skill;
public Node next; //存放下一个节点地址
//构造器
public Node(int number, String name, String skill) {
this.number = number;
this.name = name;
this.skill = skill;
//this.next = next;
// 理解：不给next赋值
//没申请一个节点时 next = null
}
//重写 toString
@Override
public String toString() {
return "Node{" +
"number=" + number +
", name='" + name + '\'' +
", skill='" + skill + '\'' +
'}';
}
}
运行结果
Node{number=0, name='表头', skill='领导单链表'}
Node{number=123, name='Tom', skill='无极剑道'}
*******************
你要插入的节编号121已经存在
Node{number=0, name='表头', skill='领导单链表'}
Node{number=121, name='Jack', skill='断头斩杀'}
Node{number=123, name='Tom', skill='无极剑道'}
Node{number=234, name='Jack', skill='断头斩杀'}
******修改后*******
Node{number=0, name='表头', skill='领导单链表'}
Node{number=121, name='Bob', skill='无形之刃'}
Node{number=123, name='Tom', skill='无极剑道'}
Node{number=234, name='Jack', skill='断头斩杀'}
删除后**************
Node{number=0, name='表头', skill='领导单链表'}
Node{number=121, name='Bob', skill='无形之刃'}
Node{number=123, name='Tom', skill='无极剑道'}
2、C语言代码实现
