Java链表数据结构及其简单使用方法解析

概述

链表是一种非线性结构，由一系列节点按照顺序连接而成。每个节点由数据域和指针域组成，数据域用于存储数据，指针域用于指向下一个节点或者上一个节点。在Java中，链表有多种实现方式，常见的有单向链表、双向链表等。

单向链表的实现

以下是一个单向链表的实现代码示例：

public class Node {
    private int data; // 数据域
    private Node next; // 指针域

    public Node(int data) {
        this.data = data;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node getNext() {
        return next;
    }

    public int getData() {
        return data;
    }
}

public class LinkedList {
    private Node head; // 链表头节点

    public Node add(int data) { // 在链表末尾添加节点
        Node node = new Node(data);
        if (head == null) { // 如果链表为空，则将新节点作为头节点
            head = node;
        } else {
            Node current = head;
            while (current.getNext() != null) { // 找到链表末尾的节点
                current = current.getNext();
            }
            current.setNext(node); // 将新节点添加到链表末尾
        }
        return node; // 返回新节点
    }

    public void remove(int data) { // 移除某个节点
        if (head == null) {
            return;
        }

        if (head.getData() == data) { // 如果需要移除的节点是头节点
            head = head.getNext();
            return;
        }

        Node current = head;
        while (current.getNext() != null) { // 查找需要移除的节点
            if (current.getNext().getData() == data) {
                current.setNext(current.getNext().getNext());
                return;
            }
            current = current.getNext();
        }
    }
}

使用方式示例：

LinkedList list = new LinkedList();
list.add(1);
Node node = list.add(2);
list.add(3);
list.remove(2); // 移除节点2

双向链表的实现

以下是一个双向链表的实现代码示例：

public class DoubleNode {
    private int data; // 数据域
    private DoubleNode previous; // 上一个节点
    private DoubleNode next; // 下一个节点

    public DoubleNode(int data) {
        this.data = data;
    }

    public void setPrevious(DoubleNode previous) {
        this.previous = previous;
    }

    public DoubleNode getPrevious() {
        return previous;
    }

    public void setNext(DoubleNode next) {
        this.next = next;
    }

    public DoubleNode getNext() {
        return next;
    }

    public int getData() {
        return data;
    }
}

public class DoubleLinkedList {
    private DoubleNode head; // 链表头节点

    public DoubleNode add(int data) { // 在链表末尾添加节点
        DoubleNode node = new DoubleNode(data);
        if (head == null) { // 如果链表为空，则将新节点作为头节点
            head = node;
        } else {
            DoubleNode current = head;
            while (current.getNext() != null) { // 找到链表末尾的节点
                current = current.getNext();
            }
            current.setNext(node); // 将新节点添加到链表末尾
            node.setPrevious(current); // 设置新节点的上一个节点
        }
        return node; // 返回新节点
    }

    public void remove(int data) { // 移除某个节点
        if (head == null) {
            return;
        }

        if (head.getData() == data) { // 如果需要移除的节点是头节点
            head = head.getNext();
            if (head != null) {
                head.setPrevious(null); // 设置新头节点的上一个节点为null
            }
            return;
        }

        DoubleNode current = head;
        while (current.getNext() != null) { // 查找需要移除的节点
            if (current.getNext().getData() == data) {
                current.setNext(current.getNext().getNext());
                if (current.getNext() != null) {
                    current.getNext().setPrevious(current); // 设置下一个节点的上一个节点为当前节点
                }
                return;
            }
            current = current.getNext();
        }
    }
}

使用方式示例：

DoubleLinkedList list = new DoubleLinkedList();
list.add(1);
list.add(2);
DoubleNode node = list.add(3);
list.remove(2); // 移除节点2