单向链表

单向链表，每次添加，向链表尾追加元素。第一个节点为head节点，每次添加的时候，找到最后一个节点，将最后一个节点的next指向新添加的元素。

先拿到head节点，每次只需要通过next，就能找到下一个节点

public class SingleLinkedList<E> {
    // 头结点
    Node head;
    // 最后一个节点
    Node last;

    public void add(E e) {
        Node node = new Node(null, e, null);
        // 头结点为空，说明还没有添加过元素
        if (head == null) {
            head = node;
        } else {
            // 最后一个节点的next指向新节点
            last.next = node;
        }
        // 新节点变为last
        last = node;
    }

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

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

class Demo1 {
    public static void main(String[] args) {
        SingleLinkedList<String> list = new SingleLinkedList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        System.out.println();
    }
}

单向链表，添加元素后，数据结构如下：

 

 双向链表

双向链表，添加元素的时候，向末尾追加。保证前一个元素的next指向下一个元素，下一个元素的pre指向上一个元素。first记录一个元素，last记录最后一个元素。

public class DoubleLinkedList<E> {
    Node first;
    Node last;

    public void add(E e) {
        Node node = new Node(null, e, null);
        // 头结点为空，说明还没有添加过元素
        if (first == null) {
            first = node;
        } else {
            node.prev = last;
            // 最后一个节点的next指向新节点
            last.next = node;

        }
        // 新节点变为last
        last = node;
    }

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

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

class Demo2 {
    public static void main(String[] args) {
        DoubleLinkedList<String> list = new DoubleLinkedList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        System.out.println();
    }
}

双向链表，添加元素后，数据结构如下：