链表是非常常用的数据结构，常见的链表有单链表、双向链表和双向循环链表。

一个比一个复杂，但实际运用中，越往后越好用。

下面我们使用java分别实现：

一、单链表

单链表特点：
1.单链表的head结点指向第一个数据节点，存数据,没有tail结点
2.单链表的每个节点都有next指针指向下一个节点，但是没有指针指向前驱节点

/**
 * @Author : wangbin
 * @Date : 2/7/2022 11:17 AM
 * @Description: 单链表特点：
 * 1.单链表的head结点指向第一个数据节点，存数据,没有tail结点
 * 2.单链表的每个节点都有next指针指向下一个节点，但是没有指针指向前驱节点
 */
public class SinglyLinkedList<E> implements LinkedList<E> {
    private int size;
    private Node<E> head;

    public SinglyLinkedList() {
    }

    @Override
    public int size() {
        return size;
    }

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

    @Override
    public boolean add(E e) {
        if (head == null) {
            head = new Node<>(e, null);
            size++;
            return true;
        }
        Node<E> cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = new Node<>(e, null);
        size++;
        return true;
    }

    @Override
    public boolean remove(E e) {
        Node<E> cur = head;
        Node<E> curPrev = head;
        while (!cur.item.equals(e) && cur.next != null) {
            curPrev = cur;
            cur = cur.next;
        }
        if (cur.next == null) {
            return false;
        }
        curPrev.next = cur.next;
        size--;
        return true;
    }

    @Override
    public E get(int index) {
        Node<E> curNode = getNode(index);
        return curNode.item;
    }

    private Node<E> getNode(int index) {
        checkIndex(index);
        Node<E> curNode = head;
        int curIdx = 0;
        while (curNode.next != null && curIdx != index) {
            curIdx++;
            curNode = curNode.next;
        }
        return curNode;
    }

    private Node<E> getPrevNode(int index) {
        checkIndex(index);
        Node<E> curNode = head;
        int curIdx = 0;
        while (curIdx != index - 1) {
            curIdx++;
            curNode = curNode.next;
        }
        return curNode;
    }

    @Override
    public E set(int index, E element) {
        checkIndex(index);
        Node<E> node = getNode(index);
        E oldElement = node.item;
        node.item = element;
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        if (!isPositionIndex(index)) {
            throw new IndexOutOfBoundsException();
        }
        Node<E> prevNode = getPrevNode(index);
        Node<E> curNode = prevNode.next;
        prevNode.next = new Node<>(element, curNode);
        size++;
    }

    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    @Override
    public E remove(int index) {
        if (index == 0) {
            E item = head.item;
            head = head.next;
            size--;
            return item;
        }
        Node<E> prevNode = getPrevNode(index);
        Node<E> curNode = prevNode.next;
        prevNode.next = curNode.next;
        size--;
        return curNode.item;
    }

    @Override
    public int indexOf(E o) {
        int curIndex = 0;
        for (Node<E> curNode = head; curIndex < size; curNode = curNode.next) {
            if (curNode.item.equals(o)) {
                return curIndex;
            }
            curIndex++;
        }
        return -1;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int nextIndex = 0;

            @Override
            public boolean hasNext() {
                return nextIndex < size;
            }

            @Override
            public E next() {
                return get(nextIndex++);
            }
        };
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }

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

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

二、双向链表

双向链表的特点：
 1.双向链表既有head节点，也有tail节点；
 2.head节点指向第一个节点，head.prev==null；
 3.tail节点指向最后一个节点，tail.next==null;
 4.相比双向循环链表，双向链表没有使用哨兵，所以需要处理复杂的边界条件

/**
 * @Author : wangbin
 * @Date : 2/7/2022 11:18 AM
 * @Description: 双向链表的特点：
 * 1.双向链表既有head节点，也有tail节点；
 * 2.head节点指向第一个节点，head.prev==null；
 * 3.tail节点指向最后一个节点，tail.next==null;
 * 相比双向循环链表，双向链表没有使用哨兵，所以需要处理复杂的边界条件
 */
public class DoublyLinkedList<E> implements LinkedList<E> {
    private int size = 0;
    private Node<E> head;
    private Node<E> tail;

    public DoublyLinkedList() {
    }

    @Override
    public int size() {
        return size;
    }

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

    @Override
    public boolean add(E e) {
        if (head == null) {
            Node<E> newNode = new Node<>(e, null, null);
            this.head = newNode;
            this.tail = newNode;
            size++;
        } else {
            Node<E> curNode = head;
            while (curNode.next != null) {
                curNode = curNode.next;
            }
            Node<E> newNode = new Node<>(e, null, curNode);
            curNode.next = newNode;
            this.tail = newNode;
            size++;
        }
        return true;
    }

    @Override
    public boolean remove(E e) {
        for (Node<E> curNode = head; curNode != null; curNode = curNode.next) {
            if (curNode.item.equals(e)) {
                Node<E> prev = curNode.prev;
                Node<E> next = curNode.next;
                if (prev == null) {
                    head = next;
                } else {
                    prev.next = next;
                }
                if (next == null) {
                    tail = prev;
                } else {
                    next.prev = prev;
                }
                size--;
                return true;
            }
        }
        return false;
    }

    @Override
    public E get(int index) {
        checkIndex(index);
        if (index < size / 2) {
            Node<E> curNode = head;
            for (int curIndex = 0; curIndex < index; curIndex++) {
                curNode = curNode.next;
            }
            return curNode.item;
        } else {
            Node<E> curNode = tail;
            for (int curIndex = size - 1; curIndex > index; curIndex--) {
                curNode = curNode.prev;
            }
            return curNode.item;
        }
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public E set(int index, E element) {
        checkIndex(index);
        Node<E> curNode = getNode(index);
        E item = curNode.item;
        curNode.item = element;
        return item;
    }

    private Node<E> getNode(int index) {
        checkIndex(index);
        if (index < size / 2) {
            Node<E> curNode = head;
            for (int curIndex = 0; curIndex < index; curIndex++) {
                curNode = curNode.next;
            }
            return curNode;
        } else {
            Node<E> curNode = tail;
            for (int curIndex = size - 1; curIndex > index; curIndex--) {
                curNode = curNode.prev;
            }
            return curNode;
        }
    }

    @Override
    public void add(int index, E element) {
        checkIndex(index);
        Node<E> oldNode = getNode(index);
        Node<E> prev = oldNode.prev;
        Node<E> newNode = new Node<>(element, null, null);
        if (prev == null) {
            head = newNode;
        } else {
            prev.setNext(newNode);
            newNode.setPrev(prev);
        }
        newNode.setNext(oldNode);
        oldNode.setPrev(newNode);
        size++;

    }

    @Override
    public E remove(int index) {
        checkIndex(index);
        Node<E> node = getNode(index);
        Node<E> next = node.next;//next和prev对象都有可能为null，所有下面需要进行判断
        Node<E> prev = node.prev;
        E item = node.item;

        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
        }
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
        }
        size--;
        return item;
    }

    @Override
    public int indexOf(E o) {
        int curIndex = 0;
        for (Node<E> curNode = head; curNode.next != null; curNode = curNode.next) {
            if (curNode.item.equals(o)) {
                return curIndex;
            }
            curIndex++;
        }
        return -1;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private int nextIndex;

            @Override
            public boolean hasNext() {
                return nextIndex < size;
            }

            @Override
            public E next() {
                return get(nextIndex++);
            }
        };
    }

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

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

        public void setNext(Node<E> next) {
            this.next = next;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }
    }
}

三、双向循环链表

双向循环链表特点：
 1.有head节点，无tail节点
 2.与单链表和双向链表不同，为简化操作，双向循环链表使用一个空哨兵节点作为head节点
 3.head节点的next指针指向第一个节点，head节点的prev指针指向最后一个节点；
 4.最后一个节点的next指针指向head节点，
 5.判断是否为空。head==head.next

/**
 * @Author : wangbin
 * @Date : 2/7/2022 11:18 AM
 * @Description: 双向循环链表特点：
 * 1.有head节点，无tail节点
 * 2.与单链表和双向链表不同，为简化操作，双向循环链表使用一个空哨兵节点作为head节点
 * 3.head节点的next指针指向第一个节点，head节点的prev指针指向最后一个节点；
 * 4.最后一个节点的next指针指向head节点，
 * 5.判断是否为空。head==head.next
 */
public class CircularLinkedList<E> implements LinkedList<E> {
    private int size = 0;
    private Node<E> head;

    public CircularLinkedList() {
        this.head = new Node<>(null, null, null);
        this.head.prev = this.head;
        this.head.next = this.head;
    }

    @Override
    public int size() {
        return size;
    }

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

    @Override
    public boolean add(E e) {
        if (head.next == head) {
            Node<E> newNode = new Node<>(e, null, null);
            this.head.next = newNode;
            this.head.prev = newNode;
            newNode.setNext(head);
            newNode.setPrev(head);
            size++;
        } else {
            Node<E> curNode = head;
            while (curNode.next != head) {
                curNode = curNode.next;
            }
            Node<E> newNode = new Node<>(e, head, curNode);
            curNode.next = newNode;
            head.prev = newNode;
            size++;
        }
        return true;
    }

    @Override
    public boolean remove(E e) {
        for (Node<E> curNode = head.next; curNode.item != null; curNode = curNode.next) {
            if (curNode.item.equals(e)) {
                Node<E> prev = curNode.prev;
                Node<E> next = curNode.next;
                prev.next = next;
                next.prev = prev;
                return true;
            }
        }
        return false;
    }

    @Override
    public E get(int index) {
        checkIndex(index);
        if (index < size / 2) {
            Node<E> curNode = head.next;
            for (int curIndex = 0; curIndex < index; curIndex++) {
                curNode = curNode.next;
            }
            return curNode.item;
        } else {
            Node<E> curNode = head.prev;
            for (int curIndex = size - 1; curIndex > index; curIndex--) {
                curNode = curNode.prev;
            }
            return curNode.item;
        }
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }

    @Override
    public E set(int index, E element) {
        checkIndex(index);
        Node<E> curNode = getNode(index);
        E item = curNode.item;
        curNode.item = element;
        return item;
    }

    private Node<E> getNode(int index) {
        checkIndex(index);
        if (index < size / 2) {
            Node<E> curNode = head.next;
            for (int curIndex = 0; curIndex < index; curIndex++) {
                curNode = curNode.next;
            }
            return curNode;
        } else {
            Node<E> curNode = head.prev;
            for (int curIndex = size - 1; curIndex > index; curIndex--) {
                curNode = curNode.prev;
            }
            return curNode;
        }
    }

    @Override
    public void add(int index, E element) {
        checkIndex(index);
        Node<E> oldNode = getNode(index);
        Node<E> prev = oldNode.prev;
        Node<E> newNode = new Node<>(element, oldNode, prev);
        prev.setNext(newNode);
        oldNode.setPrev(newNode);
        size++;
    }

    @Override
    public E remove(int index) {
        checkIndex(index);
        Node<E> node = getNode(index);
        Node<E> next = node.next;
        Node<E> prev = node.prev;
        E item = node.item;
        prev.next = next;
        next.prev = prev;

        size--;
        return item;
    }

    @Override
    public int indexOf(E o) {
        int curIndex = 0;
        for (Node<E> curNode = head.next; curNode.next != head; curNode = curNode.next) {
            if (curNode.item.equals(o)) {
                return curIndex;
            }
            curIndex++;
        }
        return -1;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            private Node<E> curNode = head.next;

            @Override
            public boolean hasNext() {
                return curNode.item != null;
            }

            @Override
            public E next() {
                E item = curNode.item;
                curNode = curNode.next;
                return item;
            }
        };
    }

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

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

        public void setNext(Node<E> next) {
            this.next = next;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }
    }
}