本文为joshua317原创文章,转载请注明：转载自joshua317博客 https://www.joshua317.com/article/68

数据结构和算法-单向链表

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不必须相邻，那么，怎么表示逻辑上的相邻关系呢？可以给每个元素附加一个指针域，指向下一个元素的存储位置。 如图：

从上图中我们也可以直观看出,每个结点包含两个域：数据域和指针域，指针域存储下一个结点的地址，因此指针指向的类型也是结点类型。

1. 链表的特点

• 链表是一种非线性、非顺序的物理结构，是由若干个节点组成。
• 链表采用的是“见缝插针”的存储方法，不要求内存连续，靠next指针关联起来。
• 链表的物理存储方式为随机存储，访问方式为顺序访问。
• 查找节点的时间复杂度为O(n)，插入、删除节点的时间复杂度为O(1)。
• 链表适用于写操作多，读操作少的场景。

2.链表的核心要素

1. 每个节点由数据域和指针域组成
2. 指针域指向下一个节点的内存地址

3.链表类型

单向链表

双向链表

循环链表

4.单向链表

链表中最简单的一种是单向链表，它包含两个域，一个信息域(data)和一个指针域(next)。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值（NULL）。所谓单链表无疑是链式存储方式，节点中的next指针指向下一个节点，存储空间不是连续的。

单向链表我们把他分为头节点和节点，头节点默认是链表的头部，不存储数据，节点则存储数据。

如图，头节点不存储数据，但是他的指针指向节点1的地址，所以头节点和节点1链接起来了。然后节点1的指针又指向了节点2的地址，使节点1和节点2也链接起来了…最后，节点i的指针指向节点n，最后一个节点，最后一个节点n的指针指向了NULL。至此，一条链条诞生了。

单向链表的操作

单向链表的操作方式主要分为增、删、改、查等操作

4.1 单向链表的建立，初始化

（1）若原链表为空，则将新建节点设置为头节点

（2）若原链表为非空，则将新建节点添加到表尾

4.2 单链表的插入操作

向一个链表中插入一个新节点时，首先要新建一个节点，并将新建节点的指针域初始化为空NULL，然后在链表中寻找适当的位置执行节点插入操作，此时需要考虑下面4种情况：

（1）若原链表为空，则将新建节点p作为头节点，让head指向新节点p

（2）若原链表为非空，折按新建节点的值的大小（假设原链表已按节点值升序排列）确定插入新节点的位置。若在头结点前插入新节点，则将新节点的指针域指向原链表的头结点，并且让head指向新节点p

（3）若在原链表中间插入新节点，则将新节点p的指针域指向下一节点，并且让前一节点的指针域指向新建节点p

（4）若在表尾插入新节点，则将尾节点的指针域指向新节点p

4.3 单向链表的删除操作

链表的删除操作就是将待删除的节点从链表中断开，那么待删除节点的上一个节点就成为尾节点。在删除节点时，我们要考虑一下4种情况：

（1）若原链表为空，则不执行任何操作，直接退出程序

（2）若待删除节点是头节点，则将head指向当前节点的下一个节点，再删除当前节点

（3）若待删除节点不是头节点，则将前一节点的指针域指向当前节点的下一节点，即可删除当前节点。当待删除节点是尾节点时，由于p->next=NULL，因此执行pr->next = p->next后，pr->next的值也变为了NULL，从而使pr所指向的节点由倒数第二个节点变成尾节点。

（4）若待删除的节点不存在，则退出程序

注意：节点被删除后，只表示将它从链表中断开而已，它仍占用着内存，必须要释放这个内存，否则会出现内存泄漏。

4.4 单向链表的修改

（1）若原链表为空，则不执行任何操作，直接退出程序

（2）若节点找到，对节点数据进行修改，否则直到节点未找到时，则退出程序

4.5 单向链表的查找

（1）若原链表为空，则不执行任何操作，直接退出程序

（2）若节点找到，则返回节点，否则直到节点未找到时，则退出程序

4.6 程序实现

package com.joshua317;

public class Main {

    public static void main(String[] args) {

        // write your code here
        Node node1 = new Node(1,"小松");
        Node node2 = new Node(2,"小明");
        Node node3 = new Node(3,"小红");
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.list();
        singleLinkedList.len();

        singleLinkedList.delete(4);

        System.out.println("删除节点后的列表为：");
        singleLinkedList.list();
    }
}

class SingleLinkedList {
    //先初始化一个头节点
    private Node head = new Node(0, "");

    /**
     * 添加节点到单向链表，不考虑排序，在链表尾部加入节点
     * 1.找到当前链表的最后节点
     * 2.将最后这个节点的next指向新的节点
     */
    public void add(Node node)
    {
        Node temp = head;
        //遍历链表，找到最后的节点
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后temp节点的next指向新的节点
        temp.next = node;
    }
    //显示链表[遍历]
    public void list()
    {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个辅助变量来遍历
        Node temp = head.next;
        while (true) {
            //判断节点是否为空
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    /**
     * 获取节点数据
     * @param no
     */
    public void get(int no)
    {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个辅助变量来遍历
        Node temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == no)  {
                System.out.println(temp);
                break;
            }
            temp = temp.next;
        }
    }

    public void delete(int no)
    {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，所以需要一个辅助变量来遍历
        Node temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("数据no:" + no + "不存在");
        }
    }
    public int len()
    {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return 0;
        }
        Node temp = head.next;
        int len = 0;
        while (true) {
            if (temp == null) {
                break;
            }
            len++;
            temp = temp.next;
        }
        System.out.println("链表的长度为:" + len);
        return len;
    }
}

//定义一个Node节点，每个Node对象是一个节点
class Node {
    public int no;
    public String name;
    public Node next;//指向下一个节点
    //构造函数
    public Node (int no, String name) {
        this.no = no;
        this.name = name;
    }

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

5. 链表的常见面试题(持续整理，附代码)

5.1 两数相加

5.2 判断链表中是否有环

5.3 删除链表的倒数第N个节点

5.4 反转链表（单链表）

5.5 回文链表

5.6 合并两个有序链表

本文为joshua317原创文章,转载请注明：转载自joshua317博客 https://www.joshua317.com/article/68