Java链表 (1) ：实现链表的基本操作

独断万古他化

发布于 2026-01-15 13:06:53

110

文章被收录于专栏：Java 攻略Java 攻略

1. 链表的概念与结构

1.1 什么是链表

链表是一种物理存储结构上不连续，但是在逻辑结构上连续存储的结构。数据元素的逻辑顺序通过链表中的引用链接次序实现。举个例子，链表在逻辑顺序上的结构可类似于火车，每一节车厢代表一个节点，节点之间通过引用链接起来。

如图就是一个链表结构，可以看出在物理上并不连续，而在逻辑上我们认为是连续的。

1.2 链表的结构

实际中的链表结构非常多样，那么以下组合起来可以有8中链表结构：

单向或者双向

带头或者不带头

循环或者非循环

我们主要掌握的有两种结构：

无头单向非循环链表：结构简单，这种结构在笔试面试中出现较多。
无头双向链表：在Java集合框架中LinkedList底层实现就是无头双向循环链表。

2. 链表的实现

这里主要实现的是无头单向非循环链表，通过自我实现一遍链表，可以更好的理解链表这一结构。首先给出要实现的链表接口：

public interface ILinkedList {

    //头插法
    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();
}

定义一个类来实现这个接口，并且在这个类中使用静态内部类来定义表示一个节点类，节点应该包含的属性有元素值和下一个节点的引用。同时定义一个head节点。（注意：此头代表的是链表中第一个节点，并不是哨兵位的头节点）

public class MyLinkedList implements ILinkedList{

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

        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;
}

2.1 头插法

定义一个新节点存储插入的元素首先要考虑链表是否为空，也就是head是否为null，如果为空，那么新节点就是头节点。如果不为空，再进行头插，也就是将新节点的next域指向head节点，然后再将head改为新节点。

	public void addFirst(int data) {
        ListNode node = new ListNode(data);

        if(head == null){
            head = node;
            return;
        }

        node.next = head;
        head = node;
    }

2.2 尾插法

定义一个新节点node存储插入的元素首先要考虑链表是否为空，也就是head是否为null，如果为空，那么新节点就是尾节点。

若不为空，则需要先遍历链表得到最后一个节点，并将最后一个节点的next域指向新节点node。

	public void addLast(int data) {
        ListNode node = new ListNode(data);

        if(head == null){
            head = node;
            return;
        }

        ListNode cur = head;
        while(cur.next != null){
            cur = cur.next;
        }

        cur.next = node;
    }

2.3 任意位置插⼊

规定将第一个节点为0号下标首先判断给出的位置index是否合理，如果小于0，或者大于链表长度则直接返回。如果给出的index刚好为0，那么对应头插法，调用头插函数即可；如果index刚好为链表长度size()，那么对应尾插法，调用尾插函数即可。

若都不是，需要遍历得到index位置的前一个节点，将新节点next域指向index下标节点，将index前一个节点的next域指向新节点。注意这个顺序不能调换，否则将丢失index及后面所有的链表节点。

	public void addIndex(int index, int data) {
        if(index < 0 || index > size()){
            return;
        }

        if(index == 0){
            addFirst(data);
            return;
        }

        if(index == size()){
            addLast(data);
            return;
        }

        ListNode node = new ListNode(data);
        ListNode cur = searchNode(index);
        
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode searchNode(int index){
        ListNode cur = head;

        int count = 0;
        while(count != index - 1){
            cur = cur.next;
        }
        
        return cur;
    }

2.4 查找关键字key是否在单链表当中

通过遍历时判断当前节点的val域是否等于key即可

	public boolean contains(int key) {
        ListNode cur = head;

        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }

        return false;
    }

2.5 删除节点

2.5.1 删除第⼀次出现关键字为key的节点

首先判断链表是否为空，如果空则不需要删除。判断删除的是否为头节点，若是头，则将head节点指向下一个节点。删除时要保证链表的连续，因此删除当前节点后，还需要将上一个节点与下一个节点连接起来。可以使用两个指针，一个用来找到key值节点，一个用来找到key值节点的前驱节点（此节点用以连接key值节点的下一个节点）。

	public void remove(int key) {
        if(head == null){
            System.out.println("链表为空，无法删除...");
            return;
        }

        if(head.val == key){
            head = head.next;
            return;
        }

        ListNode prev = searchPrev(key);
        if(prev == null){
            System.out.println("找不到" + key + "值，没有要删除的节点");
            return;
        }
        ListNode cur = prev.next;
        prev.next = cur.next;
    }

    /**
     * 找到key值节点的前驱节点
     * @param key
     * @return
     */
    private ListNode searchPrev(int key){
        ListNode cur = head;
        while(cur.next !=  null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }

        return null;
    }

2.5.2 删除所有值为key的节点

首先判断是否为空。可以用双指针来删除，指针1为head，指针2为head.next，判断指针2的值域是否等于key，若等于则将指针1的节点域指向指针2的节点域，同时指针2向后移动；若不等于，两个指针都同时向后移动。例如图所示：

此时头节点并未判断，只需对头节点单独判断处理即可。

	public void removeAllKey(int key) {
        if(head == null){
            System.out.println("没有要删除的节点...");
            return;
        }

        ListNode prev = head;
        ListNode cur = head.next;

        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                cur = cur.next;
                prev = prev.next;
            }
        }

        if(head.val == key){
            head = head.next;
        }
    }

2.6 得到单链表的长度

可以定义一个count，通过遍历使count++，最后count的值就是链表的长度

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

2.7 删除整个链表

简单粗暴的方式：直接将头节点head的next域置为空。第二种，遍历使得每一个节点都置为空；最后将head置为空。

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

2.8 遍历链表

遍历输出当前节点val的值，最后判断节点为空则结束遍历

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

以上就是链表的一些基本操作了。

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

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

链表