[Java数据结构与算法]模拟实现链表

木井巳

发布于 2025-12-16 09:32:22

1340

一、为什么需要链表：ArrayList 的缺陷

ArrayList 底层是基于 动态数组 的：

优点：支持随机访问，时间复杂度 O(1)。
缺点：插入/删除需要整体搬移元素，时间复杂度 O(n)，效率低。

示例：

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(1, 100);  // 在下标1插入100

这一步操作会导致后续元素整体后移，性能消耗大。

因此，在插入/删除元素频繁的情况下，ArrayList 并不适合，这就需要链表。

二、链表的基本概念和分类

2.1 链表的概念与结构

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

与数组的连续存储不同，链表的每个元素（节点）都包含两部分：

数据域：存储实际数据
指针域：存储下一个节点的地址引用

2.2 链表的分类

分类方式：

单向链表 / 双向链表
带头 / 不带头
循环 / 非循环

在 Java 中，LinkedList 的底层实现是 无头双向循环链表。

三、链表的模拟实现

3.1 单向无头链表的模拟实现

单链表的基本方法如下：

public void display()	打印链表
public int size()	获取链表长度
public void addFirst(int data)	在第一个元素前插入新元素
public void addLast(int data)	在链表末尾插入新元素
public void addAt(int pos,int data)	在pos位置处插入
public boolean contains(int data)	判断是否包含某个值
public void remove(int data)	删除第一次出现的某个值
public void clear()	清空链表

首先我们编写一个MyList类，然后将节点类ListNode作为MyList的内部类：

public class MyList {
    static class ListNode {
        public int val;        //链表的值域
        public ListNode next;  //链表的next域，默认初始化为null
    
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;    //指向链表的第一个节点
}

display方法的实现十分简单，我们只需要遍历链表就可以做到。

与顺序表不同的是，链表在内存中的存储不是连续的，因此十分依赖next域找到下一个节点。

实现思路：

定义一个指针先指向head，让指针遍历整个链表（为了保持head指向第一个节点）
如果直接使用head遍历，等结束循环后head就为空了

具体实现如下：

public void display() {
    ListNode cur = head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

size方法的实现思路：

也是直接遍历链表
用一个计数器统计节点的个数
注意当链表没有元素时，要返回0

具体实现如下：

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

addFirst方法是在第一个节点之前插入新节点，实现思路是：

将新节点的next域指向当前的head
将head指向新节点，该新节点就成为了第一个节点

具体实现如下：

public void addFirst(int data) {
    ListNode toAdd = new ListNode(data);    //要插入的新节点
    toAdd.next = head;
    head = toAdd;
}

addLast方法是在链表末尾插入新节点，由于单链表没有指向前一个节点的prev域，因此我们通常用遍历的方式找到链表找到最后一个节点：

遍历链表找到最后一个节点
将最后一个节点的next域指向新节点
注意当链表为空时，新节点是第一个节点，不能遍历
还要注意链表的最后一个节点的next域是null，循环条件需要改变

具体实现如下：

public void addLast(int data) {
    ListNode toAdd = new ListNode(data);
    if (head == null) {
        head = toAdd;    //当链表为空时，让toAdd成为第一个节点
        return;
    }
    ListNode cur = head;
    while (cur.next != null) {    //注意这里条件是next域不为空
        cur = cur.next;
    }
    cur.next = toadd;
}

addAt方法的实现稍微有些复杂，需要检查pos的合法性，思路：

首先判断链表是否为空、判断pos的合法性（异常）
然后在pos都合法的情况下，判断pos是否为0或者size（可以使用头插或尾插）
若是中间，先让遍历指针走到pos-1位置（前一个结点），然后先把toAdd的next指向pos-1位置结点的next，使得toAdd可以指向后一个结点，再将pos-1位置结点的next指向toAdd（顺序不可换，否则找不到pos位置的结点）

具体实现如下：

public void addAt(int pos, int data) {
    try {
        if (head == null) return;
        checkPos(pos);
        if (pos == 0) {
            addFirst(data);
        } else if (pos == len) {
            addLast(data);
        } else {
            ListNode toAdd = new ListNode(data);
            ListNode cur = head;
            while (pos-1 != 0) {
                cur = cur.next;
                pos--;
            }
            toAdd.next = cur.next;    //先让toAdd的next指向cur结点的后一个结点
            cur.next = toAdd;
        }
    } catch (PositionIllegalException e) {
        e.printStackTrace();
    }
}

其中 checkPos方法和异常的编写如下：

private void checkPos(int pos) {
    int len = size();
    if (pos<0 || pos>len) {
        throw new PositionIllegalException("Illegal position!");
    }
}

public class PositionIllegalException extends RuntimeException {
    public PositionIllegalException() {
        super();
    }
    public PositionIllegalException(String message) {
        super(message);
    }
}

contains方法十分简单，只需要遍历一遍链表即可：

若找到对应的data值，则返回true
若没找到data，则返回false

具体实现如下：

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

romove方法的实现思路：

首先判断链表是否为空
然后判断链表的第一个节点是否需要被删除，若是，则删掉然后结束
接着遍历链表，遍历时要判断遍历指针的下一个结点的值是否为对应data值
若是要删除的，用一个指针记录该节点，然后将该节点的next给遍历指针的next（否则找不到后续结点）

具体实现如下：

public void remove(int data) {
    if (head == null) return;
    if (head.val == data) {
        head = head.next;    //检查第一个节点
        return;
    }
    ListNode cur = head;
    while (cur != null) {
        if (cur.next.val == data) {
            ListNode next = cur.next;
            cur.next = next.next;
            return;
        }
        cur = cur.next;
    }
}

最后的 clear方法的实现思路：

使用两个指针：一个指针用来将结点的next置空，一个指针用于记录下一个节点的位置
注意将指向第一个结点的head置空，建议放在最后操作

具体实现如下：

public void clear() {
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = null;
        cur = next;
    }
    head = null;        //将head置空
}

以上，我们就模拟实现了单向无头链表。

3.2 双向无头链表的模拟实现

双向链表的基本方法与单链表的基本一致：

public void display()	打印链表
public int size()	获取链表长度
public void addFirst(int data)	在第一个元素前插入新元素
public void addLast(int data)	在链表末尾插入新元素
public void addAt(int pos,int data)	在pos位置处插入
public boolean contains(int data)	判断是否包含某个值
public void remove(int data)	删除第一次出现的某个值
public void clear()	清空链表

在实现双向链表的方法前，我们先定义一个 MyLinkedList类，然后将结点类 ListNode作为内部类；与单链表不同的是，节点类有 prev域和 next域，并且我们有一个引用 tail 指向双向链表的最后一个结点：

public class MyLinkedList {
    static class ListNode {
        public int val;
        public ListNode prev;    //prev域，指向该节点的前一个结点
        public ListNode next;    //next域，指向该节点的后一个结点
        
        class MyLinkedList(int val) {
            this.val = val;
        }

    public ListNode head;        //指向双向链表的第一个结点
}

display方法、size方法和 contains方法的实现思路与单链表的实现思路完全一致，因此不再过多赘述，具体实现如下：

public void display() {
    ListNode cur = head;
    while (cur != null) {
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

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

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

addFirst方法的实现思路：

首先判断链表是否为空，若为空，head 和 tail 都要指向新节点
然后将 head 所指向的结点的地址给新节点的 next；将 head 所指向结点的 prev 指向新节点
最后让 head 指向新节点即可

具体实现如下：

public void addFirst(int data) {
    ListNode toAdd = new ListNode(data);
    if (head == null) {
        head = tail = toAdd;
        return;
    }
    toAdd.next = head;
    head.prev = toadd;
    head = head.prev;
}

addLast方法的实现思路与 addFirst方法的大致一样：

public void addLast(int data) {
    ListNode toAdd = new ListNode(data);
    if (head == null) {
        head = tail = toAdd;
        return;
    }
    tail.next = toAdd;
    toAdd.prev = tail;
    tail = tail.next;
}

addAt方法前半部分都是与单链表一致的，当确定 pos 合法且既不是第一个也不是最后一个的时候：

遍历链表，这次可以直接走到 pos 位置指向对应的结点
然后将该结点的 prev 给新节点的 prev；再将该节点的地址给新节点的 next
接着将该节点的前一个结点的 next 改成新节点的地址
最后将该节点的 prev 改成新节点的地址

具体实现如下：

public void addAt(int pos, int data) {
    try {
        if (head == null) return;
        checkPos(pos);
        if (pos == 0) {
            addFirst(data);
        } else if (pos == len) {
            addLast(data);
        } else {
            ListNode toAdd = new ListNode(data);
            ListNode cur = head;
            while (pos != 0) {
                cur = cur.next;
                pos--;
            }
            toAdd.prev = cur.prev;
            toAdd.next = cur;
            cur.prev = toAdd;
            toAdd.prev.next = toAdd;
        }
    } catch (PositionIllegalException e) {
        e.printStackTrace();
    }
}

其中 checkPos方法和异常的编写如下：

private void checkPos(int pos) {
    int len = size();
    if (pos<0 || pos>len) {
        throw new PositionIllegalException("Illegal position!");
    }
}

public class PositionIllegalException extends RuntimeException {
    public PositionIllegalException() {
        super();
    }
    public PositionIllegalException(String message) {
        super(message);
    }
}

remove方法的实现思路：

遍历链表查找对应要删除的结点
找到之后，把遍历指针的 next 给上一个节点的 next，实现删除操作
如果该节点是第一个节点，直接删掉然后让 head 指向下一个节点；如果该节点是最后的结点，删掉后让 tail 指向上一个结点；若该节点是中间的某个结点，则把该节点（已被删除）的下一个节点的 prev 指向已被删除节点的上一个节点即可
特殊情况：该链表只有一个节点，意味着该节点同时也是被 head 所指向的，可以在删除第一个节点时同时操作：将该节点的 prev 置为空即可（next 已经是空了）

具体实现如下：

public void remove(int data) {
    ListNode cur = head;
    
    while (cur != null) {
        if (cur.val == data) {
            if (cur == head) {        //当toRemove是第一个节点
                head = head.next;
                if (head == null) {    //处理只有一个节点的情况
                    head.prev = null;
                }
            } else {
                cur.prev.next = cur.next;
                if (cur.next == null) {    //当toRemove是最后的节点
                    tail = tail.prev;
                } else {                    //当toRemove是中间某个节点
                    cur.next.prev = cur.prev;
                }
            }
            return;
        }
        cur = cur.next;
    }
}

clear方法的实现思路：

使用两个指针，遍历操作，一个一开始指向 head 所指向的节点，一个指向第一个指针的下一个节点
第一个指针将节点的 next 置空，第二个指针将节点的 prev 置空
注意循环条件是第二个节点不能为空
最后要记得将 head 和 tail 置空

具体实现如下：

public void clear() {
    ListNode cur = head;
    ListNode next = cur.next;
    
    while (next != null) {
        cur.next = null;    //将节点next置空
        next.prev = null;   //将节点prev置空
        cur = next;
        next = next.next;
    }
    head = null;
    tail = null;
}

至此，链表的模拟实现已经完成啦 ~ 恭喜你！

完

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

原始发表：2025-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

链表