Java实现自定义LinkedList类的示例代码

下面是Java实现自定义LinkedList类的攻略：

1. LinkedList类的概述

LinkedList是Java API中提供的一种线性数据结构，实现了List和Deque接口，底层使用双向链表实现。LinkedList的特点是支持插入和删除操作，但查找操作比较慢。对于需要频繁增删元素而不需要随机访问的场景，使用LinkedList比较合适。

2. 自定义LinkedList类的实现

Java中提供的LinkedList类已经比较完善，但我们还是可以模仿它的实现，自己编写一个自定义的LinkedList类。以下是自定义LinkedList类的示例代码：

public class MyLinkedList<E> {

    private Node<E> head;
    private int size;

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

        Node(E element, Node<E> prev, Node<E> next) {
            this.data = element;
            this.prev = prev;
            this.next = next;
        }
    }

    public MyLinkedList() {
        head = new Node<>(null, null, null);
        head.prev = head;
        head.next = head;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void add(E element) {
        add(size, element);
    }

    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> newNode = new Node<>(element, null, null);
        Node<E> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }

        newNode.prev = p;
        newNode.next = p.next;
        p.next.prev = newNode;
        p.next = newNode;

        size++;
    }

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }

        E element = p.next.data;
        p.next.next.prev = p;
        p.next = p.next.next;

        size--;

        return element;
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }

        Node<E> p = head.next;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }

        return p.data;
    }
}

3. 具体说明

自定义LinkedList类包含一个内部类Node，表示双向链表中的一个节点，其中data表示节点的数据，prev和next表示节点的前驱和后继。头节点head的data值为null，prev和next均指向自身，表示空链表。size表示链表中元素的个数。

构造函数中初始化头节点head，并使其prev和next均指向自身。

size()方法返回链表中元素的个数。

isEmpty()方法判断链表是否为空。

add(E element)方法向链表末尾添加一个元素。

add(int index, E element)方法在指定位置添加一个元素。该方法先判断索引位置是否合法，然后依次找到要添加位置的前驱节点p，创建一个新节点newNode，并将newNode的前驱和后继指向p和p的后继节点，然后将p的后继节点的前驱指向newNode，p的后继指向newNode。

remove(int index)方法移除指定位置的元素。该方法先判断索引位置是否合法，然后依次找到要移除位置的前驱节点p，将要移除的元素保存下来，将p的后继节点的后继节点的前驱指向p，p的后继指向p的后继节点的后继节点。

get(int index)方法获取指定位置的元素。该方法先判断索引位置是否合法，然后依次找到指定位置的节点p，返回其data值。

4. 示例

MyLinkedList<String> list = new MyLinkedList<>();
list.add("a");
list.add("b");
list.add("c");
System.out.println(list.get(1)); // 输出 b
list.remove(0);
System.out.println(list.get(0)); // 输出 b
System.out.println(list.size()); // 输出 2

以上示例中，我们创建了一个自定义的LinkedList对象list，向其中添加了三个元素a、b、c，并输出了下标为1的元素b的结果。然后移除了下标为0的元素a，并输出了下标为0的元素b的结果，以及list的元素个数2。

阅读剩余 65%