数据结构链表（4）

水深无声 2022-11-24 14:17 139阅读 0赞

### 链表（Linked List） ###

#### 1、数组的特点 ####

内存地址连续

#### 2、数组优缺点 ####

优点：数据是存放在一个连续的内存地址上，查找效率比较高

缺点：在改变数据个数的时如：增加，插入，删除效率比较低

#### 3、链表 ####

数据在内存中可以在任意位置，通过引用来关联数据

#### 4、链表优缺点 ####

优点：

*  任意位置插入元素和删除元素的速度快，时间复杂度为O(1)
 *  内存利用率高，不会浪费内存
 *  链表的空间大小不固定，可以动态拓展

缺点：

随机访问效率低，时间复杂度为0(N)。（需要从第一个数据开始找起，依次往后遍历）

#### 5、小结 ####

*  链表是以将节点方式来存储，链式存储
 *  每个节点包含data域，next域：指向下一个节点
 *  链表的各个节点不一定是连续存储的
 *  链表分带头节点的链表和没有带头节点的链表

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pKY6Gzr8-1596697272780)(/Users/dimitri/Library/Application Support/typora-user-images/image-20200727221835239.png)\]

#### 6、链表基本操作 ####

> （1）添加节点、（2）修改节点、（3）删除节点、（4）显示节点

（1）添加节点

void insert(HeroNode5 heroNode5){ 
        HeroNode5 temp = head;//因为头节点不能动，则需一个辅助节点
        while (true){ 
            if (temp.next == null){ //如果temp.next==null，说明是链表的最后
                break;
            }
            //当temp.next不为null时，就将temp往后移
            temp = temp.next;
        }
        //当退出while时，说明temp指向链表的最后
        //然后将最后节点连接新的节点heroNode5就可以了
        temp.next = heroNode5;
    }

（2）修改节点

//2、修改/更新
    //根据ID来修改，ID不能修改
    void update(HeroNode5 newHeroNode5){ 
        //首先找到需要修改的节点
        HeroNode5 temp = head.next;
        boolean flag = false;//找到时flag = true
        while (true){ 
            if (temp == null){ 
                System.out.println("链表为空");
                break;//遍历结束
            } else if (temp.no == newHeroNode5.no){ //说明找到需要修改的节点，则flag=true，直接退出然后执行if(flag){...}
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){ //根据上述条件，如果flag=true，说明找到
            temp.name = newHeroNode5.name;
        }else { 
            System.out.printf("没有找到编号%d节点，不能修改\n",newHeroNode5.no);
        }
    }

（3）删除节点

//3、删除节点
    void dle(int no){ 
        if (head.next == null){ 
            System.out.println("链表为空");
            return;
        }
        HeroNode5 cur = head;
        boolean flag = false;
        while (true){ 
            if (cur.next == null){ 
                break;
            }
            if (cur.next.no == no){ //说明找到了要删除的节点
                flag = true;//找到需要删除的节点时flag为true
                break;
            }
            cur = cur.next;
        }
        if (flag){ 
            cur.next = cur.next.next;
        }else { 
            System.out.printf("要删除的%d节点不存在\n",no);
        }
    }

（4）显示节点

//4、显示链表
    void list(){ 
        if (head.next == null){ 
            System.out.println("该链表为空");
            return;
        }
        //如果链表不为空，则遍历出来，需要辅助节点协助遍历
        HeroNode5 tamp = head.next;
        while (tamp != null){ 
            System.out.println(tamp);
            tamp = tamp.next;//然后将temp后移
        }
    }

#### 7、完整代码实现 ####

public class SingLeLinkedList5 { 
        public static void main(String[] args) { 
            HeroNode5 hero1 = new HeroNode5(1,"aaa");
            HeroNode5 hero2 = new HeroNode5(2,"bbb");
            HeroNode5 hero3 = new HeroNode5(3,"ccc");
            HeroNode5 hero4 = new HeroNode5(4,"ddd");
            HeroNode5 hero5 = new HeroNode5(5,"eee");
            SingLeLinked singLeLinked = new SingLeLinked();
            singLeLinked.insert(hero1);
            singLeLinked.insert(hero2);
            singLeLinked.insert(hero3);
            singLeLinked.insert(hero4);
            singLeLinked.insert(hero5);
            singLeLinked.list();
            System.out.println("修改后～");
            HeroNode5 newhero5 = new HeroNode5(5,"MarkJava");
            singLeLinked.update(newhero5);
            singLeLinked.list();
            System.out.println("删除节点");
            singLeLinked.dle(50);
            singLeLinked.list();
        }
    }
    //链表类
    class SingLeLinked{ 
        //初始化头节点
        HeroNode5 head = new HeroNode5(0,null);
        //1、添加节点（尾插法）
        void insert(HeroNode5 heroNode5){ 
            HeroNode5 temp = head;//因为头节点不能动，则需一个辅助节点
            while (true){ 
                if (temp.next == null){ //如果temp.next==null，说明是链表的最后
                    break;
                }
                //当temp.next不为null时，就将temp往后移
                temp = temp.next;
            }
            //当退出while时，说明temp指向链表的最后
            //然后将最后节点连接新的节点heroNode5就可以了
            temp.next = heroNode5;
        }
        //2、修改/更新
        //根据ID来修改，ID不能修改
        void update(HeroNode5 newHeroNode5){ 
            //首先找到需要修改的节点
            HeroNode5 temp = head.next;
            boolean flag = false;//找到时flag = true
            while (true){ 
                if (temp == null){ 
                    System.out.println("链表为空");
                    break;//遍历结束
                } else if (temp.no == newHeroNode5.no){ //说明找到需要修改的节点，则flag=true，直接退出然后执行if(flag){...}
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag){ //根据上述条件，如果flag=true，说明找到
                temp.name = newHeroNode5.name;
            }else { 
                System.out.printf("没有找到编号%d节点，不能修改\n",newHeroNode5.no);
            }
        }
        //3、删除节点
        void dle(int no){ 
            if (head.next == null){ 
                System.out.println("链表为空");
                return;
            }
            HeroNode5 cur = head;
            boolean flag = false;
            while (true){ 
                if (cur.next == null){ 
                    break;
                }
                if (cur.next.no == no){ //说明找到了要删除的节点
                    flag = true;//找到需要删除的节点时flag为true
                    break;
                }
                cur = cur.next;
            }
            if (flag){ 
                cur.next = cur.next.next;
            }else { 
                System.out.printf("要删除的%d节点不存在\n",no);
            }
        }
        //4、显示链表
        void list(){ 
            if (head.next == null){ 
                System.out.println("该链表为空");
                return;
            }
            //如果链表不为空，则遍历出来，需要辅助节点协助遍历
            HeroNode5 tamp = head.next;
            while (tamp != null){ 
                System.out.println(tamp);
                tamp = tamp.next;//然后将temp后移
            }
        }
    }
    //节点类
    class HeroNode5{ 
        int no;
        String name;
        HeroNode5 next;
    
        public HeroNode5(int no, String name) { 
            this.no = no;
            this.name = name;
        }
        @Override
        public String toString() { 
            return "HeroNode5{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3JlYWxpemVfZHJlYW0_size_16_color_FFFFFF_t_70]: /images/20221124/d138984acb044bbf8b0b4fe3117e5c6b.png