JAVA数据结构-3.链表

JAVA数据结构-单链表

• 链表(Link list)是以节点的方式来存储,各个节点不一定是连续存放的
• 每个节点包含data域,next域,指向下一个节点
• 链表分带头节点的链表和没有头节点的链表,根据实际需求来确定

链表在内存中的存储情况:

链表(带头节点)的逻辑结构:

​ head节点不存放具体的数据,作用就是表示单链表的头和指向第一个数据节点的指针next

单链表的结构

定义一个节点类,每一个类对象就是一个数据节点

• 每个数据节点包含自己的数据域data和指向下一个对象的指针域next

//每一个数据节点就是一个music对象
class Music{
    public int no;
    public String name;
    public Music next;   //指向下一个节点

    public Music(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Music{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

定义一个单链表,管理歌单节点对象

• 单链表创建时先创建一个头节点.

//定义SingleLinkedList 管理歌单
class SingnleLinkList{
    //先创建一个头节点,头节点不能动  头节点不保存数据
    private Music head = new Music(0,"");

    //添加元素(最后的位置)
    public void add(Music musicNode){
        //1.遍历找到节点最后的位置 (因为头节点不能动,所以需要创建一个临时变量temp,指向头节点)
        //2插入节点
    }

    //遍历输出节点
    public void showList(){
        //1.判断链表是否为空
        //2.遍历每个节点并输出 (临时变量temp)
    }
    
    //....操作函数

}

单链表的操作

​ 由于是单向链表,所以只能从前往后进行遍历查找,因此单链表的多种操作都需要找当预操作节点的前一个节点.

1.添加(创建元素): 找前节点

1. 先创建一个head头节点,表示单链表的头部;
2. 创建一个数据节点,将head的指针域next指向该元素;
3. 后面每创建一个数据节点,就直接加入到链表的最后位置,将上一个节点的next指针域指向该元素;

//添加元素(最后的位置)
public void add(Music musicNode){
    //1.遍历找到节点最后的位置 (因为头节点不能动,所以需要创建一个临时变量temp,指向头节点)
    Music temp = head;
    while(temp.next != null){
        temp=temp.next; //若temp的后一个节点存在,则后移一位
    }
    //循环结束后,temp已经指向最后一个节点
    //2插入节点
    temp.next = musicNode;
}

2.遍历:

1. 通过一个辅助变量,帮助遍历整个单链表

//遍历输出节点
public void showList(){
    //1.判断链表是否为空
    if(head.next == null ){
        System.out.println("链表为空");
        return ;
    }
    //遍历每个节点并输出 (临时变量temp)
    Music temp = head.next;
    while (temp != null){
        System.out.println(temp);
        temp=temp.next;
    }
}

3.插入数据节点: 找前节点

1. 使用临时变量temp,遍历到需要插入节点的位置的前一个节点front;

2. 将待插入节点的next域指向temp的后一个节点rear,

   node.next=temp.next(rear);

3. 将front的next指针域指向新节点node;

   (front.next)temp.next=node

//插入节点1(index)  第一个元素下标为1
public void insert(Music musicNode, int index){
    //1.遍历,使temp指向到待插入位置的前一个节点
    Music temp = head;
    while ((index-1) != 0){
        temp = temp.next;
        index --;
    }
    //2.插入
    musicNode.next = temp.next;
    temp.next = musicNode;
}

//插入节点2(通过no按顺序插入)
public void insertOrderByNo(Music musicNode){
    //1.遍历,使temp指向到待插入位置的前一个节点
    boolean flag = false; //判断节点是否存在
    Music temp = head;
    while (temp.next != null){
        if(temp.next.no > musicNode.no){ //找到位置,在temp的后方插入
            break;
        }
        if(temp.next.no == musicNode.no){  //节点已经存在,返回标识
            flag = true;
            break;
        }
        temp = temp.next;
    }
    //2.插入
    if(flag){
        System.out.println("编号存在不能添加"+musicNode.no);
        return ;
    }
    //正确插入
    musicNode.next = temp.next;
    temp.next = musicNode;
}

4.修改节点信息: 找本节点

• 遍历节点,使临时temp指向待修改节点,
• 修改节点数据

//根据节点no值进行修改
    public void updata(Music musicNode){
        if(head.next == null){
            System.out.println("修改失败,链表节点为空");
            return ;
        }
        //遍历到待修改节点
        Music temp = head.next;
        boolean flag = false;
        while(true){
            if(temp.next == null){
                System.out.println("没有找到指定节点");
                break;
            }
            if(temp.no == musicNode.no){//找到节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //修改节点信息
        if(flag){
            temp.name = musicNode.name;
        }
    }

5.删除节点: 找前节点

• 由于是单向链表,所以只能从前往后进行遍历查找,而删除需要同时得到待删除节点的前和后两个节点,因此需要遍历使temp指向前节点before,后节点after通过前节点获得(before.next.next)

• 将前节点before的next指针指向后节点;

  before.next = before.next.next(after)

//删除某一个节点 (no)
public void delete(Music musicNode){
    //遍历遭到待删除节点的上一个节点
    Music temp = head;
    boolean flag = false;
    while (true){
        if(temp.next == null){
            System.out.println("没有找到指定节点");
            break;
        }
        if(temp.next.no == musicNode.no){ //找到指定节点的前一个节点
            flag = true;
            break;
        }
        temp = temp.next;
    }
    //删除
    if(flag){
        Music after = temp.next.next;
        temp.next = after;
    }
}

附:操作完整测试代码

public class SingleLinkedList {
    public  static void main(String args[]){
        //创建数据节点
        Music music1 = new Music(1, "墙上的向日葵");
        Music music2 = new Music(6, "和你在一起");
        Music music3 = new Music(7, "你离开了南京,从此没有人跟我说话");

        //创建链表
        SingnleLinkList list = new SingnleLinkList();
        list.add(music1);
        list.add(music2);
        list.add(music3);
        list.showList();

        list.insert(new Music(4, "这个世界会好码"),2);
        list.showList();

        list.insertOrderByNo(new Music(2, "结婚"));
        list.showList();

        list.updata(new Music(6,"热歌"));
        list.showList();

        list.delete(new Music(9,""));
        list.showList();

    }
}

//定义SingleLinkedList 管理歌单
class SingnleLinkList{
    //先创建一个头节点,头节点不能动  头节点不保存数据
    private Music head = new Music(0,"");

    //添加元素(最后的位置)
    public void add(Music musicNode){
        //1.遍历找到节点最后的位置 (因为头节点不能动,所以需要创建一个临时变量temp,指向头节点)
        Music temp = head;
        while(temp.next != null){
            temp=temp.next; //若temp的后一个节点存在,则后移一位
        }
        //循环结束后,temp已经指向最后一个节点
        //2插入节点
        temp.next = musicNode;
    }
    //插入节点(index)  第一个元素下标为1
    public void insert(Music musicNode, int index){
        //1.遍历,使temp指向到待插入位置的前一个节点
        Music temp = head;
        while ((index-1) != 0){
            temp = temp.next;
            index --;
        }
        //2.插入
        musicNode.next = temp.next;
        temp.next = musicNode;
    }

    //插入节点(通过no按顺序插入)
    public void insertOrderByNo(Music musicNode){
        //1.遍历,使temp指向到待插入位置的前一个节点
        boolean flag = false; //判断节点是否存在
        Music temp = head;
        while (temp.next != null){
            if(temp.next.no > musicNode.no){ //找到位置,在temp的后方插入
                break;
            }
            if(temp.next.no == musicNode.no){  //节点已经存在,返回标识
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //2.插入
        if(flag){
            System.out.println("编号存在不能添加"+musicNode.no);
            return ;
        }
        //正确插入
        musicNode.next = temp.next;
        temp.next = musicNode;
    }

    //根据节点no值进行修改
    public void updata(Music musicNode){
        if(head.next == null){
            System.out.println("修改失败,链表节点为空");
            return ;
        }
        //遍历到待修改节点
        Music temp = head.next;
        boolean flag = false;
        while(true){
            if(temp.next == null){
                System.out.println("没有找到指定节点");
                break;
            }
            if(temp.no == musicNode.no){//找到节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //修改节点信息
        if(flag){
            temp.name = musicNode.name;
        }
    }

    //删除某一个节点 (no)
    public void delete(Music musicNode){
        //遍历遭到待删除节点的上一个节点
        Music temp = head;
        boolean flag = false;
        while (true){
            if(temp.next == null){
                System.out.println("没有找到指定节点");
                break;
            }
            if(temp.next.no == musicNode.no){ //找到指定节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //删除
        if(flag){
            Music after = temp.next.next;
            temp.next = after;
        }
    }

    //遍历输出节点
    public void showList(){
        //1.判断链表是否为空
        if(head.next == null ){
            System.out.println("链表为空");
            return ;
        }
        //遍历每个节点并输出 (临时变量temp)
        Music temp = head.next;
        while (temp != null){
            System.out.println(temp);
            temp=temp.next;
        }
    }

}

//每一个数据节点就是一个music对象
class Music{
    public int no;
    public String name;
    public Music next;   //指向下一个节点

    public Music(int no, String name) {
        this.no = no;
        this.name = name;
   de
    public String toString() {
        return "Music{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}

单链表 算法题

JAVA数据结构-链表算法题
21. 合并两个有序链表
剑指 Offer 22. 链表中倒数第k个节点
剑指 Offer 06. 从尾到头打印链表
剑指 Offer 24. 反转链表