2.1 链表

       链表是一种有序的列表。在实际的开发中，链表的使用场景太多了，比如作栈或者队列来使用，在多线程中用作线程队列，在内存管理中用作LRU（最近最少使用）算法的底层数据结构。与数组相比，它的优点是长度可变，可以从两端动态删除或增加节点。但是缺点是按索引访问比数组慢。所以这里我只简单介绍链表的实现。

       链表按结构可以分成单向链表、双向链表与环状列表。使用场景最多的是双向链表，所以仅介绍双向链表。

       双向链表结构如下图（图片来自麻省理工《算法导论》）所示

       所以如果用java实现则需要两个类，一个是链表，包含头、尾和长度属性。另一个是节点类，包含前置节点，后置节点和key属性。

       链表有四个核心方法：头部添加、尾部添加、头部删除、尾部删除。

       其类关系和属性方法如下：

       Node类代码：

package com.youngthing.list.linked;

/**
 * 2022/1/9 22:17 创建
 *
 * @author 花书粉丝
 */
class Node<T> {

    private Node<T> prev;
    private Node<T> next;
    private T key;

    public Node(T value) {
        key = value;
    }

    public Node<T> getPrev() {
        return prev;
    }

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

    public Node<T> getNext() {
        return next;
    }

    public void setNext(Node<T> next) {
        this.next = next;
        if (next != null) {
            next.prev = this;
        }
    }

    public T getKey() {
        return key;
    }

    public void setKey(T key) {
        this.key = key;
    }
}

       List类代码：

package com.youngthing.list.linked;

/**
 * 2022/1/9 22:17 创建
 *
 * @author 花书粉丝
 */
public class LinkedList<T> {

    private Node<T> head;
    private Node<T> tail;
    private int length;

    public void addLast(T value) {
        Node<T> node = new Node<>(value);
        if (head == null) {
            tail = head = node;
        } else {
            tail.setNext(node);
            tail = node;
        }
        length++;
    }

    public T removeLast() {
        if (head == null) {
            throw new RuntimeException("链表为空");
        }
        T temp = tail.getKey();
        if (length == 1) {
            tail = head = null;
            return temp;
        } else {
            tail = tail.getPrev();
        }
        length--;
        return temp;
    }

    public void addFirst(T value) {
        Node<T> node = new Node<>(value);
        if (head == null) {
            tail = head = node;
        } else {
            node.setNext(head);
            head = node;
        }
        length++;
    }

    public T removeFirst() {
        T temp = head.getKey();
        if (length == 1) {
            tail = head = null;
        } else {
            head = head.getNext();
        }
        length--;
        return temp;
    }
}

       提供一个公开的git地址：

       https://e.coding.net/buildt/data-structure/list.git

       对于想学习数据结构的读者来说，链表还是要自己动手写一写，练一练。但是不建议在实际项目中自己写链表的实现，除了c语言外，其他语言基本上都有官方的链表实现，官方实现都考虑了诸如多线程并发等问题。