Java单链表

我会带着你远行 2021-11-16 11:32 262阅读 0赞

## 一、概述 ##

![1007094-20190727121929950-552348322.png][]

## 二、主方法 ##

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     }

## 五、打印显示 ##

![1007094-20190727123415212-1170402204.png][]

[1007094-20190727121929950-552348322.png]: /images/20211116/688a5ffff3b947caa0c177b86c3f57c2.png
[1007094-20190727123415212-1170402204.png]: /images/20211116/6190b29a99be49a1bf94ffa9b6c26a1b.png