数据结构——链表

链表

数组要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间 时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。

链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。

链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点 的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next。

单向链表

单向链表就是通过每个节点的指针指向下一个节点从而链接起来的结构，最后一个节点的next指向null。

其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针 不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。与数组一样，链表也支持数据的查找、插入和删除操作。只不过效率会不高。

单向循环链表

单向循环链表和单向链表的不同是，最后一个节点的next不是指向null，而是指向head节点，形成一个“环”。

循环链表是一种特殊的单链表。它跟单链表唯一的区别就在尾结点：单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

双向链表包含两个指针，pre指向前一个节点，next指向后一个节点，第一个节点的pre和最后一个节点的next都指向null。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向循环链表

双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。而Java的LinkedList就是基于双向循环链表设计的。

代码实现

单向链表实现

public class LinkedList<E> {

    private class Node<E>{
        public E e;

        public Node<E> next;

        public Node(E e){
            this.e = e;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node<E> dummyHead;

    private Integer size;

    public LinkedList(){
        dummyHead = new Node<>(null);
        size = 0;
    }

    /**
     * 获取元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 返回链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 在链表的index(0-based)位置添加新的元素e
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param e
     */
    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node<E> prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> node = new Node<>(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    /**
     * 在链表头添加新元素
     * @param e
     */
    public void addFirst(E e){
        Node<E> node = new Node<>(e);
        node.next = dummyHead.next;
        dummyHead.next = node;
        size++;
    }

    /**
     * 在链表尾部添加新元素
     * @param e
     */
    public void addLast(E e){
        add(size,e);
    }

    /**
     * 获取链表的index(0-based)位置的元素e
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param index
     * @return
     */
    public E get(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }
        Node<E> cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    /**
     * 获取链表的第一个元素
     * @return
     */
    public E getFirst(){
        return get(0);
    }

    /**
     * 获取链表的最后一个元素
     * @return
     */
    public E getLast(){
        return get(size - 1);
    }

    /**
     * 修改链表的index(0-based)位置的元素
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Update failed. Illegal index.");
        }
        Node<E> cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

    /**
     * 查找链表中是否有元素e
     * @param e
     * @return
     */
    public boolean contains(E e){
        Node<E> cur = dummyHead;
        while (cur != null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 从链表中删除index(0-based)位置的元素，返回删除的元素
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param index
     * @return
     */
    public E remove(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        }
        Node<E> prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size -- ;
        return retNode.e;
    }

    /**
     * 从链表中删除第一个元素，返回删除的元素
     * @return
     */
    public E removeFirst(){
        return remove(0);
    }

    /**
     * 删除链表最后一个元素，返回删除的元素
     * @return
     */
    public E removeLast(){
        return remove(size - 1);
    }

    /**
     * 删除链表元素
     * @param e
     * @return
     */
    public boolean delete(E e) {
        if (isEmpty())
            throw new NoSuchElementException();

        Node<E> cur = dummyHead;
        for (int i = 0; i < size; i++) {
            if(cur.next.e.equals(e)){
                Node<E> delNode = cur.next;
                cur.next = delNode.next;
                delNode.next = null;
                size -- ;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 反转链表
     * @return
     */
    public void reverseList() {
        //定义前置节点
        Node<E> prev = null;
        //定义当前节点
        Node<E> cur = dummyHead.next;
        while(cur != null){
            //当前节点的下一节点
            Node<E> next = cur.next;
            //当前节点指向前置节点
            cur.next = prev;
            //当前节点赋值为前置节点
            prev = cur;
            //下一节点赋值为当前节点
            cur = next;
        }
        //设置反转后的链表
        dummyHead.next = prev;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: head ");
        Node<E> cur = dummyHead.next;
        while (cur != null){
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }
}

单向链表(while循环)实现

public class LinkedList2<E> {

    private class Node<E>{
        public E e;

        public Node<E> next;

        public Node(E e){
            this.e = e;
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node<E> dummyHead;

    private Integer size;

    public LinkedList2(){
        dummyHead = new Node<>(null);
        size = 0;
    }

    /**
     * 获取元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 返回链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 在链表的index(0-based)位置添加新的元素e
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param e
     */
    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }

        Node<E> prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> node = new Node<>(e);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    /**
     * 在链表头添加新元素
     * @param e
     */
    public void addFirst(E e){
        Node<E> node = new Node<>(e);
        node.next = dummyHead.next;
        dummyHead.next = node;
        size++;
    }

    /**
     * 在链表尾部添加新元素
     * @param e
     */
    public void addLast(E e){
        Node<E> node = new Node<>(e);
        Node<E> cur = dummyHead.next;
        if(cur == null){
            addFirst(e);
        }else{
            while (cur.next!=null){
                cur = cur.next;
            }
            cur.next = node;
            size++;
        }
    }

    /**
     * 获取链表的第一个元素
     * @return
     */
    public E getFirst(){
        Node<E> cur = dummyHead.next;
        if(cur == null){
            return null;
        }
        return cur.e;
    }

    /**
     * 获取链表的最后一个元素
     * @return
     */
    public E getLast(){
        Node<E> cur = dummyHead.next;
        if(cur == null){
            return null;
        }else {
            while (cur.next != null){
                cur = cur.next;
            }
        }
        return cur.e;
    }

    /**
     * 修改链表的index(0-based)位置的元素
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("Update failed. Illegal index.");
        }
        Node<E> cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

    /**
     * 查找链表中是否有元素e
     * @param e
     * @return
     */
    public boolean contains(E e){
        Node<E> cur = dummyHead;
        while (cur != null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 从链表中删除第一个元素，返回删除的元素
     * @return
     */
    public E removeFirst(){
        if(isEmpty()){
            throw new IllegalArgumentException("Remove failed. linkedList is empty");
        }
        Node<E> prev = dummyHead;
        Node<E> retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size -- ;
        return retNode.e;
    }

    /**
     * 删除链表元素
     * @param e
     * @return
     */
    public boolean delete(E e) {
        if (isEmpty())
            throw new NoSuchElementException();

        Node<E> cur = dummyHead;
        while (cur.next != null) {
            if(cur.next.e.equals(e)){
                Node<E> delNode = cur.next;
                cur.next = delNode.next;
                delNode.next = null;
                size -- ;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 反转链表
     * @return
     */
    public void reverseList() {
        //定义前置节点
        Node<E> prev = null;
        //定义当前节点
        Node<E> cur = dummyHead.next;
        while(cur != null){
            //当前节点的下一节点
            Node<E> next = cur.next;
            //当前节点指向前置节点
            cur.next = prev;
            //当前节点赋值为前置节点
            prev = cur;
            //下一节点赋值为当前节点
            cur = next;
        }
        //设置反转后的链表
        dummyHead.next = prev;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: head ");
        Node<E> cur = dummyHead.next;
        while (cur != null){
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }
}

双向链表实现

public class DoubleLinkedList<E> {

    private class Node<E>{
        public E e;

        public Node<E> next;

        public Node<E> prev;

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

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node<E> head;

    private Node<E> tail;

    private Integer size;

    public DoubleLinkedList(){
        size = 0;
    }

    /**
     * 获取元素个数
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 返回链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 在链表头添加新元素
     * @param e
     */
    public void addFirst(E e){
        Node<E> node = head;
        Node<E> newNode = new Node<>(null, e, node);
        head = newNode;
        if(node == null){
            tail = newNode;
        }else{
            node.prev = newNode;
        }
        size++;
    }

    /**
     * 在链表尾部添加新元素
     * @param e
     */
    public void addLast(E e){
        Node<E> node = tail;
        Node<E> newNode = new Node<>(node, e, null);
        tail = newNode;
        if (node == null)
            head = newNode;
        else
            node.next = newNode;
        size++;
    }

    public void add(Integer index, E e){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Add failed. Illegal index.");
        }
        if(index == 0){
            addFirst(e);
            return;
        }
        if(index == size - 1){
            addLast(e);
            return;
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Node<E> prev = cur.prev;
        Node<E> newNode = new Node<>(prev, e, cur);
        cur.prev = newNode;
        prev.next = newNode;
        size++;
    }

    /**
     * 获取链表的第一个元素
     * @return
     */
    public E getFirst(){
        if (head == null)
            throw new NoSuchElementException();
        return head.e;
    }

    /**
     * 获取链表的最后一个元素
     * @return
     */
    public E getLast(){
        if (tail == null)
            throw new NoSuchElementException();
        return tail.e;
    }

    /**
     * 获取链表的index(0-based)位置的元素e
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param index
     * @return
     */
    public E get(int index){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }

    /**
     * 修改链表的index(0-based)位置的元素
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Update failed. Illegal index.");
        }
        if(index == 0){
            head.e = e;
            return;
        }
        if(index == size - 1){
            tail.e = e;
            return;
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }

    /**
     * 查找链表中是否有元素e
     * @param e
     * @return
     */
    public boolean contains(E e){
        Node<E> cur = head;
        while (cur != null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 从链表中删除第一个元素，返回删除的元素
     * @return
     */
    public E removeFirst(){
        if (head == null)
            throw new NoSuchElementException();
        Node<E> delNode = head;
        if(delNode.next == null){
            head = tail = null;
        }else {
            head = delNode.next;
            head.prev = null;
            delNode.next = null;
        }
        size--;
        return delNode.e;
    }

    /**
     * 删除链表最后一个元素，返回删除的元素
     * @return
     */
    public E removeLast(){
        if (tail == null)
            throw new NoSuchElementException();
        Node<E> delNode = tail;
        if(delNode.prev == null){
            head = tail = null;
        }else {
            tail = delNode.prev;
            tail.next = null;
            delNode.prev = null;
        }
        size--;
        return delNode.e;
    }

    /**
     * 删除链表元素
     * @param e
     * @return
     */
    public boolean delete(E e) {
        if (head == null)
            throw new NoSuchElementException();

        Node<E> cur = head;
        while (cur != null) {
            if(cur.e.equals(e)){
                Node<E> prev = cur.prev;
                Node<E> next = cur.next;

                //当前节点为头结点
                if (prev == null) {
                    head = next;
                } else {
                    prev.next = next;
                    cur.prev = null;
                }
                //当前节点为尾节点
                if (next == null) {
                    tail = prev;
                } else {
                    next.prev = prev;
                    cur.next = null;
                }
                size--;
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    /**
     * 从链表中删除index(0-based)位置的元素，返回删除的元素
     * 在链表中不是一个常规操作，仅仅作为练习
     * @param index
     * @return
     */
    public E remove(int index){
        if(index < 0 || index > size - 1){
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        }
        if(index == 0){
            return removeFirst();
        }
        if(index == size - 1){
            return removeLast();
        }
        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        cur.next = null;
        cur.prev = null;
        size -- ;
        return cur.e;
    }

    /**
     * 反转链表
     * @return
     */
    public void reverseList() {
        //定义前置节点
        Node<E> prev = null;
        //定义当前节点
        Node<E> cur = head;
        while(cur != null){
            //当前节点的下一节点
            Node<E> next = cur.next;
            //当前节点next指向前置节点
            cur.next = prev;
            //当前节点prev指向next节点
            cur.prev = next;
            //当前节点赋值为前置节点
            prev = cur;
            //下一节点赋值为当前节点
            cur = next;
        }
        //设置反转后的链表
        head = prev;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: head ");
        Node<E> cur = head;
        while (cur != null){
            sb.append(cur + "->");
            cur = cur.next;
        }
        sb.append("NULL tail");
        return sb.toString();
    }
}

参考：
https://blog.csdn.net/weixin_39084521/article/details/89820104

https://www.pianshen.com/article/2658786689/