数据结构之单链表

简介

概念介绍

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

链接存储方法

链接方式存储的线性表简称为链表（Linked List）。

链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

结点结构

┌───┬───┐

│ data│next ｜

└───┴───┘

data域–存放结点值的数据域

next域–存放结点的直接后继的地址（位置）的指针域（链域）

链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。

单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。

终端结点无后继，故终端结点的指针域为空，即NULL。

图示

带单独头节点单链表的逻辑结构示意图

不带单独头节点的单链表逻辑结构示意图

代码实现

使用带head头的单向链表实现 –水浒英雄排行榜管理。图示省略nickname

定义节点类

创建HeroNode类

//定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    //为了显示方便，我们重新toString
    @Override
    public String toString() {
        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
    }
}

创建单链表类

定义SingleLinkedList 管理我们的英雄，创建一个head节点类成员属性。

//先初始化一个头节点, 头节点不要动, 不存放具体的数据
private HeroNode head = new HeroNode(0, "", "");

获取到头节点

直接将单链表类中定义的head返回return head;

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

遍历单链表

首先判断单链表是否为空head.next=null,不为空依次遍历节点

//显示链表[遍历]
public void list() {
    //判断链表是否为空
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }
    //因为头节点，不能动，因此我们需要一个辅助变量来遍历
    HeroNode temp = head.next;//不打印头节点
    //判断是否到链表最后
    while (temp != null) {
        //输出节点的信息
        System.out.println(temp);
        //将temp后移， 一定小心
        temp = temp.next;
    }
}

添加节点

遍历单链表，在最后一个节点添加入新的节点。HerNode temp = head;

//添加节点到单向链表
//思路，当不考虑编号顺序时
//1. 找到当前链表的最后节点
//2. 将最后这个节点的next 指向 新的节点
public void add(HeroNode heroNode) {
    //因为head节点不能动，因此我们需要一个辅助遍历 temp
    HeroNode temp = head;
    //遍历链表，找到最后
    while (temp.next != null) {
        //如果没有找到最后, 将temp后移
        temp = temp.next;
    }
    //当退出while循环时，temp就指向了链表的最后
    //将最后这个节点的next 指向新的节点
    temp.next = heroNode;//第一次添加的时候不走循环，直接赋值
}

测试

//进行测试
//先创建节点
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

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

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

singleLinkedList.list();

添加节点，遍历单链表成功！

排序添加节点

添加节点的时候根据节点的编号按照从小到大的顺序依次添加节点HerNode temp = head;由于是单链表所以为们要通过temp.next才能进行比较节点。如果temp.next.no>heroNode.no则进行相应的操作。temp.next.no==heroNode.no则序号相同不添加。temp.next.no<heroNode.no则正常在尾部添加

//第二种方式在添加英雄时，根据排名将英雄插入到指定位置
//(如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode heroNode) {
    //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
    //因为单链表，因为我们找的temp 是位于添加位置的前一个节点，才能指向它，否则插入不了
    HeroNode temp = head;
    while (temp.next != null) {
        if (temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
            //插入到链表中, temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
            return;
        } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
            return;
        }
        temp = temp.next; //后移，遍历当前链表
    }
    //第一次添加,temp.next 为null。后面则序号大于最后一个节点序号，在最后添加节点
    temp.next = heroNode;
}

测试

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

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

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

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        //显示
        singleLinkedList.list();
        
    }

使用排序添加节点，遍历单链表。排序成功！

修改节点

首先判断链表是否为空，不为空根据节点的序号修改节点信息，若通过序号没有匹配到该节点，提示信息。`HeroNode temp = head.next;

//根据no修改
public void update(HeroNode newHeroNode) {
    //判断是否为空
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }
    HeroNode temp = head.next;
    while (temp != null) {
        //当遍历节点的no与更新的no相等时修改信息
        if (temp.no == newHeroNode.no) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
            return;
        }
        temp = temp.next;
    }
    System.out.println("链表中没有该编号节点信息！");
}

测试

    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

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

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

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        //显示
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

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

    }

修改节点信息成功！

删除节点

首先判断链表是否为空，不为空根据序号删除节点，序号不存在提示错误信息！while循环条件应为temp.next != null否则当遍历到最后一个节点时temp.next为null，报空指针异常。

//根据no删除节点
public void del(int no) {
    if (head.next == null) {
        System.out.println("当前链表为空！");
    }

    HeroNode temp = head;
    //经过上面判断，当前链表不为空，所以条件为temp!=null; temp.next当遍历最后一个节点时发生越界
    while (temp.next != null) {
        //找到该节点，同样是找代删链表的前一个节点
        if (temp.next.no == no) {
            temp.next = temp.next.next;
            return;
        }
        //后移
        temp = temp.next;
    }
    System.out.println("要删除的节点不存在！");
}

测试

    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

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

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

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        //显示
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

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

        //删除一个节点
        singleLinkedList.del(1);
        singleLinkedList.del(4);
        System.out.println("删除后的链表情况~~");
        singleLinkedList.list();

    }

链表长度

传入链表头节点获取链表的有效长度。

//方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)

/**
 * @param head 链表的头节点
 * @return 返回的就是有效节点的个数
 */
public static int getLength(HeroNode head) {
    if (head.next == null) { //空链表
        return 0;
    }
    int length = 0;
    //定义一个辅助的变量, 这里我们没有统计头节点
    HeroNode cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next; //遍历
    }
    return length;
}

测试

 public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

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

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

        //加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);

        //显示
        singleLinkedList.list();

        //测试修改节点的代码
        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
        singleLinkedList.update(newHeroNode);

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

        //删除一个节点
        singleLinkedList.del(1);
        singleLinkedList.del(4);
        System.out.println("删除后的链表情况~~");
        singleLinkedList.list();

        //测试一下 求单链表中有效节点的个数
        System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));

        
    }

查找倒数k节点

根据传入的位置在链表中查找节点。首先判断链表是否为空，接着判断传入的位置的合法性。在获取到链表的总共长度。int i = 0;i <size - index; i+=

public static HeroNode findLastIndexNode(HeroNode heroNode, int index) {
    //判断该链表是否为空
    if (heroNode.next == null) return null;

    //得到该链表的长度节点个数
    int size = getLength(heroNode);

    if (index <= 0 || index > size) return null;

    HeroNode node = heroNode.next;
    for (int i = 0; i < size - index; i++) {
        node = node.next;
    }
    return node;
}

链表反转

将一条链表反转，要创建一个新的节点来进行操作。详情看图！

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

    //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    HeroNode cur = head.next;
    HeroNode next = null;// 指向当前节点[cur]的下一个节点
    HeroNode reverseHead = new HeroNode(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 reversePrint(HeroNode head) {
    if (head.next == null) {
        return;//空链表，不能打印
    }
    //创建要给一个栈，将各个节点压入栈
    Stack<HeroNode> stack = new Stack<HeroNode>();
    HeroNode cur = head.next;
    //将链表的所有节点压入栈
    while (cur != null) {
        stack.push(cur);
        cur = cur.next; //cur后移，这样就可以压入下一个节点
    }
    //将栈中的节点进行打印,pop 出栈
    while (stack.size() > 0) {
        System.out.println(stack.pop()); //stack的特点是先进后出
    }
}