模拟实现链表的功能

用户11820508

发布于 2026-01-12 15:43:18

1.什么是链表？

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

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

单向或者双向

带头或者不带头

循环或者非循环

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

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

2.如何定义一个链表？

无头单向链表的每一个节点有两个属性，分别是值val和存储下一个节点的地址。我们来回顾内部类的定义：当一个事物的内部，还有一个部分需要一个完整的结构进行描述，而这个内部的完整的结构又只为外部事物提供服务，那么这个内部的完整结构最好使用内部类这里我们把每个节点定义为内部类正合适

    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {

            this.val = val;
        }
    }
    public ListNode head;//定义头节点

此时的head：

注：这里的next中存储的下一个节点的位置，所以类型是ListNode；使用构造方法初始化的时候，仅仅初始化val的值，next节点默认为null

3.链表的模拟实现

这里我们模拟实现的是无头单向非循环链表

// 1、无头单向非循环链表实现
 public class SingleLinkedList {
    //头插法
    public void addFirst(int data){
   }
    //尾插法
    public void addLast(int data){
   }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
   }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        return false;
   }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
   }
    //删除所有值为key的节点
    public void removeAllKey(int key){
   }
    //得到单链表的长度
    public int size(){
        return -1;
   }
 
    public void clear() {
   }
     
    public void display() {}
 }

（1）头插addFirst的实现

解析： 假设有这样一组链表，我们想把node节点添加到该链表的头节点

实现效果：

创建需要头插的node节点
我们需要把node节点的next指向下一个结点的地址
把node节点变为头节点即可

public void addFirst(int val) {
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
    }

（2）尾插addLast的实现

解析： 实现效果：

思路：

创建需要尾插的node节点
通过循环找到链表的最后一个节点，将原本链表最后节点的next的null变为所要尾插节点的地址

操作：

空链表怎么处理？ 首先我们判断链表是否是空链表，如果是，直接将node节点变为头节点即可
怎么找到链表的最后一个节点？ 通过while循环遍历来找到链表的最后一个节点，如果没找到就一直循环移动到下一个节点，如果找到了，我们将node的地址赋值给最后一个节点的next
为什么要定义cur节点来遍历？ 我们定义一个cur节点来存储head节点，以防遍历后数据丢失
循环的条件？ while循环的条件，判断每个节点的next是否为空，为空说明找到了最后一个节点，也就是cur.next != null

public void addLast(int val) {
        ListNode cur = head;
        ListNode node = new ListNode(val);
        if(head == null) {
            head = node;
            return;
        }
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

（3）addIndex()的实现

此方法实现在任意位置插入节点

实现效果：

思路：

找到所要插入位置的前一个节点
将node的next指向cur的next节点；将前一个结点cur的next指向node的地址

操作：

如何处理传入的下标不合法问题？ 这里我们定义一个异常处理，当下标小于0，或者大于链表长度时，抛出异常，并用try catch()语句来进行异常的捕获
插入的位置在头部和尾部怎么处理？ 对应头插法和尾插法，直接调用写好的方法即可
如何找到前一个结点？ 我们可以专门写一个方法来实现此操作，定义一个count变量来表示循环次数，只需循环到index-1的位置即可
如何进行连接？ 将node的next指向cur的next节点；将前一个结点cur的next指向node的地址。需要注意的是需要先将添加的节点与后面的节点进行绑定，再对前面的进行绑定

public void addIndex(int index, int val) {
        //1.判断合法性
        try {
            checkIndex(index);
        }catch (IndexNotLegalException e) {
            e.printStackTrace();
        }
        //2.index == 0  || index == size()
        if(index == 0) {
            addFirst(val);
            return;
        }
        if(index == size()) {
            addLast(val);
            return;
        }
        //找到前一个结点
        ListNode cur = findIndexSubOne(index);
        //4. 进行连接
        ListNode node = new ListNode(val);
        node.next = cur.next;
        cur.next = node;
    }
    private ListNode findIndexSubOne(int index) {
        ListNode cur = head;
        int count = 0;
        while (count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
    private void checkIndex(int index) throws IndexNotLegalException{
        if(index < 0 || index > size()) {
            throw new IndexNotLegalException("index不合法");
        }
    }

IndexNotLegalException.java 文件

public class IndexNotLegalException extends RuntimeException {
    public IndexNotLegalException() {
    }

    public IndexNotLegalException(String message) {
        super(message);
    }
}

（4）contains()的实现

此方法判断链表中是否包含val值，包含则返回true，否则返回false 思路：

遍历链表，与每个节点的val值进行对比

操作：

循环的条件？ 因为需要将每个节点的val值进行比较，所以条件为cur != null；
如果找到就返回true，如果没有就继续遍历，遍历完好没找到就返回false；

    public boolean contains(int val) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

（5）remove()的实现

此方法是删除第一次出现关键字为val的节点实现效果：

思路：

找到所要删除节点的前一个节点，将该节点与所要删除节点的后一个节点进行拼接来完成删除操作

操作：

如何找到所要删除节点的前一个节点？ 当cur.next.val == 34（所要删除的节点）时，定义一个del节点，cur的下一个节点就是del，ListNode del = cur.next; 为什么不能用cur.val而用cur.next.val来对比判断所要删除的节点呢？ 因为此时是一个单向的链表当我们的cur走到要删除的节点是就不能修改前面的节点了，这样就无法实现改变前一个结点的val值了

如何进行删除？ 我们定义所要删除的节点为del，将cur的next指向del的next，即：cur.next = del.next;（cur.next = cur.next.next）
循环条件是什么？ 判断每个节点的val是否是所要删除的val，循环条件是cur.next != null，通过cur.next.val就可以访问到下一个节点的val值。 为什么不能通过cur != null来作为循环条件呢？ 在我们寻找删除结点的前一个节点时，我们是通过cur.next.val == 34（所要删除的节点）进行值的对比来寻找，如果我们通过cur != null来判断，当cur走到最后一个节点时，next为null，此时cur.next.val就会出现空指针异常
为什么需要特殊判断头节点？ 因为我们是通过cur.next.val来开始判断的，并没有判断头节点的val值所以我们需要进行特殊判断， head = head.next;

public void remove(int val) {
        if(head == null) {
            return;
        }
        if(head.val == val) {
            head = head.next;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == val) {
                ListNode del = cur.next;
                cur.next = del.next;
                return;
            }
            cur = cur.next;
        }
    }

（6）removeAllKey()的实现

此方法是删除所有出现关键字为val的节点操作：

cur代表当前需要删除的节点 prev代表当前需要删除节点cur的前驱节点
如果找到需要删除的节点，prev.next = cur.next;cur = cur.next;

如果没找到所要删除的节点，移动prev节点prev = cur;再移动cur判断下一个节点cur = cur.next;

最后的效果

如何处理头节点就是要删除的节点的情况？

先将头节点以外的删除再来考虑头节点位置即可 if(head.val == val) { head = head.next; }

也可先考虑头节点的情况，while循环判断

public void removeAllKey(int val) {
        //1. 判空
        if (head == null) {
            head = head.next;
        }
        //2. 定义prev 和 cur
        ListNode prev = head;
        ListNode cur = head.next;
        //3.开始判断并且删除
        while (cur != null) {
            if (cur.val == val) {
                //找到了
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
        //4.处理头节点
        if(head.val == val) {
            head = head.next;
        }
    }

（7）size()的实现

遍历链表，用count计数即可

public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

（8）clear()的实现

将每一个节点的next置空即可，注意这里需要单独把头节点置空

public void clear() {
        ListNode cur = head;
        while (cur != null) {
            ListNode curN = cur.next;
            //cur.val = null;
            cur.next = null;
            cur = curN;
        }
        head = null;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-09，如有侵权请联系 cloudcommunity@tencent.com 删除

public