线性表 - 单向链表

链表介绍：

链表是以节点的方式链式存储的有序列表，链表中的每个节点在内存空间上不一定是连续的，可以利用内存空间中细小的不连续空间，内存使用率高，链表是动态分配内存的扩展灵活。

单向链表

单向链表在内存中的存储如下：

特点：
每个节点包括 data域 和 next域，next指向下一个节点的地址；
链表中的每个节点在内存空间上不一定是连续的。
链表分为带头节点的和不带头节点的，对于带头节点的链表，头节点不存放数据，只用于表示链表的开始。
带头节点的单向链表逻辑结构如下：

单向链表使用实例

一. 逻辑分析

1.新增

首先创建 head 头节点，之后每次增加节点都是在链表的最后面追加。
1）遍历找到链表的最后一个节点（next指针执行null 的节点）；
2）让最后一个节点的 next 指向待新增的节点；

2.带排序的新增

遍历链表，找到可以增加节点的正确位置，由于是单向链表，每个节点只有指向下一个节点的 next指针，因此需要找到插入位置的前一个节点。
1）遍历链表，找到插入位置的前一个节点；
2）让新增节点的 next 指向插入位置的后一个节点；
3）让插入位置的前一个节点的next 指向新增节点；

3.修改

找到需要修改的节点，直接修改

4.删除

找到要删除的节点，由于是单向链表，因此要找到被删除节点的前一个节点。
1）找到删除节点的前一个节点；
2）让删除位置的前一个节点的next 指向 删除节点的后一个节点；
3）被删除的节点不在被引用，会自动被垃圾回收机制回收；

5.查询

二. 代码实现

package linkedlist;

import org.junit.Test;

/**
 * 单项链表
 * @author
 * @create 2020-07-14 8:18 AM
 */
public class SingleLinkedListDemo {
    @Test
    public  void testAdd(){
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(new StudentPo(1,"zs"));
        singleLinkedList.add(new StudentPo(4,"zl"));
        singleLinkedList.add(new StudentPo(2,"ls"));
        singleLinkedList.add(new StudentPo(3,"ww"));

        singleLinkedList.showLinkedList();
    }

    @Test
    public  void testAddByOrder(){
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(new StudentPo(1,"zs"));
        singleLinkedList.addByOrder(new StudentPo(4,"zl"));
        singleLinkedList.addByOrder(new StudentPo(2,"ls"));
        singleLinkedList.addByOrder(new StudentPo(3,"ww"));
        singleLinkedList.showLinkedList();
    }

    @Test
    public  void testUpdate(){
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(new StudentPo(1,"zs"));
        singleLinkedList.addByOrder(new StudentPo(4,"zl"));
        singleLinkedList.addByOrder(new StudentPo(2,"ls"));
        singleLinkedList.addByOrder(new StudentPo(3,"ww"));
        System.out.println("修改前～～～");
        singleLinkedList.showLinkedList();

        singleLinkedList.update(new StudentPo(1,"张三"));
        System.out.println("修改后～～～");
        singleLinkedList.showLinkedList();
    }

    @Test
    public  void testDel(){
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(new StudentPo(1,"zs"));
        singleLinkedList.addByOrder(new StudentPo(4,"zl"));
        singleLinkedList.addByOrder(new StudentPo(2,"ls"));
        singleLinkedList.addByOrder(new StudentPo(3,"ww"));
        System.out.println("删除前～～～");
        singleLinkedList.showLinkedList();

        singleLinkedList.del(1);
        System.out.println("删除后～～～");
        singleLinkedList.showLinkedList();
    }

}


class SingleLinkedList{

    //创建头节点，头节点不存放任何数据，只用来表示链表的头部.在对链表的操作中，头部节点保持不动
   private StudentPo headNode = new StudentPo(0,"");


    /**
     * 向单向链表中添加元素
     * @param student 要添加的节点
     *
     * 分析：向单项链表中添加元素，就是在链表的尾部追加元素。
     * 1.从头开始找，找到链表的最后一个元素；
     * 2.让链表的最后一个元素的 next 指向要添加的节点；
     */
   public void add(StudentPo student){
       StudentPo temp = headNode;
       while(true){
           if(temp.next==null){
               break;
           }
           temp = temp.next;
       }
       temp.next=student;
   }

    /**
     * 向单向链表中按顺序添加元素
     * @param newStudent 要添加的节点
     * 需求：
     * 1）向当前单向链表中添加元素，按照sno从小到大的顺序添加
     * 2）如果当前链表中已经存在同一个 sno 的学生，则不能添加。
     *
     * 分析：
     * 1）按顺序添加就需要找到当前节点的添加位置
     * 2）由于是单项链表，每个节点只有next指针指向后一个元素，因此寻找添加元素的位置时，要找到该位置的前一个元素；
     * 3）让前一个元素的 next 指向要添加的 newStudent 节点，再让 newStudent 节点的next 指向该位置的后一个节点；
     * 4）由于head 头节点不能动，需要指定一个中间临时变量接收 head 节点，以便往后移动寻找可添加元素的位置
     */
   public void addByOrder(StudentPo newStudent){
        StudentPo temp = headNode;
        boolean flag = false;//表示 当前链表中是否存在同一个 sno 的学生，默认不存在。

        while(true){
            if(temp.next==null){//开始遍历时，temp（head）的next就是第一个元素，即从第一个元素开始挨个比一遍，直到找到可添加元素的位置
                break;
            }
            if(temp.next.sno>newStudent.sno){
                break;
            }else if(temp.next.sno == newStudent.sno){
                flag=true;
                break;
            }
            temp= temp.next;
        }

        if(flag){
            System.out.println("已经存在相同学号的学生了。。。");
            return;
        }else{
            newStudent.next = temp.next;
            temp.next = newStudent;
        }
   }

    /**
     * 修改链表中的元素
     * @param student 要修改的节点
     * 分析：
     * 从头开始找，找到要修改的节点，直接赋值修改
     *
     */
   public void update(StudentPo student){

       boolean flag = false;//是否找到了要修改的元素
       if(headNode.next==null){
           System.out.println("链表为空～～～");
           return;
       }
       StudentPo temp = headNode.next;
       while(true){
           if(temp==null){//已经遍历到了链表的最后一个元素，没找到要修改的元素
               break;
           }
           if(temp.sno==student.sno){
               flag=true;
               break;
           }
           temp=temp.next;
       }
       if(flag){
            temp.sname=student.sname;
       }else{
           System.out.println("没有找到学号为["+student.sno+"]的节点，不能修改～～～");
       }

   }

    /**
     * 删除链表中的元素
     * @param sno 要删除的节点的编号（学号）
     * 分析：
     * 由于是单项链表，只能通过 next 向后查找，因此需要找到待删除节点的前一个节点，让它的 next 指向待删除节点的后一个节点，此时形成一个新的链表。
     * 指针重新指向待删除节点的后一个节点后，被删除的节点不在被引用，会被垃圾回收机制自动回收。
     */
   public void del(int sno){
       if(headNode.next==null){
           System.out.println("链表为空～～～");
           return;
       }

        StudentPo temp = headNode;
        boolean flag = false;//表示是否找到要删除的节点

        while(true){
            if(temp.next==null){//一直遍历到最后一个节点了，也没找到要删除的节点
                break;
            }
            if(temp.next.sno==sno){
                flag=true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next=temp.next.next;
        }else{
            System.out.println("没有找到学号为["+sno+"]的节点，不能删除～～～");
        }
   }

    /**
     * 展示当前链表中的所有元素
     */
   public void showLinkedList(){
       if(headNode.next==null){
           System.out.println("链表为空～～～");
           return;
       }
       StudentPo temp = headNode.next;//从头节点的下一个节点开始遍历
       while(true){
           if(temp==null){
               break;
           }
           System.out.println("学号："+temp.sno+",姓名："+temp.sname);
           temp=temp.next;
       }
   }
}





class StudentPo{
    public int sno;
    public String sname;
    public StudentPo next;


    public StudentPo() {
    }

    public StudentPo(int sno, String sname) {
        this.sno = sno;
        this.sname = sname;
    }

    @Override
    public String toString() {
        return "StudentPo{" +
                "sno=" + sno +
                ", sname='" + sname + '\'' +
                '}';
    }
}

三、单向链表的常见面试题

1.求单向链表中有效节点的个数

 /**
     * 1.求单向链表中有效节点的个数
     * 分析：
     * 求有效节点的个数就是从第一个节点开始遍历，直到最后一个（next 指向 null的节点），统计数量
     *
     * @param headNode
     */
    public int getLength(StudentPo headNode){
        int length = 0;
        if(headNode.next==null){
            System.out.println("当前链表为空～～～");
            return 0;
        }

        StudentPo temp = headNode.next;
        while (temp!=null){

            length++;
            temp = temp.next;
        }
        return length;
    }

2.查找单链表中倒数第k个节点

  /**
     * 2.查找单链表中倒数第k个节点
     * 分析：
     * 1）遍历整个链表，得到链表的有效节点个数 size
     * 2）要找到倒数第k个节点，即是从链表第一个节点开始遍历，向后移动 size-k 次即可得到。
     * @param headNode
     * @return
     */
    public StudentPo getRecipKNode(StudentPo headNode , int k){
        if(headNode.next==null){
            System.out.println("当前链表为空～～～");
            return null;
        }

        int size = getLength(headNode);

        // 对 k 做校验，倒数滴k个节点，则k的值必须符合：k>0,&& k<size
        if(k<=0 || k>size){
            System.out.println("K 的值不在 链表范围内");
            return null;
        }
        StudentPo temp = headNode.next;
        for(int i=0;i<size-k;i++){
            temp = temp.next;
        }
        return temp;
    }

3.单链表的反转

 /**
     *  3.单链表的反转
     *  分析：
     *  反转的意思是：让链表中的节点按照相反的顺序连接在 head节点后面。
     *  1）创建一个新的头部节点 reverseHead，用于连接反转过来的节点；
     *  2）从头开始遍历需要反转的链表，每取出一个节点，都放在 reverseHead 后的第一个位置；
     *  3）从原链表中取出所有节点后，head.next = reverseHead.next 让head 节点指向反转后的链表节点
     *  tips: 由于是单向链表，所以每次从原链表中取出一个节点，都要用 一个变量记下下一个节点，否则就找不到下一个节点了
     * @param headNode
     */
    public void reverseLinkedList(StudentPo headNode){
        StudentPo reverseHead = new StudentPo(0,"");
        if(headNode.next==null){
            System.out.println("当前链表为空～～～");
            return;
        }
        StudentPo temp = headNode.next;
        StudentPo next = null;
        while (temp!=null){
            //先记录下一个节点
            next = temp.next;
            //将取下来的节点添加到reverseHead的第一个位置
            temp.next = reverseHead.next;
            reverseHead.next = temp;
            temp = next;
        }
        headNode.next = reverseHead.next;
    }

4.从尾到头打印但链表

/**
     * 4.从尾到头 反向打印单链表
     * 分析：
     * 方式一：先将链表反转，再顺序打印出（但是会改变原来的链表）
     * 方式二：将链表中的节点顺序遍历，压入栈中，然后再从栈中弹出即可（利用栈的先进后出原理）
     * @param headNode
     */
    public void printLinkedList(StudentPo headNode){
        Stack<StudentPo> stack = new Stack();
        StudentPo temp = headNode.next;
        while(temp!=null){
            stack.push(temp);
            temp = temp.next;
        }
        while(stack.size()>0){
            StudentPo obj = stack.pop();
            System.out.println(obj);
        }
    }

5.合并两个有序的单链表，合并之后依然有序

/**
     *  5.合并两个有序的单链表，合并之后依然有序
     *  分析：
     *  以 链表l1 为基准，遍历 l2 ，将l2 中的节点挨个添加到 l1 链表中去。
     *  1）遍历l2，每次从 l2 中按顺序取出一个节点；
     *  2）拿着这个节点，在l1 中寻找合适的位置的前一个节点；
     *  3）让新增节点的 next 指向 插入位置的下一个节点；
     *  4）让新增位置的前一个节点的 next 指向新增节点；
     *
     * @param l1
     * @param l2
     */
    public SingleLinkedList mergeLinkedList(SingleLinkedList l1,SingleLinkedList l2){
        StudentPo headNode1 = l1.getHeadNode();
        StudentPo headNode2 = l2.getHeadNode();
        if(headNode1.next==null){
            System.out.println("链表1为空");
            return l2;
        }
        if(headNode2.next==null){
            System.out.println("链表2为空");
            return l1;
        }
        StudentPo temp1 = headNode1.next;
        StudentPo temp2 = headNode2.next;
        StudentPo next = null;
        while(true){
            if(temp2==null){
                break;
            }
            boolean flag = false; //是否找到了添加的位置
            while(true){
                if(temp1.next==null){
                    break;
                }
                if(temp1.next!=null && temp1.next.sno>temp2.sno || temp1.next.sno==temp2.sno){
                    flag=true;
                    break;
                }
                temp1 = temp1.next;
            }

            next = temp2.next;
            if(flag){
                temp2.next = temp1.next;
                temp1.next=temp2;

            }else{
                temp1.next=temp2;
            }
            temp2 = next;
        }
        return l1;
    }

本文地址：https://blog.csdn.net/zxjdC/article/details/107339771