Java单链表

发布时间：2020-12-15 05:35:30 所属栏目：Java 来源：网络整理

导读：一、概述二、主方法 1 // 创建头结点 2 private HeroNode head = new HeroNode(-1, null , null ); 3 // 计数器，用于id的自增 4 private static int count=0; ? 1 @Test 2 public void test(){ 3 // 1.0插入节点 4 insertNode( new HeroNode(++count,"亚瑟

一、概述

二、主方法

1  //创建头结点
2     private HeroNode head = new HeroNode(-1,null,null); 3     //计数器，用于id的自增
4     private  static  int count=0;

 1     @Test
 2     public void test(){
 3         //1.0插入节点
 4         insertNode(new HeroNode(++count,"亚瑟","坦克"));
 5         insertNode(new HeroNode(++count,"甄姬","法师"));
 6         insertNode(new HeroNode(++count,"后裔","射手"));
 7         insertNode(new HeroNode(++count,"赵云","刺客"));
 8         //2.0打印链表
 9         printLinked();
10 
11         //3.0根据id删除节点
12         //deleteNode(2);
13 
14         //4.0更新数据，根据id
15         //updateData(new HeroNode(2,"诸葛亮","法师"));
16 
17         //5.0根据id查找英雄
18         //findData(2);
19 
20         //6.0查找链表的节点个数（有效的）
21         //System.out.println(getLength());
22 
23         //7.0利用栈stack（）反转链表
24         //reverseLinkedStack();
25 
26         //8.0反转链表
27         //reverseLinked();
28 
29         //9.0找倒数第k个节点
30         System.out.println(show( findLastIndexNode(2)));
31         //printLinked();
32     }

二、节点类　　

 1 class HeroNode{
 2     //值域
 3     private int id;
 4     private String name;
 5     private  String nickName;
 6 
 7     //指针域
 8     private HeroNode next;
 9 
10     HeroNode(int id,String name,String nickName) {
11         this.id = id;
12         this.name = name;
13         this.nickName = nickName;
14     }
15     /*    @Override
16         public String toString() {
17             return "HeroNode{" +
18                     "id=" + id +
19                     ",name=‘" + name + ‘‘‘ +
20                     ",nickName=‘" + nickName + ‘‘‘ +
21                     ",next=" + next +
22                     ‘}‘+"n";
23         }*/
24 
25     public int getId() {
26         return id;
27     }
28 
29     public void setId(int id) {
30         this.id = id;
31     }
32 
33     public String getName() {
34         return name;
35     }
36 
37     public void setName(String name) {
38         this.name = name;
39     }
40 
41     public String getNickName() {
42         return nickName;
43     }
44 
45     public void setNickName(String nickName) {
46         this.nickName = nickName;
47     }
48 
49     public HeroNode getNext() {
50         return next;
51     }
52 
53     public void setNext(HeroNode next) {
54         this.next = next;
55     }
56 
57 
58 }

三、基本功能实现

　　1、打印单个节点　

1  public String show(HeroNode h){
2         return "{" +
3                 "本节点id="+ h.toString().substring(h.toString().lastIndexOf(‘.‘)+1)+ ‘‘‘ +
4                 "id=" + h.getId() +
5                 ",name=‘" + h.getName() + ‘‘‘ +
6                 ",nickName=‘" + h.getNickName() + ‘‘‘ +
7                 ",next=" + h.getNext() + ‘‘‘ +
8                 ‘}‘+"n";
9     }

　　2、插入新节点

 1  //插入新节点
 2     public void insertNode(HeroNode newNode){
 3         if(head==null) {
 4             System.out.println("头结点不能为空");
 5             return;
 6         }
 7         if(newNode.getId()<1){
 8             System.out.println("请输入正确的编号");
 9             return;
10         }
11         HeroNode tmp = head;
12         while (tmp.getNext()!=null){
13             tmp=tmp.getNext();
14         }
15         tmp.setNext(newNode);
16     }

　　3、打印链表　

 1 public  void printLinked(){
 2         if(head==null) {
 3             System.out.println("头结点不能为空");
 4             return;
 5         }
 6         if(head.getNext()==null){
 7             System.out.println("只有头结点，链表无数据");
 8             return;
 9         }
10         HeroNode tmp = head;
11         System.out.println(head);
12         while (tmp.getNext()!=null){
13             System.out.println(show(tmp.getNext()));
14             tmp=tmp.getNext();
15         }
16     }

　　4、删除指定id节点

 1  //删除指定id节点
 2     public void deleteNode(int id){
 3         if(head==null) {
 4             System.out.println("头结点不能为空");
 5             return;
 6         }
 7         if(head.getNext()==null){
 8             System.out.println("只有头结点，链表无数据");
 9             return;
10         }
11         HeroNode tmp = head;
12         while (tmp.getNext()!=null){
13             if(tmp.getNext().getId()==id){
14                 tmp.setNext(tmp.getNext().getNext());
15                 return;
16 
17             }
18             tmp=tmp.getNext();
19         }
20         System.out.println("未找该英雄，请选择正确的编号id");
21     }

　　5、修改　　

 1 //修改指定id节点的内容
 2     public void updateData(HeroNode node){
 3         if(head==null) {
 4             System.out.println("头结点不能为空");
 5             return;
 6         }
 7         if(head.getNext()==null){
 8             System.out.println("只有头结点，链表无数据");
 9             return;
10         }
11         HeroNode tmp = head;
12         while (tmp.getNext()!=null){
13             if(tmp.getNext().getId()==node.getId()){
14                 //根据id更新节点内容，只需更新名字，id和next均不需更新
15                 tmp.getNext().setName(node.getName());
16                 tmp.getNext().setNickName(node.getNickName());
17                return;
18             }
19             tmp=tmp.getNext();
20         }
21         System.out.println("未找该英雄，请选择正确的编号id");
22     }

　　6、查找节点

 1  //查找节点数据
 2     public HeroNode findData(int id){
 3         if(head==null) {
 4             System.out.println("头结点不能为空");
 5             return null;
 6         }
 7         if(head.getNext()==null){
 8             System.out.println("只有头结点，链表无数据");
 9             return null;
10         }
11         HeroNode tmp = head;
12         while (tmp.getNext()!=null){
13             if(tmp.getNext().getId()==id){
14                 return tmp.getNext();
15             }
16             tmp=tmp.getNext();
17         }
18         System.out.println("未找该英雄，请选择正确的编号id");
19         return  null;
20     }

四、较难功能

　　1、单链表反转：方法1（不能只交换数据，节点随数据一起交换）

 1 //将单链表反转1
 2     public void reverseLinked(){
 3         if(head==null) {
 4             System.out.println("头结点不能为空");
 5             return ;
 6         }
 7         if(head.getNext()==null){
 8             System.out.println("只有头结点，链表无数据");
 9             return ;
10         }if(head.getNext().getNext()==null){
11             System.out.println("就一个节点，无法反转");
12             return ;
13         }
14         ////定义一个辅助的指针(变量)，帮助我们遍历原来的链表
15         HeroNode cur = head.getNext();
16         HeroNode next = null; //指向当前节点[cur]的下一个节点
17         HeroNode tmpHead = new HeroNode(-1,"","");
18         //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
19         while (cur!=null){
20             //先暂时保存当前节点的下一个节点，因为后面需要使用
21             next = cur.getNext();
22             //将当前节点的next设置为，tmpHead的下一个节点
23 
24             cur.setNext(tmpHead.getNext());
25             tmpHead.setNext(cur);
26             //节点后移
27             cur=next;
28         }
29         head.setNext(tmpHead.getNext());
30         printLinked();
31     }

　　2、单链表反转：方法2（不能只交换数据，节点随数据一起交换），利用stack（）栈的先进后出（FIFO）特性

 1 //将单链表反转2:stack()
 2     public void reverseLinkedStack(){
 3         Stack<HeroNode> stack = new Stack<>();
 4         if(head==null) {
 5             System.out.println("头结点不能为空");
 6             return ;
 7         }
 8         if(head.getNext()==null){
 9             System.out.println("只有头结点，链表无数据");
10             return ;
11         }
12         HeroNode tmp = head;
13         while (tmp.getNext()!=null){
14             stack.push(tmp.getNext());
15             tmp=tmp.getNext();
16         }
17         while(!stack.isEmpty()){
18             System.out.println(show(stack.pop()));
19         }
20     }

　　3、　查找单链表中的倒数第k个结点

 1 //查找单链表中的倒数第k个结点
 2     //1. 编写一个方法，接收head节点，同时接收一个index
 3     //2. index 表示是倒数第index个节点
 4     //3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
 5     //4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
 6     //5. 如果找到了，则返回该节点，否则返回nulll
 7     public  HeroNode findLastIndexNode(int k){
 8         if(head==null) {
 9             System.out.println("头结点不能为空");
10             return null;
11         }
12         if(head.getNext()==null){
13             System.out.println("只有头结点，链表无数据");
14             return null;
15         }
16         if(k<0 ||k >getLength()){
17             System.out.println("k节点不能小于0，或者大于链表节点数");
18             return null;
19         }
20         HeroNode tmp = head.getNext();
21         for (int i = 0; i < getLength()-k ; i++) {
22             tmp  = tmp.getNext();
23         }
24         return  tmp;
25     }

　　4、求链表有效节点个数

 1  //获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
 2     public int getLength(){
 3         int linkedLength=0;
 4         if(head==null) {
 5             System.out.println("头结点不能为空");
 6             return -1;
 7         }
 8         if(head.getNext()==null){
 9             System.out.println("只有头结点，链表无数据");
10             return 0;
11         }
12         HeroNode tmp = head;
13         while (tmp.getNext()!=null){
14             linkedLength++;
15             tmp=tmp.getNext();
16         }
17         return  linkedLength;
18     }

五、打印显示

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!