数据结构-链表(Java实现) 作者:哇塞大嘴好帥

作者:哇塞大嘴好帥(哇塞大嘴好帅)

1.链表的介绍

​ 第一个节点是头节点，他不存放任何数据，他的任务只有指向第一个真正存放数据的的节点。每一个节点都有next属性，next是指向下一个节点。如果next为NULL就证明当前节点是尾节点。

​ 链表的优点：

​ 插入删除不需要移动其他元素，只需要更改指针即可。效率高。

​ 链表在内存空间中不要求连续，空间利用率高。

​ 大小没有固定，扩展灵活。

​ 链表的缺点：

​ 查询数据效率低。

2.代码解析

2.1链表节点元素

//链表中的元素 class LinkedDate{ int on; //当前序号 String data; //存放的数据 LinkedDate next; //指向下一个链表 @Override public String toString() { return "LinkedDate{" + "on=" + on + ", data='" + data + '\'' + '}'; } public LinkedDate(int on, String data) { this.on = on; this.data = data; } }

2.2 浏览所有元素

//浏览链表 public void showList(){ //创建临时变量 指向节点位置使用 // headNode.next 头节点的下一个节点，因为头节点的任务只是指向第一个存放数据的链表 LinkedDate temp = headNode.next; while(true){ //如果当前为NULL要不就是到了尾节点要不就是当前链表为NULL if (temp == null){ break; } System.out.println(temp); //指针下移动 指向下一个个元素 temp = temp.next; } }

如果链表有数据

​ 如以下图：当我们第一次循环，指针所在的位置next，此处不为NULL不满足代码中的if判断，并且打印了此处节点，第二次循环也发现此处不为NULL,也打印了此处节点，第三次… 当到了某一次循环发现当前节点为NULL，就证明了后方没有数据了，当前链表也遍历完了。

​ 如果遍历没有数据

​ 当我们进入while循环，发现当前节点为NULL，也就是说当前链表没有数据了。

​

2.3 添加节点（节点数据ON为序号，已按照序号序列添加）

//添加元素 public void putNode(LinkedDate Node){ //创建临时变量 指向头节点 LinkedDate temp = headNode; while(true){ //如果链表为Null if (temp.next == null){ break; } //查找薪数据属于链表的某个位置 if (temp.next.on > Node.on){ break; } //指针移动 temp = temp.next; } //添加到链表中 Node.next = temp.next; temp.next = Node; }

如果链表没有节点：

​ 如果头节点的下一个没有节点，就证明了当前链表没有元素。

​ 当我们发现当前链表没有节点 跳出了循环。这时候我们插入节点。

//添加到链表中 Node.next = temp.next; temp.next = Node;

​ 首先我们将要插入的节点的下一个指向temp的下一个节点。（这时候temp指向的是头节点），接下来我们temp下一个节点指向Node。

2.4 删除节点

//删除元素 public void deleteNode(int id){ LinkedDate temp = headNode.next; while(true){ if (temp.on == id){ break; } //指针下移动 temp = temp.next; } temp.next = temp.next.next; }

​ 通过while循环找到我们要删除的元素，当我们找到我们要删除的元素我们只需要更改指针即可。

为什么是temp.next.next,因为temp.next在的位置是指针所在的位置，temp.next.next的位置是指针所在的位置的下一个节点。我们直接更改指针就可以做到删除元素.

2.5 更改节点数据

//修改数据 public void updateNode(LinkedDate Node){ LinkedDate temp = headNode.next; while(true){ if (temp == null){ System.out.println("没有此数据"); return; } //如果on相等进行修改t if (temp.on == Node.on){ temp.data = Node.data; return; } / temp = temp.next; } }

​ 道理相同，我们通过while循环找到我们要修改的数据，当我们找到我们只需要把传递的Node.data赋值给要修改的节点的**.data**即可。

2.6尾添加

//尾添加 public void foodput(LinkedDate Node){ LinkedDate temp = headNode; while (true){ //如果满足就代表已经到了列表尾 if (temp.next == null){ break; } //指针下移动 temp = temp.next; } temp.next = Node; }

通过while循环找到链表的尾处，将节点插入进即可。

3.完整代码

package com.dazuizui.linkedlist; /** * 链表 */ public class LinkedList { public static void main(String[] args) { LinkedAdmin linkedAdmin = new LinkedAdmin(); linkedAdmin.putNode(new LinkedDate(0,"123")); linkedAdmin.putNode(new LinkedDate(5,"123")); linkedAdmin.putNode(new LinkedDate(4,"123")); linkedAdmin.putNode(new LinkedDate(10,"123")); linkedAdmin.showList(); linkedAdmin.deleteNode(5); System.out.println(); linkedAdmin.updateNode(new LinkedDate(0,"1243")); linkedAdmin.showList(); linkedAdmin.foodput(new LinkedDate(100,"12787878783")); linkedAdmin.showList(); } } //控制链表 class LinkedAdmin{ //设置头节点 头节点一直不会动 private LinkedDate headNode = new LinkedDate(0,""); //添加元素 public void putNode(LinkedDate Node){ //创建临时变量 指向链表位置使用 LinkedDate temp = headNode; while(true){ //如果链表为Null if (temp.next == null){ break; } //查找薪数据属于链表的某个位置 if (temp.on > Node.on){ break; } //指针移动 temp = temp.next; } //添加到链表中 Node.next = temp.next; temp.next = Node; System.out.println("tianj"); } //浏览链表 public void showList(){ //创建临时变量 指向节点位置使用 // headNode.next 头节点的下一个节点，因为头节点的任务只是指向第一个存放数据的链表 LinkedDate temp = headNode.next; while(true){ //如果当前为NULL要不就是到了尾节点要不就是当前链表为NULL if (temp == null){ break; } System.out.println(temp); //指针下移动 指向下一个个元素 temp = temp.next; } } //删除元素 public void deleteNode(int id){ LinkedDate temp = headNode.next; while(true){ if (temp.on == id){ break; } //指针下移动 temp = temp.next; } temp.next = temp.next.next; } //修改数据 public void updateNode(LinkedDate Node){ LinkedDate temp = headNode.next; while(true){ if (temp == null){ System.out.println("没有此数据"); return; } //如果on相等进行修改t if (temp.on == Node.on){ temp.data = Node.data; return; } temp = temp.next; } } //尾添加 public void foodput(LinkedDate Node){ LinkedDate temp = headNode; while (true){ //如果满足就代表已经到了列表尾 if (temp.next == null){ break; } //指针下移动 temp = temp.next; } temp.next = Node; } } //链表中的元素 class LinkedDate{ int on; String data; @Override public String toString() { return "LinkedDate{" + "on=" + on + ", data='" + data + '\'' + '}'; } public LinkedDate(int on, String data) { this.on = on; this.data = data; } LinkedDate next; }