Java如何实现自定义LinkedList类

在Java中，LinkedList是java.util包中的一个常用集合类，它实现了List接口和Deque接口，提供了双向链表的实现。虽然Java标准库中的LinkedList已经非常强大且功能丰富，但理解其内部实现原理对于深入学习数据结构与算法非常有帮助。本文将详细介绍如何从零开始实现一个自定义的LinkedList类。

1. 链表的基本概念

链表（Linked List）是一种线性数据结构，它通过节点（Node）来存储数据，每个节点包含数据域和指针域。指针域指向下一个节点，从而将多个节点串联起来形成一个链表。链表可以分为单向链表、双向链表和循环链表等。

• 单向链表：每个节点只有一个指针，指向下一个节点。
• 双向链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
• 循环链表：链表的最后一个节点指向第一个节点，形成一个环。

本文将实现一个双向链表。

2. 自定义LinkedList类的设计

为了实现一个自定义的LinkedList类，我们需要定义以下几个部分：

1. 节点类（Node）：用于存储数据和前后节点的引用。
2. LinkedList类：包含链表的头节点、尾节点以及链表的基本操作方法。

2.1 节点类的实现

首先，我们需要定义一个节点类Node，它包含三个属性：

• data：存储节点的数据。
• prev：指向前一个节点的引用。
• next：指向后一个节点的引用。

class Node<E> {
    E data;
    Node<E> prev;
    Node<E> next;

    public Node(E data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

2.2 LinkedList类的实现

接下来，我们实现LinkedList类。该类包含以下属性和方法：

• 属性：

  • head：指向链表的第一个节点。
  • tail：指向链表的最后一个节点。
  • size：链表的长度。

• 方法：

  • add(E element)：在链表末尾添加一个元素。
  • add(int index, E element)：在指定位置插入一个元素。
  • remove(int index)：删除指定位置的元素。
  • get(int index)：获取指定位置的元素。
  • size()：返回链表的长度。
  • isEmpty()：判断链表是否为空。
  • clear()：清空链表。

public class MyLinkedList<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size;

    public MyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // 在链表末尾添加元素
    public void add(E element) {
        Node<E> newNode = new Node<>(element);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }

    // 在指定位置插入元素
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index == size) {
            add(element);
        } else {
            Node<E> newNode = new Node<>(element);
            Node<E> current = getNode(index);
            newNode.prev = current.prev;
            newNode.next = current;
            if (current.prev != null) {
                current.prev.next = newNode;
            } else {
                head = newNode;
            }
            current.prev = newNode;
            size++;
        }
    }

    // 删除指定位置的元素
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> current = getNode(index);
        if (current.prev != null) {
            current.prev.next = current.next;
        } else {
            head = current.next;
        }
        if (current.next != null) {
            current.next.prev = current.prev;
        } else {
            tail = current.prev;
        }
        size--;
        return current.data;
    }

    // 获取指定位置的元素
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return getNode(index).data;
    }

    // 获取链表的长度
    public int size() {
        return size;
    }

    // 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 清空链表
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    // 获取指定位置的节点
    private Node<E> getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> current;
        if (index < size / 2) {
            current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
        } else {
            current = tail;
            for (int i = size - 1; i > index; i--) {
                current = current.prev;
            }
        }
        return current;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node<E> current = head;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(", ");
            }
            current = current.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

2.3 测试自定义LinkedList类

为了验证我们的自定义LinkedList类是否正确实现，我们可以编写一些测试代码。

public class Main {
    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();

        // 添加元素
        list.add(10);
        list.add(20);
        list.add(30);
        System.out.println("After adding elements: " + list);

        // 在指定位置插入元素
        list.add(1, 15);
        System.out.println("After inserting 15 at index 1: " + list);

        // 删除元素
        list.remove(2);
        System.out.println("After removing element at index 2: " + list);

        // 获取元素
        System.out.println("Element at index 1: " + list.get(1));

        // 获取链表长度
        System.out.println("Size of the list: " + list.size());

        // 判断链表是否为空
        System.out.println("Is the list empty? " + list.isEmpty());

        // 清空链表
        list.clear();
        System.out.println("After clearing the list: " + list);
    }
}

运行上述代码，输出结果如下：

After adding elements: [10, 20, 30]
After inserting 15 at index 1: [10, 15, 20, 30]
After removing element at index 2: [10, 15, 30]
Element at index 1: 15
Size of the list: 3
Is the list empty? false
After clearing the list: []

3. 总结

通过本文的介绍，我们实现了一个自定义的LinkedList类。虽然Java标准库中的LinkedList已经非常强大，但通过自己动手实现一个链表，我们可以更深入地理解链表的内部工作原理。这对于学习数据结构和算法非常有帮助。

在实际开发中，我们通常会直接使用Java标准库中的LinkedList，因为它经过了充分的测试和优化。然而，理解其内部实现原理仍然是非常重要的，尤其是在面试或需要自定义数据结构时。

希望本文对你理解Java中的链表实现有所帮助！