数据结构之链表篇

“

Hello，大家好！我是老丑，今天给大家分享的是一种数据结构——链表

”

链表是什么？

有人肯定会说，链表是一种数据结构啊！

说的对！

链表是那么多数据结构中的一种。也是面试常问的一种，当然面试常问的很多，今天我们只讨论这个常问的链表。

链表的定义

“

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

”

不知道大家吃没吃过糖葫芦，请看：

大家所看到的一串糖葫芦其实就可以被理解为一个非常常见的链表。

生活中，处处有惊喜！！！

糖葫芦被我们的竹签以某种形式进行串起来了，是不是有内味了。

链表的存储方式不再是物理地址开辟一块连续空间存储所有结点的形式，而是通过绳子（指针）将结点链接（串）起来，每个结点在物理空间可以不相邻（物理空间，也就是实际的空间），而逻辑空间上是连续的。

链表的优缺点

优点：

可以充分使用碎片化的内存空间
插入和删除元素，只需要改变指向，而不用全部迁移。
插入和删除时间复杂度角度，适合插入和删除频繁的场景
可动态扩增

缺点：

不具备随机访问的特性
需要额外的空间来记录下一个结点的地址。
查询效率低，所以不适合查询频繁的场景

必要的概念

结点，头结点，尾结点，指针域

链表的最基本操作

查找结点
插入结点
删除结点

链表的分类

单链表

单链表是链表里面最简单的一种，指的是链表中的结点的指向只能指向链表中的下一个结点或者为空，元素之间不能互相指向。
双链表

每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针。即结点类中会存在Prev和Next两个成员变量，其中Prev指向左边的链表结点，Next指向右边的链表结点
循环链表

将单链表的尾结点指向头结点从而实现循环。
双向循环链表

在双链表的基础上，尾结点的Next指针指向头结点，头结点的Prev指针指向尾结点。

图示

图中主要显示的是单链表。至于双链表和循环链表和双向循环链表，大家可以自行脑补。

注意：图中的头结点的数据域是null。

很多博文中的图，可能会导致误解，上面的图是确保正确的。

单链表的自实现

因为老丑主修的是Java语言，所以单链表的自实现也会采用Java语言来实现

大家可以自行了解双链表和循环链表。

结点类

package cn.laochou.link;

public class Node {

    private String data;

    private Node next;

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

链表类

package cn.laochou.link;

/**
 * 链表类
 */
public class ListNode {

    // 头结点
    private Node head;

    // 大小
    private int size;

    public ListNode() {
        head = new Node(null);
        size = 0;
    }

    /**
     * 添加元素
     * @param node 元素
     */
    public void addNode(Node node) {
        Node cur = head;
        while (cur.getNext() != null) {
            cur = cur.getNext();
        }
        cur.setNext(node);
        size++;
    }

    /**
     * 插入元素
     * @param index 元素索引
     * @param node 元素
     */
    public void insertNode(int index, Node node) {
        if(index > size) {
            return;
        }
        // 当索引位置等于链表大小，即是尾结点
        if(index == size) {
            Node cur = head;
            while (cur.getNext() != null) {
                cur = cur.getNext();
            }
            cur.setNext(node);
        }
        // 当索引位置小于链表大小，说明在中间
        else {
            Node cur = head;
            // 在这里注意，我们如果想在中间插入的话，是必须找到该索引对应结点的前面一个结点。
            // 我们插入的结点的next指针需要指向原来索引所指向的结点。
            // 大家可以想一下，我们需要前一个节点的next指针指向我们要插入的结点。
            // 大家在这里好好理一理哈。
            for(int i = 0; i < index; i++) {
                cur = cur.getNext();
            }
            node.setNext(cur.getNext());
            cur.setNext(node);
        }
    }


    /**
     * 删除元素
     * @param index 元素所对应的索引
     */
    public void removeNode(int index) {
        if(index >= size) {
            return;
        }
        // 说明删除的是最后一个结点
        if(index == size - 1) {
            Node cur = head;
            while (cur.getNext().getNext() != null) {
                cur = cur.getNext();
            }
            cur.setNext(null);
        }else {
            Node cur = head;
            for(int i = 0; i < index; i++) {
                cur = cur.getNext();
            }
            cur.setNext(cur.getNext().getNext());
        }
    }

    /**
     * 查找元素
     * @param data 元素数据
     * @return 返回该结点
     */
    public Node search(String data) {
        Node cur = head;
        if(data != null) {
            // 在这里注意为什么使用data.equals()，而不是cur.getData().equals()
            while (cur.getNext() != null) {
                if(data.equals(cur.getData())) {
                    return cur;
                }else {
                    cur = cur.getNext();
                }
            }
        }
        return null;
    }

    /**
     * 遍历链表
     */
    public void forEach() {
        Node cur = head;
        while (cur.getNext() != null) {
            System.out.println(cur.getNext());
            cur = cur.getNext();
        }
    }

}

主类

import cn.laochou.link.ListNode;
import cn.laochou.link.Node;

public class Main {

    public static void main(String[] args) {
        ListNode listNode = new ListNode();
        Node node = new Node("laochou");
        Node node2 = new Node("yzl");
        listNode.addNode(node);
        listNode.addNode(node2);
        Node node3 = new Node("bajie");
        listNode.insertNode(1, node3);
        listNode.forEach();
        System.out.println("-----------");
        System.out.println(listNode.search("lz"));
        System.out.println(listNode.search("wave"));
        System.out.println(listNode.search("laochou"));
        System.out.println("------------");
        listNode.removeNode(0);
        listNode.forEach();
        System.out.println("------------");
        listNode.removeNode(1);
        listNode.forEach();
    }

}

最后结果

我希望，大家可以阅读主类，可以先在大脑里面运行下代码。

Node{data='laochou', next=Node{data='bajie', next=Node{data='yzl', next=null}}}
Node{data='bajie', next=Node{data='yzl', next=null}}
Node{data='yzl', next=null}
-----------
null
null
Node{data='laochou', next=Node{data='bajie', next=Node{data='yzl', next=null}}}
------------
Node{data='bajie', next=Node{data='yzl', next=null}}
Node{data='yzl', next=null}
------------
Node{data='bajie', next=null}

小试牛刀

大家如果跟着上面把单链表实现了，那么恭喜你，你已经自己完成了一个单链表。

当然对于初步学习链表的小伙伴，可能不太适应，因此我特意找了一个小题目。

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

来源：力扣（LeetCode）

大家可以一试。