数据结构之单链表实现（JAVA语言+C语言）

一、理论

1 单链表结构

在这里插入图片描述

2 增、删、查、改思路

（增）直接添加放到最后即可。按顺序添加：找到要修改的节点的前一个节点，插入新节点（）。
（改）要修改的节点修改内容即可。
（删）找到待删除节点的前一个节点，把要删除节点的后一个节点信息存放到该节点的next即可
（查==较容易）遍历依次打印即可。按编号查找，找到对应编号打印即可

二、代码实现

1、1JAVA代码实现

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 = nulltemp.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;// 为找到插入位置 需要一个 flagboolean 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;// 头插法 把当前节点接到到reverSetHeadreverSetHead.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@Overridepublic String toString() {return "Node{" +"number=" + number +", name='" + name + '\'' +", skill='" + skill + '\'' +'}';}
}

1.2运行结果

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、1 C语言代码实现

#include <stdio.h>
#include <stdlib.h>// 结构 是自定义类型的一种
// typedef 类型定义，（类型重定义）  
typedef struct Node {int data;// next是指针，指向地址的类型是Node型struct Node* next;
}Node;//初始化头结点函数
Node* initList() {//给指针变量分配一个Node型存储空间。Node* list = (Node*)malloc(sizeof(Node));list->data = 0;list->next = NULL;return list; 
}//头插法
void headInset(Node* list, int data) {//给指针变量分配一个Node型存储空间。Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = list->next;// 理解插入节点变成头结点list->next = node;}//尾插法
void tailInsert(Node* list, int data) {Node* temp = list;Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = NULL;//找到尾while (temp->next){temp = temp->next;}temp->next = node;
}
// 删除操作
//默认数据无重复
void deleteNum(Node* list, int data) {Node* temp = list->next;Node* pre = list;//找到待删除节点while (temp) {if (temp->data ==  data){//删除pre->next = temp->next;//释放内存free(temp);//如果有重复数据，不要breakbreak;}//往后移动一个节点pre = temp;temp = temp->next;}}// 打印
void printList(Node* list) {Node* temp = list->next;while (temp){printf("%d", temp->data);temp = temp->next;}printf("\n");
}int main() {Node* list = initList();printf("头插结果：");headInset(list, 1);headInset(list, 2);headInset(list, 3);headInset(list, 4);printList(list);printf("尾插56插结果：");tailInsert(list, 5);tailInsert(list, 6);printList(list);printf("删除3 后结果：");deleteNum(list, 3);printList(list);return 0;
}