手写LinkedList

组成结构

• 成员变量：LinkedList类本身包含了一个头节点first，一个尾节点last，和一个记录链表大小的变量size。
• 构造方法：无参构造方法和带参构造方法。
• 常用方法：
  1. – add(E element): 将元素添加到链表的尾部。
  2. – add(int index, E element): 在指定位置插入元素。
  3. – get(int index): 获取指定位置的元素。
  4. – contains(E element): 判断链表是否包含指定元素。
  5. – indexOf(E element): 返回指定元素在链表中的索引，若不存在则返回-1。
  6. – size(): 获取链表的大小。
  7. 私有方法getNode(int index)，用于获取指定位置的节点。

代码实现

下面是一个比较完整功能的LinkedList的实现：

public class LinkedList<E> {

    private Node<E> first; // 头节点
    private Node<E> last; // 尾节点
    private int size; // 链表的大小

    // 内部类，表示链表的节点
    private static class Node<E> {
        E element; // 节点存储的元素
        Node<E> prev; // 指向前驱节点的指针
        Node<E> next; // 指向后继节点的指针

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

    // 添加元素到链表尾部
    public void add(E element) {
        Node<E> newNode = new Node<>(element, last, null);
        if (last == null) {
            first = newNode;
        } else {
            last.next = newNode;
        }
        last = newNode;
        size++;
    }

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

    // 获取指定位置的元素
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> node = getNode(index);
        return node.element;
    }

    // 判断链表是否包含指定元素
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    // 返回指定元素在链表中的索引，若不存在则返回-1
    public int indexOf(E element) {
        int index = 0;
        if (element == null) {
            for (Node<E> node = first; node != null; node = node.next) {
                if (node.element == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (Node<E> node = first; node != null; node = node.next) {
                if (element.equals(node.element)) {
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    // 获取链表的大小
    public int size() {
        return size;
    }

    // 获取指定位置的节点
    private Node<E> getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        if (index < size / 2) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }
}