【数据结构】Java实现单链表

1. ArrayList的缺陷

2. 链表

2.1 链表的概念及结构

2.2 接口的实现

3. 动手实现单链表

3.1 重写SeqList接口方法

3.2 在当前链表头部添加节点（头插）

3.3 在第index位置添加节点（任意位置）

3.4 在当前链表尾部添加节点（尾插）

3.5 删除第index个节点

3.6 检验index是否合法

3.7 删除第一个值element的节点

3.8 删除所有值element的节点

3.9 修改第index个节点的值为element

3.10 获取第index个节点的值

3.11 判断链表中是否存在element

3.12 获取element在链表中的位置

3.13 打印链表

4. SingleLinkedList整体实现

4.1 SingleLinkedList类

4.2 Test类

4.3 测试结果

1. ArrayList的缺陷

由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为 O(n) ，效率比较低，因此 ArrayList 不适合做任意位置插入和删除比较多的场景 。因此： java集合中又引入了LinkedList ，即链表结构。

2. 链表

2.1 链表的概念及结构

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

实际中链表的结构非常多样，以下情况组合起来就有6 种链表结构：

（1） 单向或者双向

（2） 带头或者不带头

（3）循环或者非循环

虽然有这么多的链表的结构，但是我们重点掌握两种 :

无头单向非循环链表 ： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结构 ，如哈希桶、图的邻接表等等。

无头双向链表 ：在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表。

2.2 接口的实现

使用泛型更好的接收不同数据类型（一个顺序表只能接受一种类型！）

public interface SeqList<E> {
    //    尾插
    void add(E element);
    //    将 element 插入到 index 位置
    void add(int index,E element);
 
    //    删除 index 位置元素<返回删除的值
    E removeByIndex(int index);
    //    删除第一个值element的元素
    void removeByValue(E element);
    //    删除所有值element的元素
    void removeAllValue(E element);
 
    //    将下标 index 位置元素设置为 element，返回替换前的值
    E set(int index,E element);
    E get(int index);
    //    判断 o 是否在其中
    boolean contains(E element);
    int indexOf(E element);
    int size();
    void clear();
 
}

3. 动手实现单链表

实现没有头节点的单链表

3.1 重写SeqList接口方法

public class SingleLinkedList<E> implements SeqList<E> {

    private Node head;//头节点

    private int size; // 节点个数，保存的元素个数

    //类的定义，内部类,对外部完全隐藏
    private class Node {
        E val;//保存的元素
        Node next;//下节车厢的位置
        Node(E val) {
            this.val = val;
        }
    }
    public void addFrist(E val){ }
    @Override
    public void add(E element) { }
    @Override
    public void add(int index, E element) { }
    @Override
    public E removeByIndex(int index) { }
    @Override
    public void removeByValue(E element) { }
    @Override
    public void removeAllValue(E element) { }
    @Override
    public E set(int index, E element) { }
    public boolean rangeCheck(int index){ }
    @Override
    public E get(int index) { }
    @Override
    public boolean contains(E element) { }
    @Override
    public int indexOf(E element) { }
    @Override
    public int size() { }
    @Override
    public void clear() { }
    @Override
    public String toString() { }
}

3.2 在当前链表头部添加节点（头插）

无论链表中是否包含节点，头插法都是这相同的代码处理~

public void addFrist(E val){
        // 要插入一个元素，首先要产生一个新节点
        Node node = new Node(val);
        // 将当前节点插入到链表中
        node.next = head;
        // 更新head的引用，指向当前的新节点
        head = node;
        size ++;
    }

    public void add(E element) {
        add(size,element);
    }

思考一下，①和②的代码顺序能换吗?

先执行2再执行1，原来的链表就丢了，head指向新节点，最终链表中只剩下新节点了~

3.3 在第index位置添加节点（任意位置）

（1）判断index是否合法

（2）判断没有前驱，没有就是头插

（3）寻找index位置的前驱节点（单链表的核心操作就是在寻找前驱节点!）

（4）先将新节点和原先位置节点连接

（5）再更改原先prev的引用

public void add(int index, E element) {
        // 1.base case，边界判断
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index illegal!");
        }
        // 2.判断没有前驱的情况
        if (index == 0) {
            addFrist(element);
            return;
        }
        // 3.确实是中间位置的插入，寻找待插入位置的前驱！
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        // prev走到待插入位置的前驱
        Node node = new Node(element);
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

3.4 在当前链表尾部添加节点（尾插）

第一种方法

（1）走到当前链表的最后

（2）让最后节点的next指向这个新添加的节点

第二种方法

调用add()方法，index等于size就是在链表末尾插入了

    public void addLast(E val){
        Node prev = head;
        while (prev.next != null){
            prev = prev.next;
        }
        Node node = new Node(val);
        prev.next = node;
    }


    //尾插2
    @Override
    public void add(E element) {
        add(size,element);
    }

3.5 删除第index个节点

（1）判断index是否合法（链表为空则index不合法）

（2）判断没有前驱，没有就是头节点删除

（3）寻找index位置的前驱节点

（4）将前驱节点和原先位置的下一个节点连接

public E removeByIndex(int index) {
        // 1.base case
        if (!rangeCheck(index)) {
            throw new IllegalArgumentException("remove index illegal!");
        }
        // 2.判断头节点的删除问题
        if (index == 0) {
            Node node = head;
            head = head.next;
            node.next = null;
            size --;
            return node.val;
        }
        // 3.现在确实是中间位置的删除
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        Node node = prev.next;
        prev.next = node.next;
        node.next = null;
        size --;
        return node.val;
    }

3.6 检验index是否合法

public boolean rangeCheck(int index){
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

3.7 删除第一个值element的节点

（1）判断链表是否为空

（2）判断头节点是否是待删除的节点，是的话删除完就方法返回

（3）寻找element节点的前驱节点（凡是用到引用的位置，一定要保证这个引用不为空）

（4）将前驱节点和原先位置的下一个节点连接

这里的图和3.5 中的图一致

 public void removeByValue(E element) {
        // 1.base case
        if (head == null) {
            return;
        }
        // 2.判断头节点恰好是待删除的节点
        if (head.val.equals(element)) {
            head = head.next;
            size --;
            return;
        }
        // 3.此时头节点不为空其一定不是待删除的结点
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.val.equals(element)) {
                // prev走到了待删除节点的前驱位置
                prev.next = prev.next.next;
                size --;
                return;
            }
            prev = prev.next;
        }
        // 4.链表中没有待删除的节点
        System.out.println("当前链表中不存在值为" + element + "的节点");
    }