Java数据结构之链表的概念及结构

链表的概念

链表是一种非顺序存储的容器，它由一个个结点组成，每个结点包含两部分，数据域和指针域。数据域是存储数据的部分，指针域是指向下一个结点的位置。

相比于数组，链表插入和删除操作的时间复杂度更低，但是访问元素时需要遍历整个链表，时间复杂度相对较高。

链表的结构

链表结构包含两个重要的部分：结点和链表。

结点（Node）：每个结点包含两个属性，一个存储数据元素的数据域（Data），一个指向下一个结点的指针域（Next）。

链表（LinkedList）：包含头结点和尾结点。头结点（head）的指针域指向第一个结点，尾结点（tail）的指针域为空。

链表的元素可以插入、删除和查找。在查找元素时，需要从头结点开始遍历，直到找到目标元素。

以下是一个示例代码：

class Node {
    int data;
    Node next;

    // 构造方法
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head, tail;

    // 头插法
    public void addAtHead(int data) {
        Node new_node = new Node(data);
        // 如果链表为空
        if(head == null) {
            head = new_node;
            tail = new_node;
            return;
        }
        new_node.next = head;
        head = new_node;
    }

    // 尾插法
    public void addAtTail(int data) {
        Node new_node = new Node(data);
        // 如果链表为空
        if(tail == null) {
            head = new_node;
            tail = new_node;
            return;
        }
        tail.next = new_node;
        tail = new_node;
    }

    // 遍历链表
    public void printList() {
        Node curr_node = head;
        System.out.print("LinkedList: ");
        while (curr_node != null) {
            System.out.print(curr_node.data + " ");
            curr_node = curr_node.next;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addAtTail(1);
        list.addAtHead(2);
        list.addAtTail(3);
        list.addAtHead(4);
        list.printList();
    }
}

输出结果为：

LinkedList: 4 2 1 3 

上述代码实现了链表的添加数据元素（头插和尾插）和遍历操作。