Java数据结构之简单链表的定义与实现方法示例

Java数据结构之简单链表的定义与实现方法示例

什么是链表

链表是线性数据结构的一种，它是由一个个节点构成的，每个节点包含两个部分，一个是数据，另一个是指向下一个节点的引用，通俗的说，就像火车一样，每节火车都是一个节点，而每车头都指向下一节车厢。

链表的定义

Java中常用链表有单向链表和双向链表，单向链表每个节点只有一个指向下一个节点的引用，而双向链表每个节点还有一个指向前一个节点的引用。

下面是一个单向链表节点的定义：

class Node {
    int data;  //节点数据
    Node next; //指向下一个节点
    Node(int data) {
        this.data = data;
        next = null;
    }
}

链表的实现方法

在链表尾部插入新节点

以下是单向链表的代码示例，单向链表插入新节点时可以先找到链表的最后一个节点，然后将新节点插入到这个最后一个节点的后面：

class LinkedList {
    Node head; //头节点
    LinkedList() {
        head = null;
    }
    void insert(int data) {
        Node newNode = new Node(data); //创建新节点
        if (head == null) { //如果是空链表
            head = newNode;
        } else { //如果不是空链表
            Node lastNode = head;
            while (lastNode.next != null) { //找到最后一个节点
                lastNode = lastNode.next;
            }
            lastNode.next = newNode; //将新节点插入到最后一个节点的后面
        }
    }
}

在链表中间插入新节点

以下是单向链表的代码示例，单向链表插入新节点时可以先找到链表的某个节点，然后将新节点插入到这个节点的后面，同时需要注意，插入新节点时必须要让它指向后面那个节点，否则链表会被破坏：

class LinkedList {
    Node head; //头节点
    LinkedList() {
        head = null;
    }
    void insert(int data, int position) {
        Node newNode = new Node(data); //创建新节点
        if (position == 0) { //特殊情况，插入到头节点的前面
            newNode.next = head;
            head = newNode;
        } else {
            Node prevNode = null;
            Node currNode = head;
            int index = 0;
            while (currNode != null && index != position) {
                prevNode = currNode;
                currNode = currNode.next;
                index++;
            }
            if (index != position) { //如果position太大，就不能插入
                throw new RuntimeException("invalid position!");
            }
            prevNode.next = newNode; //将新节点插入到某个节点的后面
            newNode.next = currNode; //让新节点指向后面那个节点
        }
    }
}

总结

以上是关于Java简单链表的定义与实现方法示例，我们可以通过以上的代码进行学习和实践，掌握链表数据结构的基本操作。