首页 / 算法 / 数据结构与算法-单向链表
数据结构与算法-单向链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法-单向链表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4660字,纯文字阅读大概需要7分钟。
内容图文
![数据结构与算法-单向链表](/upload/InfoBanner/zyjiaocheng/615/2ba09c4f26c24ac89e0ea6517445c535.jpg)
一、链表
1、链表是以节点的方式存储的,是链式存储
2、每个节点包含data域和指向下一个节点的next域
3、链表分带头节点的链表和不带头节点动的链表,根据实际需求来确定
二、应用场景
游戏排行榜
三、思路分析
- 添加节点
由于head不能改动,定义一个临时变量temp,遍历链表,找到最后一个节点,将最后一个节点的next指向新节点 - 根据顺序添加节点
由于head不能改动,定义一个临时变量temp,遍历链表,找到no比新节点heroNode.no大的前一个节点temp,heroNode.next = temp.next,temp.next = heroNode; - 更新指定节点
由于head不能改动,定义一个临时变量temp,遍历链表,找到指定的节点,并更新相关数据 - 删除指定节点
由于head不能改动,定义一个临时变量temp,遍历链表,找到指定节点的前一个节点temp,并将前一个节点的temp.next指向temp.next.next
四、代码实现
//节点数据结构(Data+Next)
class HeroNode{
public int no;
public String name;
public String nickName;
public HeroNode next;
public HeroNode(int no,String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
}
}
public class SingleLinkedList{
//头节点
private HeroNode head = new HeroNode(0, "", "");
//添加节点
public void addNode(HeroNode heroNode) {
HeroNode temp = head;
while(true) {
//找到最后一个节点
if (temp.next == null) {
break;
}
//后移
temp = temp.next;
}
//将最后一个节点的next指向新节点
temp.next = heroNode;
}
//根据顺序加入节点
public void addByOrder(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no > heroNode.no) {
break;
} else if (temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
System.out.printf("准备插入的英雄编号%d已经存在\n", heroNode.no);
} else {
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//遍历链表
public void list() {
if (head.next == null) {
System.out.println("链表为空");
return ;
}
HeroNode temp = head.next;
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.next;
}
}
//更新指定节点
public void update(HeroNode heroNode) {
if (head.next == null) {
System.out.println("链表为空");
return ;
}
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;
}
if (temp.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
} else {
System.out.printf("没有找到编号%d的节点", heroNode.no);
}
}
//删除指定的节点,不再指向指定节点即可
public void detele(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.printf("要删除的编号为%d的节点不存在", heroNode.no);
}
}
//根据头节点获取链表长度
public static int size(HeroNode head) {
if (head.next == null) {
return 0;
}
int size = 0;
HeroNode cur = head.next;
while (cur !=null) {
size++;
cur = cur.next;
}
return size;
}
//得到头节点
public HeroNode getHead() {
return head;
}
//设置头节点
public void setHead(HeroNode head) {
this.head = head;
}
public static HeroNode findLastIndexNode(HeroNode head, int index) {
if (head == null) {
return null;
}
int size = size(head);
if (index <= 0 || index > size) {
return null;
}
HeroNode cur = head.next;
for (int i=0; i<size-index; i++) {
cur = cur.next;
}
return cur;
}
public static void reversePrint(HeroNode head) {
if (head.next == null) {
return;
}
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode cur = head.next;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
public static void reverseList(HeroNode head) {
if (head.next==null || head.next.next==null) {
return;
}
HeroNode cur = head.next;
HeroNode next = null;
HeroNode reverseHead = new HeroNode(0, null, null);
while (cur != null) {
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
head.next = reverseHead.next;
}
public static void main(String[] args) {
HeroNode hero1 = new HeroNode(1,"松江", "及时雨");
HeroNode hero2 = new HeroNode(2,"卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3,"吴用", "智多星");
HeroNode hero4 = new HeroNode(4,"林冲", "豹子头");
SingleLinkedList list = new SingleLinkedList();
list.addNode(hero1);
list.addNode(hero4);
list.addNode(hero3);
list.addNode(hero2);
// list.addByOrder(hero1);
// list.addByOrder(hero4);
// list.addByOrder(hero3);
// list.addByOrder(hero2);
list.list();
list.update(new HeroNode(2,"卢俊义","小玉"));
list.list();
// list.detele(new HeroNode(2,"卢俊义","小玉"));
// list.list();
System.out.println(size(list.getHead()));
// System.out.println(findLastIndexNode(list.getHead(), 2));
// reverseList(list.getHead());
// list.list();
reversePrint(list.getHead());
}
}
内容总结
以上是互联网集市为您收集整理的数据结构与算法-单向链表全部内容,希望文章能够帮你解决数据结构与算法-单向链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。