数据结构之链表(LinkedList)(一)

链表(Linked List)介绍

链表是有序的列表，但是它在内存中是存储如下

1）链表是以节点方式存储的，是链式存储

2）每个节点包含data域（value），next域，指向下一个节点

3）各个节点不一定连续存储，如上图

4）链表分 带头节点的链表和 不带头节点的链表，根据实际需求确定

单链表介绍

单链表(带头结点) 逻辑结构示意图如下

应用实例

使用带head头的单向链表实现 –学生成绩录入管理   {学号，姓名，分数}

1.完成学生成绩的增删改查操作

2.第一种方法在添加英雄时，直接添加到链表的尾部

3.第二种方式在添加学生时，根据学号排序，将学生插入指定位置

第一种实现思路：

添加（创建）

1. 先创建一个head 头节点， 作用就是表示单链表的头

2. 后面我们每添加一个节点，就直接加入到 链表的最后

遍历：

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

示意图：

 

代码实例:

package com.linkedList;

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();
    }
}
//定义SingleLinkedList 管理我们的学员
class SingleLinkedList {
    //先初始化一个头节点, 头节点不要动, 不存放具体的数据
    private StuNode head = new StuNode(0, "", "");


    //返回头节点
    public StuNode getHead() {
        return head;
    }

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1. 找到当前链表的最后节点
    //2. 将最后这个节点的next 指向 新的节点
    public void add(StuNode stuNode) {

        //因为head节点不能动，因此我们需要一个辅助遍历 temp
        StuNode temp = head;
        //遍历链表，找到最后
        while(true) {
            //找到链表的最后
            if(temp.next == null) {//
                break;
            }
            //如果没有找到最后, 将将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next 指向 新的节点
        temp.next = stuNode;
    }

    //显示链表[遍历]
    public void list() {
        //判断链表是否为空
        if(head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点，不能动，因此我们需要一个辅助变量来遍历
        StuNode temp = head.next;
        while(true) {
            //判断是否到链表最后
            if(temp == null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            //将temp后移， 一定小心
            temp = temp.next;
        }
    }
}
//定义StuNode ， 定义StuNode 对象就是一个节点
class StuNode {
    public int stuNo;
    public String name;
    public String mark;
    public StuNode next; //指向下一个节点
    //构造器
    public StuNode(int stuNo, String name, String mark) {
        this.stuNo = stuNo;
        this.name = name;
        this.mark = mark;
    }
    //为了显示方法，我们重新toString
    @Override
    public String toString() {
        return "StuNode [stuNo=" + stuNo + ", name=" + name + ", mark=" + mark + "]";
    }
}

代码

 输出：

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=4, name=小红, mark=90]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]

 从上面可以看出链表存储是根据先后录入顺序的，那么我们想要根据stuNo存储呢。

第二种方式在添加学生时，根据学号排序，将学生插入指定位置

实现思路：

需要按照学号的顺序添加

1. 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定

2. 新的节点.next = temp.next

3. 将temp.next = 新的节点

示意图：

实现代码：

将代码加入SingleLinkedList中

//第二种方式在添加学生时，根据学号将学生插入到指定位置
    //(如果有这个学号，则添加失败，并给出提示)
    public void addByOrder(StuNode stuNode) {
        //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
        //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
        StuNode temp = head;
        boolean flag = false; // flag标志添加的编号是否存在，默认为false
        while(true) {
            if(temp.next == null) {//说明temp已经在链表的最后
                break; //
            }
            if(temp.next.stuNo > stuNode.stuNo) { //位置找到，就在temp的后面插入
                break;
            } else if (temp.next.stuNo == stuNode.stuNo) {//说明希望添加的stuNode的学号已然存在

                flag = true; //说明学号存在
                break;
            }
            temp = temp.next; //后移，遍历当前链表
        }
        //判断flag 的值
        if(flag) { //不能添加，说明学号存在
            System.out.printf("准备插入的学生 %d 已经存在了, 不能加入\n", stuNode.stuNo);
        } else {
            //插入到链表中, temp的后面
            stuNode.next = temp.next;
            temp.next = stuNode;
        }
    }

public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();
    }

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]

 链表修改：

实现思路：

1.修改节点的信息, 根据stuNo来修改，即stuNo不能改

2.将修改的值替换

实现代码:

//修改节点的信息, 根据stuNo来修改，即stuNo不能改.
    //说明
    //1. 根据 newStuNode 的 stuNo 来修改即可
    public void update(StuNode newStuNode) {
        //判断是否空
        if(head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        //找到需要修改的节点, 根据stuNo
        //定义一个辅助变量
        StuNode temp = head.next;
        boolean flag = false; //表示是否找到该节点
        while(true) {
            if (temp == null) {
                break; //已经遍历完链表
            }
            if(temp.stuNo == newStuNode.stuNo) {
                //找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag 判断是否找到要修改的节点
        if(flag) {
            temp.name = newStuNode.name;
            temp.mark = newStuNode.mark;
        } else { //没有找到
            System.out.printf("没有找到 学号 %d 的节点，不能修改\n", newStuNode.stuNo);
        }
    }

public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();

        StuNode newStu = new StuNode(3,"王五","99");
        singleLinkedList.update(newStu);

        System.out.println("修改之后的链表");
        singleLinkedList.list();

    }

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
修改之后的链表
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=王五, mark=99]
StuNode [stuNo=4, name=小红, mark=90]

链表删除：

实现思路：

1. 我们先找到 需要删除的这个节点的前一个节点 temp

2. temp.next = temp.next.next(待删除节点的上一个节点next直接指向待删除节点的下一个节点)

3. 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收

示意图:

实现代码：

//删除节点
    //思路
    //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
    //2. 说明我们在比较时，是temp.next.stuNo 和  需要删除的节点的stuNo比较
    public void del(int stuNo){
        StuNode temp = head;
        boolean flag = false;
        while (true){
            if (temp.next==null){
                break;
            }
            if(temp.next.stuNo==stuNo){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next=temp.next.next;
        }else {
            System.out.printf("要删除的 %d 学号节点不存在",stuNo);
        }

    }

public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();

        singleLinkedList.del(2);
        System.out.println("删除之后的链表");
        singleLinkedList.list();

    }

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
删除之后的链表
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]

下面我们看几道关于单链表的面试题。

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

2.查找单链表中的倒数第k个结点 【新浪面试题】

3.单链表的反转【腾讯面试题，有点难度】

4.从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】

第一题思路，只要遍历该链表就可得出有效节点的个数

实现代码：

//方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
    /**
     *
     * @param head 链表的头节点
     * @return 返回的就是有效节点的个数
     */
    public static int getLength(StuNode head) {
        if(head.next == null) { //空链表
            return 0;
        }
        int length = 0;
        //定义一个辅助的变量, 这里我们没有统计头节点
        StuNode cur = head.next;
        while(cur != null) {
            length++;
            cur = cur.next; //遍历
        }
        return length;
    }

public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();

        singleLinkedList.del(2);
        System.out.println("删除之后的链表");
        singleLinkedList.list();

        System.out.println("有效节点个数="+getLength(singleLinkedList.getHead()));


    }

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
删除之后的链表
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
有效节点个数=3

第二题思路，先遍历出链表有效节点数size，在第size-k个就是倒数k个节点

实现代码：

//查找单链表中的倒数第k个结点 【新浪面试题】
    //思路
    //1. 编写一个方法，接收head节点，同时接收一个index 
    //2. index 表示是倒数第index个节点
    //3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
    //4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
    //5. 如果找到了，则返回该节点，否则返回nulll
    public static StuNode findLastIndexNode(StuNode head, int index) {
        //判断如果链表为空，返回null
        if(head.next == null) {
            return null;//没有找到
        }
        //第一个遍历得到链表的长度(节点个数)
        int size = getLength(head);
        //第二次遍历  size-index 位置，就是我们倒数的第K个节点
        //先做一个index的校验
        if(index <=0 || index > size) {
            return null;
        }
        //定义给辅助变量， for 循环定位到倒数的index
        StuNode cur = head.next; //3 // 3 - 1 = 2
        for(int i =0; i< size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }

public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();

        singleLinkedList.del(2);
        System.out.println("删除之后的链表");
        singleLinkedList.list();
        System.out.println("有效节点个数="+getLength(singleLinkedList.getHead()));
        StuNode stuNode = findLastIndexNode(singleLinkedList.getHead(),2);
        System.out.println("倒数第二个节点数是"+stuNode);
    }

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
删除之后的链表
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
有效节点个数=3
倒数第二个节点数是StuNode [stuNo=3, name=小明, mark=70]

第三题思路

1. 先定义一个节点 reverseHead = new StuNode();

2. 从头到尾遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端.

3. 原来的链表的head.next = reverseHead.next

实现代码：

//将单链表反转
    public static void reversetList(StuNode head) {
        //如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if(head.next == null || head.next.next == null) {
            return ;
        }

        //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
        StuNode cur = head.next;
        StuNode next = null;// 指向当前节点[cur]的下一个节点
        StuNode reverseHead = new StuNode(0, "", "");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
        //动脑筋
        while(cur != null) {
            next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
            reverseHead.next = cur; //将cur 连接到新的链表上
            cur = next;//让cur后移
        }
        //将head.next 指向 reverseHead.next , 实现单链表的反转
        head.next = reverseHead.next;
    }

public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();
        System.out.println("反转链表的情况");
        reversetList(singleLinkedList.getHead());
        singleLinkedList.list();

        /*singleLinkedList.del(2);
        System.out.println("删除之后的链表");
        singleLinkedList.list();
        System.out.println("有效节点个数="+getLength(singleLinkedList.getHead()));
        StuNode stuNode = findLastIndexNode(singleLinkedList.getHead(),2);
        System.out.println("倒数第二个节点数是"+stuNode);*/
    }

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
反转链表的情况
StuNode [stuNo=4, name=小红, mark=90]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=1, name=张三, mark=85]

第四题思路

1. 上面的题的要求就是逆序打印单链表.

2. 方式1： 先将单链表进行反转操作，然后再遍历即可，这样的做的问题是会破坏原来的单链表的结构，不建议

3. 方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果.

实现代码：

//方式2：
    //可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
    public static void reversePrint(StuNode head) {
        if(head.next == null) {
            return;//空链表，不能打印
        }
        //创建要给一个栈，将各个节点压入栈
        Stack<StuNode> stack = new Stack<StuNode>();
        StuNode cur = head.next;
        //将链表的所有节点压入栈
        while(cur != null) {
            stack.push(cur);
            cur = cur.next; //cur后移，这样就可以压入下一个节点
        }
        //将栈中的节点进行打印,pop 出栈
        while (stack.size() > 0) {
            System.out.println(stack.pop()); //stack的特点是先进后出
        }
    }

public static void main(String[] args) {
        //进行测试
        //先创建节点
        StuNode hero1 = new StuNode(1, "张三", "85");
        StuNode hero2 = new StuNode(2, "李四", "87");
        StuNode hero3 = new StuNode(3, "小明", "70");
        StuNode hero4 = new StuNode(4, "小红", "90");

        //创建要给链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();


        //加入
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        // 测试一下单链表的反转功能
        System.out.println("原来链表的情况");
        singleLinkedList.list();
        System.out.println("逆序打印单链表");
        reversePrint(singleLinkedList.getHead());

        /*singleLinkedList.del(2);
        System.out.println("删除之后的链表");
        singleLinkedList.list();
        System.out.println("有效节点个数="+getLength(singleLinkedList.getHead()));
        StuNode stuNode = findLastIndexNode(singleLinkedList.getHead(),2);
        System.out.println("倒数第二个节点数是"+stuNode);*/
    }

原来链表的情况
StuNode [stuNo=1, name=张三, mark=85]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=4, name=小红, mark=90]
逆序打印单链表
StuNode [stuNo=4, name=小红, mark=90]
StuNode [stuNo=3, name=小明, mark=70]
StuNode [stuNo=2, name=李四, mark=87]
StuNode [stuNo=1, name=张三, mark=85]