由于其底层是一段连续空间，当在 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 + "的节点");
    }

3.8 删除所有值element的节点

（1）判断链表是否为空

（2）判断头节点是否是待删除的节点

（3）判断链表是否已经删除完，删除完就返回

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

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

（6）如果下一个节点不是待删除的节点，prev指向下一个节点

（7）循环执行步骤（5）、（6）直到链表走完(prev.next != null)


public void removeAllValue(E element) {
        // 1.base case
        if(head == null) {
            return;
        }
        // 2.若头节点就是待删除的节点且出现连续的待删除节点
        while (head != null && head.val.equals(element)) {
            head = head.next;
            size --;
        }
        if (head == null) {
            // 整个链表已经删除完了
            return;
        }
        // 3.头节点一定不是待删除的节点且链表不为空！
        // prev一定指向的不是待删除的结点~
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.val.equals(element)) {
                // 此时prev就是待删除节点的前驱
                prev.next = prev.next.next;
                size --;
            }else {
                // 只有后继节点不是待删除的结点才能移动prev引用!
                prev = prev.next;
            }
        }
    }

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

（1）判断index是否合法

（2）寻找index位置的节点

（3）将节点的val修改为element


public E set(int index, E element) {
//        1.索引的合法性校验
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("set index illegal!");
        }
        // 从前向后遍历走到index对应的元素
        Node x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        // 此时x就落在了待修改的节点位置
        E oldVal = x.val;
        x.val = element;
        return oldVal;
    }
    public boolean rangeCheck(int index){
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

3.10 获取第index个节点的值


public E get(int index) {
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("get index illegal!");
        }
        Node x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x.val;
    }

3.11 判断链表中是否存在element


 public boolean contains(E element) {
        Node cur = head;
        while (cur.next != null){
            if (cur.val.equals(element)){
                return true;
            }
        }
        return false;
    }

3.12 获取element在链表中的位置


public int indexOf(E element) {
        int count = 0;
        Node cur = head;
        while (cur.next != null){
            if (cur.val.equals(element)){
                return count;
            }
            count++;
            cur = cur.next;
        }
        return -1;
    }

3.13 打印链表


public String toString() {
        StringBuilder sb = new StringBuilder();
        // 从当前链表的第一个节点开始向后遍历，直到走到尾结点为止
        // 第一个节点head
        for(Node x = head;x != null;x = x.next){
            sb.append(x.val);
            sb.append("->");
            if(x.next == null){
                // 此时temp走到了尾结点
                sb.append("NULL");
            }
        }
        return sb.toString();
    }

3.14 获取链表长度以及清空链表


    public int size() {
        return this.size;
    }
 
    @Override
    public void clear() {
        Node cur = this.head;
        Node curNext = null;
        while (cur != null) {
            curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }

4. SingleLinkedList整体实现

4.1 SingleLinkedList类


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;
        }
    }
    //  ------------------------------------------------
 
//    头插，在当前链表头部添加元素  head在移动
    public void addFrist(E val){
        // 要插入一个元素，首先要产生一个新节点
        Node node = new Node(val);
        // 将当前节点插入到链表中
        node.next = head;
        // 更新head的引用，指向当前的新节点
        head = node;
        size ++;
    }
 
 
    @Override
    public void add(E element) {
        add(size,element);
    }
 
    @Override
    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 ++;
    }
 
    @Override
    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;
    }
 
    @Override
    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 + "的节点");
    }
 
    @Override
    public void removeAllValue(E element) {
        // 1.base case
        if(head == null) {
            return;
        }
        // 2.若头节点就是待删除的节点且出现连续的待删除节点
        while (head != null && head.val.equals(element)) {
            head = head.next;
            size --;
        }
        if (head == null) {
            // 整个链表已经删除完了
            return;
        }
        // 3.头节点一定不是待删除的节点且链表不为空！
        // prev一定指向的不是待删除的结点~
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.val.equals(element)) {
                // 此时prev就是待删除节点的前驱
                prev.next = prev.next.next;
                size --;
            }else {
                // 只有后继节点不是待删除的结点才能移动prev引用!
                prev = prev.next;
            }
        }
    }
 
//    修改
    @Override
    public E set(int index, E element) {
//        1.索引的合法性校验
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("set index illegal!");
        }
        // 从前向后遍历走到index对应的元素
        Node x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        // 此时x就落在了待修改的节点位置
        E oldVal = x.val;
        x.val = element;
        return oldVal;
    }
    public boolean rangeCheck(int index){
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }
 
    @Override
    public E get(int index) {
        if(!rangeCheck(index)){
            throw new IllegalArgumentException("get index illegal!");
        }
        Node x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x.val;
    }
 
    @Override
    public boolean contains(E element) {
        Node cur = head;
        while (cur.next != null){
            if (cur.val.equals(element)){
                return true;
            }
        }
        return false;
    }
 
    @Override
    public int indexOf(E element) {
        int count = 0;
        Node cur = head;
        while (cur.next != null){
            if (cur.val.equals(element)){
                return count;
            }
            count++;
            cur = cur.next;
        }
        return -1;
 
    }
 
    @Override
    public int size() {
        return this.size;
    }
 
    @Override
    public void clear() {
        Node cur = this.head;
        Node curNext = null;
        while (cur != null) {
            curNext = cur.next;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        // 从当前链表的第一个节点开始向后遍历，直到走到尾结点为止
        // 第一个节点head
        for(Node x = head;x != null;x = x.next){
            sb.append(x.val);
            sb.append("->");
            if(x.next == null){
                // 此时temp走到了尾结点
                sb.append("NULL");
            }
        }
        return sb.toString();
    }
}

4.2 Test类


public class SingleLinkedTest {
    public static void main(String[] args) {
        SingleLinkedList<Integer> list = new SingleLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(9);
        list.add(10);
        list.add(10);
        list.add(6);
        list.add(10);
        list.add(5);
        list.add(7);
        list.add(10);
        list.add(10);
 
        System.out.println(list);
        System.out.println("------------添加测试-----------");
        System.out.println("从链表尾部添加99");
        list.add(99);
        System.out.println("添加index为2，element为88");
        list.add(2,88);
        System.out.println(list);
        System.out.println("-----------删除测试------------");
        System.out.println("删除index为0");
        list.removeByIndex(0);
        System.out.println("删除元素为6");
        list.removeByValue(6);
        System.out.println("删除所有10");
        list.removeAllValue(10);
        System.out.println(list);
        System.out.println("-----------其他------------");
        System.out.println("查看是否包含10这个元素");
        System.out.println(list.contains(10));
        System.out.println("修改index为3，element为19");
        list.set(3,19);
        System.out.println("获取index为3的元素");
        System.out.println(list.get(3));
        System.out.println(list);
        System.out.println("获取element为88的index");
        System.out.println(list.indexOf(88));
        System.out.println("获取顺序表长度");
        System.out.println(list.size());
        System.out.println("清空顺序表");
        list.clear();
        System.out.println(list + "...");
    }
}

4.3 测试结果

下一篇：双向链表

双向链表

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/码创造者/article/detail/905209

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

1. ArrayList的缺陷