自定义LinkedList

原理

链表是一种物理存储结构上不连续的存储结构，是由存储元素的结点连接而成。每一个节点都包含前一个节点的引用，后一个节点的引用和节点存储的值。

链表分为单向链表和双向链表：

• 单向链表：只能通过前一个节点找到后一个节点或者只能通过后一个节点找到前一个节点，关联关系是单向的；
• 双向链表：既能通过前一个节点找到后一个节点，同时也能通过后一个节点找到前一个节点，关联关系是双向的。

Java原生的LinkedList是采用双向链表实现的。

示例：自定义实现LinkedList 自定义链表的每一个节点所对应的数据结构

public class Node {
    E item; //当前节点中存储的对象
    Node next;   //下一个节点
    Node prev;   //上一个节点

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

自定义链表类：

public class LinkedList {
    private Node first;
    private Node last;
    private int size;

    /**
     * 从链表的尾部添加
     *
     * @param str
     * @return
     */
    boolean add(String str) {
        Node node = new Node(last, str, null);
        if (first == null) {
            first = node;
            last = node;
        } else {
            last.next = node;
            last = node;
        }
        size++;
        return true;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer("[");

        Node temp = first;
        if(temp != null) {
            while (temp != null) {
                sb.append(temp.item).append(", ");
                temp = temp.next;
            }
            return sb.substring(0, sb.length() - 2)+"]";
        }
        return "";
    }

    /**
     * 获取第index位置处的元素
     *
     * @param index 下标，从0开始
     * @return
     */
    Node getNode(int index) {
        if (index  size) {
            throw new IllegalArgumentException();
        }
        Node temp = first;

        for (int i = 0; i