单链表头尾指针

 容器接口

 
import java.io.Serializable;
import java.util.stream.Stream;
 
public interface Container extends Serializable {
 
    /**
     * 求容器大小
     */
    int size();
 
    /**
     * 容器是否包含元素
     *
     * @param e 要判断的元素
     * @return true表示容器中存在该元素
     */
    boolean contains(E e);
 
    /**
     * 清空容器
     */
    void clear();
 
    /**
     * 容器是否为空
     *
     * @return true表示为空
     */
    default boolean isEmpty() {
        return size() == 0;
    }
 
    /**
     * 流，数据源不能被修改，所以要屏蔽所有修改方法？？臃肿！
     */
    default Stream stream() {
        throw new UnsupportedOperationException();
    }
}

 链表实现类

/**
 * 单链表
 * 链表类：头指针、尾指针、链表大小
 *
 * @param 
 */
public class MyLinkedList implements Container {
    private Node head = new Node<>(null);
    private Node tail = head;
    private int size;
 
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList<>();
        // 向单链表中插入元素
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(5);
        list.addLast(6);
        list.addLast(7);
        System.out.println(list);
        // 移除第一个元素
        list.removeFirst();
        list.removeFirst();
        list.addFirst(2);
        System.out.println(list);
        // 移除最后一个元素
        list.removeLast();
        list.removeLast();
        list.addFirst(1);
        list.addLast(6);
        System.out.println(list);
        // 清空链表
        list.clear();
        System.out.println(list);
        list.addFirst(1);
        System.out.println(list);
    }
 
    /**
     * 在链表头插入，头尾指针互相不干涉，头指针永远指向头节点，尾指针永远指向尾节点
     *
     * @param e 插入的元素
     */
    public void addFirst(E e) {
        if (e == null) {
            throw new NullPointerException();
        }
        Node node = new Node<>(e);
        node.next = head.next;
        head.next = node;
        size++;
    }
 
    /**
     * 向链表尾部添加元素
     *
     * @param e 要添加的元素
     */
    public void addLast(E e) {
        if (e == null) {
            throw new NullPointerException();
        }
        size++;
        Node newTail = new Node<>(e);
        tail.next = newTail;
        tail = newTail;
    }
 
    /**
     * 移除链表最后一个元素
     */
    public void removeLast() {
        if (isEmpty()) {
            return;
        }
        size--;
        Node temp = head;
        while (temp.next != tail) {
            temp = temp.next;
        }
        temp.next.elem = null; // 删除最后一个元素
        temp.next = null; // 修改倒数第二个元素指针指向空
        tail = temp;
    }
 
    /**
     * 移除链表第一个元素
     */
    public void removeFirst() {
        if (isEmpty()) {
            return;
        }
        size--;
        head.next.elem = null;
        head = head.next;
    }
 
    @Override
    public int size() {
        return size;
    }
 
    private Node getNode(E e) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
            if (e.equals(temp.elem)) {
                return temp;
            }
        }
        return null;
    }
 
    @Override
    public boolean contains(E e) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
            if (e.equals(temp.elem)) {
                return true;
            }
        }
        return false;
    }
 
    @Override
    public void clear() {
        head.next = null;
        tail = head;
        size = 0;
    }
 
    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }
        final StringBuilder sb = new StringBuilder();
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
            sb.append(",").append(temp.elem);
        }
        sb.insert(1, "[").append("]");
        return sb.substring(1);
    }
 
    private static class Node {
        E elem;
        transient Node next;
 
        public Node(E elem) {
            this.elem = elem;
        }
 
        public Node(E elem, Node next) {
            this.elem = elem;
            this.next = next;
        }
 
        @Override
        public String toString() {
            return elem.toString();
        }
    }
}