本文共 3249 字，大约阅读时间需要 10 分钟。

链表的基础知识与操作

前言

链表是一种重要的数据结构，是树和图的基础。如果你想深入理解树和图的实现，先从链表开始是一个不错的选择。链表看似简单，但它蕴含着很大的知识。如果能完成以下几种基本操作，链表的学习者将不会再感到困难。

链表是什么

如果你在百度百科或课本上看到链表的定义，可能会觉得有些冗长。这时候我们可以用简单的示意图来理解。链表由若干个节点组成，节点主要包含两个部分：data域和next域。

• data域：存储节点的数据。
• next域：存储下一个节点的地址。

链表的终止标志是next == null。

想要更直观地理解这个概念，可以画个简单的图。假设每个节点都有两个插槽，一个用来存放数据，另一个用来指向下一个节点。当我们有了头节点，就可以通过next域依次访问所有节点。这就是链表的基本工作原理。

创建链表

理解了链表的概念后，创建一个链表其实非常简单。首先定义一个节点类，然后创建头节点即可。

class Node {
    public Object data;
    public Node next;  // 构造方法需要传入data
    Node(Object data) {
        this.data = data;
    }
    @Override
    public String toString() {
        return "Node{" + "data=" + data + '}';
    }
}

创建链表的步骤如下：

public class SingleLinkedList {
    private final Node header = new Node(null);
}

这样一个简单的链表就创建完成了。接下来我们可以模拟一些链表的基本操作。

核心操作

链表的核心操作包括插入节点、删除节点、修改节点以及遍历链表。这些操作的实现方法是非常基础的，但如果不掌握，就很难深入学习树和图。

展示链表

public void showList() {
    Node temp = header;
    if (header.next == null) {
        System.out.println("链表为空");
        return;
    }
    while (true) {
        if (temp.next != null) {
            temp = temp.next;
            System.out.println("当前节点是：" + temp);
        } else {
            break;
        }
    }
}

新增节点

public void add(Node element) {
    Node temp = header;
    while (true) {
        if (temp.next != null) {
            temp = temp.next;
        } else {
            temp.next = element;
            break;
        }
    }
}

删除节点

public void deleteByIndex(int index) {
    if (header.next == null) {
        System.out.println("链表为空");
        return;
    }
    Node temp = header;
    for (int i = 0; i < index; i++) {
        if (temp.next != null) {
            temp = temp.next;
            System.out.println("当前遍历节点是：" + temp);
        } else {
            System.out.println("链表长度不足，程序结束");
            break;
        }
    }
    // 到达目标节点
    if (temp.next != null) {
        temp.next = temp.next.next;
    } else {
        System.out.println("无法删除最后一个节点");
    }
}

修改节点

public void updateNodeByIndex(Node newNode, int index) {
    if (index <= 0) {
        System.out.println("索引必须大于0");
        return;
    }
    if (header.next == null) {
        System.out.println("链表为空");
        return;
    }
    Node temp = header;
    for (int i = 0; i <= index; i++) {
        if (i != index) {
            if (temp.next != null) {
                temp = temp.next;
                System.out.println("继续遍历，当前节点是：" + temp);
            } else {
                System.out.println("链表长度不足，程序结束");
                break;
            }
        } else {
            // 修改当前节点的data
            temp.data = newNode.data;
            break;
        }
    }
}

获取节点

public Node getIndexElement(int index) {
    if (header.next == null) {
        System.out.println("链表为空");
        throw new RuntimeException("空链表！");
    }
    Node temp = header;
    for (int i = 0; i <= index; i++) {
        if (i != index) {
            if (temp.next != null) {
                temp = temp.next;
            } else {
                System.out.println("链表长度不足，无法获取目标节点");
                break;
            }
        } else {
            return temp;
        }
    }
    return null;
}

总结

本节内容涉及链表的基础知识以及增删改查操作。通过这些操作，你已经掌握了链表的核心技能。接下来可以学习链表的其他高级操作，比如逆序链表、分割链表等。在实际项目中，链表虽然不再常用，但对理解其他数据结构等于学习一门新语言。