2.1 链表

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

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

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

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

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

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

       Node类代码：

package com.youngthing.list.linked;/ * 2022/1/9 22:17 创建 * * @author 花书粉丝 */class Node {    private Node prev;    private Node next;    private T key;    public Node(T value) { key = value;    }    public Node getPrev() { return prev;    }    public void setPrev(Node prev) { this.prev = prev;    }    public Node getNext() { return next;    }    public void setNext(Node 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 {    private Node head;    private Node tail;    private int length;    public void addLast(T value) { Node 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 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语言外，其他语言基本上都有官方的链表实现，官方实现都考虑了诸如多线程并发等问题。