数据结构之单链表详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之单链表详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

😽博主CSDN主页：小源_😽

🖋️个人专栏：《数据结构》🖋️

😀努力追逐大佬们的步伐~

1.前言

2. 链表

2.1 链表的概念及结构

2.2 链表的结构分类

3. 无头单向非循环链表的模拟实现

3.1 定义IList接口

3.2 重写IList中的方法

3.3 display（打印方法）

3.4 size方法

3.5 contains方法

3.6 addFirst头插法

3.7 addLast尾插法

3.8 addIndex任意插法

3.9 remove方法

3.10 removeAllKey方法

3.11 clear方法

4.小结

1.前言

我们都知道，ArrayList的底层是一段连续的空间，在ArrayList任意位置插入或者删除元素时，就需要将后续元素整体往前或往后搬移，时间复杂度为O(n)，效率比较低，并且在插入元素遇到扩容时，有可能会浪费空间，所以ArrayList不适合做任意位置插入和删除比较多的场景。因此，java集合中又引入了LinkedList，即链表结构。

本章重点：

本文着重讲解了链表的结构和无头单向非循环链表的实现。

2. 链表

2.1 链表的概念及结构

链表是一种物理结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。我们举个小火车例子就可以轻松理解这句话：

链表类似火车一样，它是由一个一个节点/结点（车厢）组成的。我们可以把头节点比作火车头，把后面的节点比作火车的车厢，把利用每个节点中存放的下一个节点的地址来连接每一个节点比作火车之间的铁钩。

链表的每个节点都分为两个部分，一个是val/dadta域（用来存放值），另一个是next域（用来存放下一个节点的地址）。最后一个节点的next域为null。

注意：

1.从上图可以看出，链式结构在物理上不一定是连续的，但是 逻辑上是连续的。

2.现实中的节点一般都是从堆上申请出来的。

3.从堆上申请的空间，是按照一定的策略来分配到，两次申请的空间可能连续，也可能不连续。

2.2 链表的结构分类

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

1.单向后者双向

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

2.带头后者不带头

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

3. 循环或者非循环

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

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

2.无头双向链表： 结构复杂，一般用来单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然复杂，但是在后面模拟实现的时候就能发现它有很多特点，反而变简单了。

3. 无头单向非循环链表的模拟实现

3.1 定义IList接口

public interface IList {
    //头插法
    void addFirst(int data); 
    //尾插法
    void addLast(int data);
    //任意位置插入,第一个数据节点为0号下标
    void addIndex(int index,int data);
    //查找是否包含关键字key是否在单链表当中
    boolean contains(int key);
    //删除第一次出现关键字为key的节点
    void remove(int key);
    //删除所有值为key的节点
    void removeAllKey(int key);
    //得到单链表的长度
    int size();
    //清空
    void clear();
    //打印
    void display();
}

3.2 重写IList中的方法

定义一个MySingleList类来实现IList接口，并且重写IList中的方法

（选中IList,快捷键为Ctrl+O）：

首先需要定义一个内部类作为节点的类，用static修饰，代表只能在当前类中使用。

接着定义一个头节点head。

然后创建一些新的节点，将head指向第一个节点的位置

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

public class MySinglelList implements IList{
    //节点的内部类
    static class ListNode {
        //val域
        public int val;
        //next域
        public ListNode next;
        //构造方法，接收放在val域的值
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
    
    //创建新的节点
    public void createList() {
        ListNode node1 = new ListNode(12);
        ListNode node2 = new ListNode(23);
        ListNode node3 = new ListNode(34);
        ListNode node4 = new ListNode(45);
        ListNode node5 = new ListNode(56);
        
        //修改当前节点的next值为指定的节点
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        //用头节点指向第一个节点的位置
        this.head = node1;
    }
    
    
    @Override
    public void addFirst(int data) {

    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }
}

3.3 display（打印方法）

首先我们要知道如何遍历链表:

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

@Override
    public void display() {
        ListNode cur = this.head;
        //判断是否遍历完了链表，当cur指向null时就说明遍历完了
        while (cur != null) {
            System.out.print(cur.val + " ");
            //cur就是这样从当前位置走到下一个节点的位置
            cur = cur.next;
        }
        System.out.println();
    }

3.4 size方法

求链表个数/长度

@Override
    public int size() {
        //定义一个计数器
        int count = 0;
        //同样的，利用cur遍历链表 
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

3.5 contains方法

指的是查找是否包含关键字key是否在单链表当中。

@Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        //遍历链表
        while (cur != null) {
            //如果cur.val等于key返回true
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

3.6 addFirst头插法

指的是将插入的节点存放在链表的第一个位置。

1.实例化一个节点

2.改变插入节点的next

3.改变head

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表


@Override
    public void addFirst(int data) {
        //1.先创建一个新的节点
        ListNode node = new ListNode(data);
        //如果头节点为空，直接将头节点指向新创建的节点
        if (this.head == null) {
            this.head = node;
        } else {
            //2.如果头节点不为空，将node的next指向head
            node.next = this.head;
            //3.然后将head指向刚刚插在最前面的节点
            this.head = node;
        }
    }

3.7 addLast尾插法

指的是将插入的节点存放在链表的第一个位置。

1.实例化一个节点

2.找到最后一个节点cur

3.cur.next = node;

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

@Override
    public void addLast(int data) {
        //先创建一个新的节点
        ListNode node = new ListNode(data);
        //我们最好不移动头节点head的位置，所以用cur指向head，用来遍历链表
        ListNode cur = this.head;
        //如果头节点为空，直接将头节点指向新创建的节点
        if (this.head == null) {
            this.head = node;
        } else {
            //如果头节点不为空，要先找到链表的尾巴，然后再进行连接
            //遍历cur，cur不为空时，会指向下一个节点，下一个节点为null时，停止
            while (cur.next != null) {
                cur = cur.next;
            }
            //此时cur已经指向最后一个节点，现在将 cur.next 指向 node
            cur.next = node;
        }
    }

分析：头插法的时间复杂度为O(1)，尾插法的时间复杂度为O(N)

结论：1.如果想让cur停在最后一个节点的位置，while循环条件为 cur.next != null

2.如果想把整个链表的节点都遍历完，while循环条件为 cur != null

3.8 addIndex任意插法

指的是在任意位置插入一个节点。

1.让cur走(index - 1)步

2.node.next = cur.next;

cur.next = node;

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

@Override
    public void addIndex(int index, int data) {
        if(index < 0 || index > size()) {
            //可以抛出自定义异常
            System.out.println("index位置不合法：" + index);
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        //用cur接收前驱
        ListNode cur = searchPrev(index);
        //实例化一个新的节点
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

    //找到要插入位置的前驱
    public ListNode searchPrev(int index) {
        int count = 0;
        ListNode cur = this.head;
        //遍历链表，让cur走(index - 1)步
        while (count != (index - 1)) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

注意：在绑定一个节点的时候，一定要先绑定后面的这个节点

假如顺序反过来:

cur.next = node;

node.next = cur.next;

则会导致node.next找不到cur.next

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

3.9 remove方法

指的是删除第一次出现关键字为key的节点。

以下代码中 del 是要删除的节点，cur 是 del 的前驱

1.找到前驱（就是要删除的节点的前一个节点）

2.判断返回值是否为空

3.删除（cur.next = del.next以后，del所指向的节点因为没有人指向，所以会被系统自动回收）

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表




@Override
    public void remove(int key) {
        //头节点为空，直接返回
        if (this.head == null) {
            return;
        }
        
        //如果头节点的val等于key，将头节点改为头节点的下一个节点
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }

        //1.找到前驱
        //用cur接收
        ListNode cur = findPrev(key);
        //2.判断返回值是否为空
        if (cur == null) {
            System.out.println("没有你要删除的对象");
            return;
        }
        //3.删除
        //如果不为空，del就是要删除的对象
        ListNode del = cur.next;
        cur = del.next;
    }

    /**
     * 找到key的前一个节点的地址
     * @param key
     * @return
     */
    private ListNode findPrev(int key) {
        ListNode cur = this.head;
        //遍历链表
        //注意while循环条件不能是cur != null,因为cur会走到最后一个节点的后面(null)，
        //后面的代码需要用到cur,null没有next，会报空指针异常
        while (cur.next != null) {
            //如果cur的下一个节点的val等于key，说明cur就是我们要找的前驱
            if (cur.next.val == key) {
                //此时cur就是要删除的节点的前驱
                return cur;
            }
            cur = cur.next;
        }
        return cur;
    }

3.10 removeAllKey方法

指的是删除所有值为key的节点。

1.定义一个前驱指向头节点

2.定义cur指向head.next

3.如果cur.val = key 则删除，然后cur的位置向后移动一个节点

4.如果cur.val ！= key，则prev和cur的位置同时向后移动一个节点

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

@Override
    public void removeAllKey(int key) {
        if (this.head == null) {
            return;
        }

        //定义一个要删除的节点的前驱指向head
        ListNode prev = head;
        //定义一个cur指向head.next，cur是要删除的节点
        ListNode cur = head.next;
        while (cur != null) {
            //遍历链表，如果cur.val == key，删除
            if (cur.val == key) {
                prev.next = cur.next;
            } else {
                //如果cur.val ！= key，继续下一个节点
                prev = prev.next;
            }
            cur = cur.next;
        }
        
        //如果头节点的val值为key，直接把head的指向改为head.next即可
        if (head.val == key) {
            head = head.next;
        }
    }

3.11 clear方法

指的是删除链表的所有节点。

1.直接把头节点置空的方法太粗糙，我们下面学习更细节的写法：

2.遍历链表，把每个节点的 val = null, next = null 即可

数据结构之单链表详解,数据结构,数据结构,学习,java,idea,链表

@Override
    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            //用curNext记录cur.next，因为接下来cur.next将会改变为null
            //  我们要用curNext来继续遍历链表
            ListNode curNext = cur.next;
            //cur.val = 0;
            cur.next = null;
            cur = curNext;
        }
        head = null;
    }