【大厂算法系列】链表实战篇，基于链表编码实现课程信息管理系统

• 前面我们使用顺序储存结构实现的顺序表，虽然查询的时候很快，同时也存在一些问题。
• 问题1：在进行元素的增加或者删除的时候:比较麻烦，需要你去移动大量的元素把数据删除或者增加。
• 问题2：查找速度快，但是插入速率低

- 链表

• 链表里的数据是以结点方式来表示的，每一个结点的组成是由：元素+指针来组成的，元素就是存储数据里的存储单元，指针就是用来连接每一个结点的地址数据。这个以结点的序列来表示线性表被称作为单链表
• 单链表是一种链式储存结构。在物理储存单元不连续，非顺序。
  • 结点里的数据域是用来存储数据元素的
  • 指针是用于指向下一个具有相同结构的结点
  • 因为只有一个指针结点，故而被称为单链表。

- 单向链表

• 单向链表是链表中的其中一种，它是由多个结点组成的，每一个结点都是有一个数据域+指针域组成。
• 数据域是用来存储数据元素的，指针用来指向后面的节点
• 链表分成带头结点的链表跟不带头结点的链表。
• 单链表的头节点里不储存数据，它的指针指向真正存储有数据的第一个链表节点。
• 带头结点的单链表演示

- 链表储存地址

单向链表的增加与遍历节点演示

• 需要实现的方法

- 单向链表的增加与遍历

• 增加

• 遍历输出

public void addCourse(CourseNode node){
         //辅助的指针
        CourseNode cur=head;
        //不断的遍历链表 找到最后一个节点
        while (true){
            //找到了
            if(cur.next==null){
                break;
            }
            //辅助指针往下移动
            cur=cur.next;
        }
        cur.next=node;
        length++;

    }
    //遍历输出课程
    public void showCourse(){
        //定义辅助的指针
        CourseNode cur=head;
        if(cur.next==null){
            System.out.println("链表空 不可以输出");
            return;
        }
        while (true){
            if(cur.next==null){
                System.out.println("课程输出完成");
                return;
            }
            System.out.println(cur.next);
            cur=cur.next;
        }
    }

链表之单向链表实现删除与修改节点

• 单链表删除节点示意图

- 单链表修改节点

 //修改课程信息
    public void update(CourseNode node){
        CourseNode cur=head;
        boolean flag=false;
        while (cur.next!=null){
            if(cur.next.id==node.id){
                flag=true;
                break;
            }
            cur=cur.next;
        }
        if(flag){
            cur.next.id=node.id;
            cur.next.courseName=node.courseName;
        }else {
            System.out.println("没有找到要修改的课程");
        }
    }

链表实现查找倒数第K个课程

• 思路分析

public CourseNode getLastCourse(int k){
        CourseNode cur=head;
        if(cur.next==null){
            System.out.println("链表空 不可以返回");
            return null;
        }
        int length=getLength();
        if(k==0 || k>length){
            throw new IllegalArgumentException("参数错误");
        }
        System.out.println("链表长度:"+length);
        for(int i=0;i<length-k+1;i++){
        //for(int i=0;i<=length-k;i++){
            cur=cur.next;
        }
        return cur;
    }

链表进阶之实现双向链表的增加与遍历

• 什么是双向链表

• 双向链表也被称作为双向表，它和单向链表一样，属于链表的一种。

• 有多个结点来组成的，和单向链表不一样的是，它拥有两个指针域，一个指向后继的节点，另一个指向前驱结点。

• 链表的头结点的数据域是不存储数据的，所以，头结点的前驱指针域为null，它的后继指针域指的是第一个真正有数据存储的结点。

• 双向链表的增加和遍历

• 增加

• 遍历

//添加课程
    public void addCourse(CourseNode2 node){
        //辅助的指针
        CourseNode2 cur=head;
        //不断的遍历链表 找到最后一个节点
        while (true){
            //找到了
            if(cur.next==null){
                break;
            }
            //辅助指针往下移动
            cur=cur.next;
        }
        cur.next=node;
        node.pre=cur;
        length++;

    }

双向链表实战删除与修改课程

• 双向链表删除节点思路分析

• 双向链表修改课程信息（同单链表类似）

 //删除课程 根据课程的id
    public void delCourse(int id){
        //定义辅助变量
        CourseNode2 cur=head.next;
        if(cur==null){
            return;
        }
        //记录是否找到课程
        boolean flag=false;
        while (cur!=null){
            if(cur.id==id){
                flag=true;
                break;
            }
            //一直遍历
            cur=cur.next;
        }
        if(flag){
            //删除节点
            // data1 next->data3
            cur.pre.next=cur.next;
            //data3 pre->data1
            if(cur.next!=null){
                cur.next.pre=cur.pre;
            }
            length--;
        }else {
            System.out.printf("要删除的节点%d没有找到",id);
        }
    }

• 对单链表与双链表的相关操作进行时间复杂度分析

• 删除节点时

  • 单链表删除节点的时候，需要找到前驱节点，也就是通过遍历的方式得到。单链表的增删操作复杂度是O(n).
  • 双向链表删除节点的时候，因为是双向的，直接通过pre就可以得到前驱节点，不用进行遍历，时间复杂度是O(1)
  • 如果只知道要删除的双链表节点的序号，那一样要遍历，时间复杂度是O(n)

• 插入节点时

  • 单链表与双链表的插入都要找到前驱节点，需要遍历找到的话时间复杂度就是O(n),给了前驱节点复杂度就是O(1)

• 查找节点时

  • 查找时，时间复杂度均为O(n)

• 总体代码

• 单链表：

public class SingleLinkeDemo {
    public static void main(String[] args) {
        CourseLinke courseLinke = new CourseLinke();
        CourseNode node1 = new CourseNode(1, "数据结构与算法");
        CourseNode node2 = new CourseNode(2, "数据结构与算法");
        CourseNode node3 = new CourseNode(3, "数据结构与算法");
        CourseNode node4 = new CourseNode(4, "数据结构与算法");
        CourseNode node5 = new CourseNode(5, "数据结构与算法");
        courseLinke.addCourse(node1);
        courseLinke.addCourse(node2);
        courseLinke.addCourse(node3);
        courseLinke.addCourse(node4);
        courseLinke.showCourse();
//        System.out.println("   ====   ");
//        courseLinke.delCourse(1);
//        System.out.println("删除课程id=1的课程后");
//        courseLinke.showCourse();
//        System.out.println("==修改信息后==");
//        courseLinke.update(node4);
//        courseLinke.showCourse();
        courseLinke.addNodeIndex(3,node5);
        System.out.println("  ====  ");
        System.out.println("倒数第1门课程的信息是："+courseLinke.getLastCourse(1));
        courseLinke.showCourse();
    }
}
//链表类  管理课程
class CourseLinke{
    //头节点 初始化
    public CourseNode head=new CourseNode(0,"");
    //链表有效元素个数
    private int length=0;
    //添加课程
    public void addCourse(CourseNode node){
         //辅助的指针
        CourseNode cur=head;
        //不断的遍历链表 找到最后一个节点
        while (true){
            //找到了
            if(cur.next==null){
                break;
            }
            //辅助指针往下移动
            cur=cur.next;
        }
        cur.next=node;
        length++;

    }
    //指定位置插入  index=2,即在第二个元素之前插入
    public void addNodeIndex(int index,CourseNode node){
        //辅助指针
        CourseNode cur=head;
        //判断参数是否合法
        if(index>length || index<0) return;
        for(int i=1;i<index;i++){
            cur=cur.next;
        }
        System.out.println("当前cur"+cur);
        CourseNode temp=cur.next;
        cur.next=node;
        node.next=temp;
    }
    //修改课程信息
    public void update(CourseNode node){
        CourseNode cur=head;
        boolean flag=false;
        while (cur.next!=null){
            if(cur.next.id==node.id){
                flag=true;
                break;
            }
            cur=cur.next;
        }
        if(flag){
            cur.next.id=node.id;
            cur.next.courseName=node.courseName;
        }else {
            System.out.println("没有找到要修改的课程");
        }
    }
    //删除课程 根据课程的id
    public void delCourse(int id){
        //定义辅助变量
        CourseNode cur=head;
        if(cur.next==null){
            return;
        }
        //记录是否找到课程
        boolean flag=false;
        while (cur.next!=null){
            if(cur.next.id==id){
                flag=true;
                break;
            }
            //一直遍历
            cur=cur.next;
        }
        if(flag){
            //删除节点
            cur.next=cur.next.next;
            length--;
        }else {
            System.out.printf("要删除的节点%d没有找到",id);
        }
    }
    //遍历输出课程
    public void showCourse(){
        //定义辅助的指针
        CourseNode cur=head;
        if(cur.next==null){
            System.out.println("链表空 不可以输出");
            return;
        }
        while (true){
            if(cur.next==null){
                System.out.println("课程输出完成");
                return;
            }
            System.out.println(cur.next);
            cur=cur.next;
        }
    }
    //获取倒数第K个节点  1.获取到链表长度  2.遍历链表直到（链表长度-K+1） return node
    public CourseNode getLastCourse(int k){
        CourseNode cur=head;
        if(cur.next==null){
            System.out.println("链表空 不可以返回");
            return null;
        }
        int length=getLength();
        if(k==0 || k>length){
            throw new IllegalArgumentException("参数错误");
        }
        System.out.println("链表长度:"+length);
        for(int i=0;i<length-k+1;i++){
            cur=cur.next;
        }
        return cur;
    }
    //获取链表长度
    public int getLength(){
        return length;
    }
}
class CourseNode{
    public int id;
    public String courseName;
    public CourseNode next;
    public CourseNode(int id,String courseName){
        this.id=id;
        this.courseName=courseName;
    }

    @Override
    public String toString() {
        return "CourseNode{" +
                "id=" + id +
                ", courseName='" + courseName + '\'' +
                ", next=" + next +
                '}';
    }
}

双链表

public class DoubleLinkeDemo {
    public static void main(String[] args) {
        DoubleLinke doubleLinke = new DoubleLinke();
        CourseNode2 node1 = new CourseNode2(1, "数据结构与算法课程1");
        CourseNode2 node2 = new CourseNode2(2, "数据结构与算法课程1");
        CourseNode2 node3 = new CourseNode2(3, "数据结构与算法课程1");
        CourseNode2 node4 = new CourseNode2(3, "数据结构与算法课程5");
        doubleLinke.addCourse(node1);
        doubleLinke.addCourse(node2);
        doubleLinke.addCourse(node3);
        doubleLinke.delCourse(1);
        doubleLinke.update(node4);
        doubleLinke.showCourse();
    }
}

//链表类  管理课程
class DoubleLinke{
    //头节点 初始化
    public CourseNode2 head=new CourseNode2(0,"");
    //链表有效元素个数
    private int length=0;
    //添加课程
    public void addCourse(CourseNode2 node){
        //辅助的指针
        CourseNode2 cur=head;
        //不断的遍历链表 找到最后一个节点
        while (true){
            //找到了
            if(cur.next==null){
                break;
            }
            //辅助指针往下移动
            cur=cur.next;
        }
        cur.next=node;
        node.pre=cur;
        length++;

    }
    //修改课程信息
    public void update(CourseNode2 node){
        CourseNode2 cur=head;
        boolean flag=false;
        while (cur.next!=null){
            if(cur.next.id==node.id){
                flag=true;
                break;
            }
            cur=cur.next;
        }
        if(flag){
            cur.next.id=node.id;
            cur.next.courseName=node.courseName;
        }else {
            System.out.println("没有找到要修改的课程");
        }
    }
    //删除课程 根据课程的id
    public void delCourse(int id){
        //定义辅助变量
        CourseNode2 cur=head.next;
        if(cur==null){
            return;
        }
        //记录是否找到课程
        boolean flag=false;
        while (cur!=null){
            if(cur.id==id){
                flag=true;
                break;
            }
            //一直遍历
            cur=cur.next;
        }
        if(flag){
            //删除节点
            // data1 next->data3
            cur.pre.next=cur.next;
            //data3 pre->data1
            if(cur.next!=null){
                cur.next.pre=cur.pre;
            }
            length--;
        }else {
            System.out.printf("要删除的节点%d没有找到",id);
        }
    }
    //遍历输出课程
    public void showCourse(){
        //定义辅助的指针
        CourseNode2 cur=head;
        if(cur.next==null){
            System.out.println("链表空 不可以输出");
            return;
        }
        while (true){
            if(cur.next==null){
                System.out.println("课程输出完成");
                return;
            }
            System.out.println(cur.next);
            cur=cur.next;
        }
    }
    //获取倒数第K个节点  1.获取到链表长度  2.遍历链表直到（链表长度-K） return node
    public CourseNode2 getLastCourse(int k){
        CourseNode2 cur=head;
        if(cur.next==null){
            System.out.println("链表空 不可以返回");
            return null;
        }
        int length=getLength();
        for(int i=0;i<length-k;i++){
            cur=cur.next;
        }
        return cur;
    }
    //获取链表长度
    public int getLength(){
        return length;
    }
}

class CourseNode2{
    public int id;
    public String courseName;
    public CourseNode2 next;
    //前驱节点
    public CourseNode2 pre;
    public CourseNode2(int id,String courseName){
        this.id=id;
        this.courseName=courseName;
    }
//    这两个方法都会尝试在它们的邻居上调用toString()，包括你开始时使用的Node。这是一个无限递归。
//    要避免这种情况，请不要在节点的toString()方法中包含相邻节点的字符串表示。
    @Override
    public String toString() {
        return  "课程id=" + id +
                ", courseName='" + courseName + '\'' +
                ", next=" + next +
                '}';
    }
}

专栏地址：【大厂算法系列】
专栏内容： 数组，列表，栈，队列，树，哈希表，字符串，堆，查找，排序，DFS,BFS，回溯，贪心，动态规划等+力扣大厂真题
算法交流： V 【yopa66】