链表

一、定义

链表是一种常见的数据结构，它由一组节点组成，每个节点包含数据元素和指向下一个节点的指针（或者称为链接）。链表中的节点可以是任意类型的数据，而且节点之间的逻辑顺序是通过指针来确定的，而不是物理上的顺序。链表中的第一个节点称为头节点，最后一个节点的指针指向空（null），表示链表的末尾。

二、特点

链表具有以下特点：

1. 动态性：链表的大小可以根据需要动态调整，可以动态地插入和删除节点。
2. 插入和删除效率高：相比于数组，链表在插入和删除操作上具有更高的效率，特别是在中间插入和删除元素时。
3. 不连续存储：链表中的节点在内存中不需要连续存储，它们可以分散在内存的任意位置。
4. 空间开销：链表需要额外的空间来存储指针，因此可能会比数组消耗更多的内存。

三、分类

根据指针的类型和节点的连接方式，链表可以分为多种类型，其中常见的包括：

1. 单向链表（Singly Linked List）：每个节点包含一个指向下一个节点的指针，节点之间的连接是单向的。从头节点开始，沿着指针可以遍历整个链表。
2. 双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点，节点之间的连接是双向的。双向链表可以从任一端开始遍历，并且可以在常数时间内进行前向或后向的遍历。
3. 循环链表（Circular Linked List）：在单向或双向链表的基础上，将最后一个节点的指针指向头节点，形成一个循环。循环链表可以像普通链表一样进行遍历，但是在特定场景下可能更加方便。

四、应用场景

链表在各种场景中都有着广泛的应用，特别是需要动态管理和操作数据的场合，例如：

1. 内存管理：操作系统中常用链表来管理内存空间的分配和释放。
2. 文件系统：文件系统中的目录结构和文件索引通常使用链表来表示和管理。
3. 缓冲区管理：链表可以用于实现缓冲区的管理，动态地添加和删除缓冲区中的数据。
4. 算法实现：链表在算法设计中有着广泛的应用，如链表排序、图的表示等。

五、实现

5.1 单向链表

/**
 * @Description 单向链表
 * @Author lcy
 * @Date 2020/9/7 14:06
 */
public class SingleLinkedList<E> extends AbstractLinear<E> {

    /**
     * 第一个节点值
     */
    private Node<E> firstNode;

    @Override public void add(int index,E element){
        //校验添加的下标
        rangeCheckAdd(index);
        //如果是在0节点插入，特殊处理。
        if (index == 0) {
            //替换第一个节点的值
            firstNode = new Node<>(element,firstNode);
        } else {
            link(element,node(index - 1));
        }
        size++;
    }

    @Override public void set(int index,E element){
        Node<E> node = node(index - 1);
        //如果是在0节点插入，特殊处理。
        if (index == 0) {
            //替换第一个节点的地址
            firstNode = new Node<>(element,firstNode.next);
        } else {
            //节点值替换。上一个节点的地址指向新的节点地址，新的节点地址指向原来旧节点地址指向的下一个节点地址
            node.next = new Node<>(element,node.next.next);
        }
    }

    @Override public E get(int index){
        //先根据函数获取当前下标的上一个节点的对象，最后获取下一个节点（即index）的对象的值
        return node(index).element;
    }

    @Override public void clear(){
        //清除引用
        firstNode = null;
        size = 0;
    }

    @Override public int indexOf(E element){
        Node<E> node = firstNode;
        //判断是要校验比较null还是根据equals比较，防止空指针异常
        boolean checkNull = false;
        if (element == null) {
            checkNull = true;
        }

        for (int i = 0; i < size; i++) {
            if (checkNull && node.element == null) {
                return i;
            } else if (!checkNull && element.equals(node.element)) {
                return i;
            }
            node = node.next;
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override public E remove(int index){
        rangeCheck(index);
        Node<E> node;
        if (index == 0) {
            node = firstNode.next;
            //替换第一个节点的地址
            firstNode = node;
        } else {
            //获取需要删除节点的上一个节点对象
            node = node(index - 1);
            node.next = node.next.next;
        }
        size--;

        return node.element;
    }

    /**
     * @param element 节点值
     * @param node    需要插入节点的上一个节点值（0节点做了特殊处理）
     * @author lcy
     * @date 2020/9/7 14:34
     **/
    private void link(E element,Node<E> node){
        //节点值转换
        node.next = new Node<>(element,node.next);
    }

    /**
     * 获取下标的节点的值
     * @param index 下标
     * @return com.lcy.study.algoithm.linear.link.SingleLinkedList.RedBlackNode<E>
     * @author lcy
     * @date 2020/9/7 14:24
     **/
    private Node<E> node(int index){
        rangeCheck(index);

        Node<E> node = firstNode;
        //找到当前下标节点的值添加
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    /**
     * 单向节点内部类
     * @author lcy
     * @date 2020/9/7 10:22
     **/
    static class Node<E> {

        /**
         * 当前节点值
         */
        E element;

        /**
         * 下个节点值
         */
        Node<E> next;

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

        }
    }

    @Override public String toString(){
        //获取第一个节点对象
        Node<E> node = firstNode;
        StringBuilder stringBuilder = new StringBuilder("SingleLinkedList: size=")
                .append(size).append(" {");
        //遍历链表
        while (node != null) {
            stringBuilder.append("[").append(node.element).append("],");
            node = node.next;
        }
        //删除最后一个逗号（,）
        stringBuilder.setLength(stringBuilder.length() - 1);
        stringBuilder.append("}");
        return stringBuilder.toString();
    }

    public static void main(String[] args){
        SingleLinkedList<Object> singleLinkedList = new SingleLinkedList<>();
        singleLinkedList.add("e");
        System.out.println(singleLinkedList);
        singleLinkedList.add(0,"a");
        singleLinkedList.add(1,"c");
        singleLinkedList.add(3,"d");
        System.out.println(singleLinkedList);
        singleLinkedList.remove(0);
        singleLinkedList.remove(1);
        System.out.println(singleLinkedList);
        singleLinkedList.add(2,"d");
        singleLinkedList.add(2,"e");
        System.out.println(singleLinkedList);
        System.out.println(singleLinkedList.get(0));
        System.out.println(singleLinkedList.get(2));
    }
}

5.2 双向链表

/**
 * @Description 双向链表
 * @Author lcy
 * @Date 2020/9/7 10:18
 */
public class DoubleLinkedList<E> extends AbstractLinear<E> {

    /**
     * 第一个节点值
     */
    private Node<E> firstNode;

    /**
     * 最后的节点值
     */
    private Node<E> lastNode;

    @Override
    public void add(int index,E element){
        //校验下标
        rangeCheckAdd(index);

        //如果第一个节点为空，则表示链表节点为空，在赋值属性
        if (firstNode == null) {
            Node<E> elementNode = new Node<>(null,element,null);
            firstNode = elementNode;
            lastNode = elementNode;
        } else {
            if (index == size) {
                linkLast(element);
            } else {
                //不为头尾插入，转换节点
                Node<E> node = node(index);
                nodeChange(node,element);
            }
        }
        size++;
    }

    @Override
    public void set(int index,E element){
        rangeCheck(index);
        //获取节点的数据
        Node<E> node = node(index);
        //替换节点数据
        node.element = element;
    }

    @Override
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    @Override
    public void clear(){
        //删除对象的引用，gc自动回收节点的其他引用
        firstNode = null;
        lastNode = null;
    }

    @Override
    public int indexOf(E element){
        Node<E> node = firstNode;
        for (int i = 0; i < size; i++) {
            //判断对象是否为空
            if (element == null && node.element == null) {
                return i;
                //对象不为空，用equals
            } else if (element != null && element.equals(node.element)) {
                return i;
            }
            node = node.next;
        }

        return ELEMENT_NOT_FOUND;
    }

    @Override
    public E remove(int index){
        rangeCheck(index);

        //获取下标节点值
        Node<E> node = node(index);
        //节点转换
        if (node.prev == null) {
            firstNode = firstNode.next;
            firstNode.prev = null;
        } else if (node.next == null) {
            lastNode = lastNode.prev;
            lastNode.next = null;
        } else {
            //中间节点删除
            //将上个节点的下标指向下个节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        size--;
        return node.element;
    }

    /**
     * 在尾部链表添加节点
     * @param element 节点值
     * @author lcy
     * @date 2020/9/7 17:05
     **/
    private void linkLast(E element){
        Node<E> elementNode = new Node<>(lastNode,element,null);
        lastNode.next = elementNode;
        lastNode = elementNode;
    }

    /**
     * 节点数据转换
     * @param node    需要替换的节点
     * @param element 需要替换节点的值
     * @author lcy
     * @date 2020/9/7 13:09
     **/
    private void nodeChange(Node<E> node,E element){
        //创建新节点值
        Node<E> elementNode = new Node<>(node.prev,element,node);
        //如果上一个节点值为空，说明是第一个节点，替换第一个节点的值。
        if (node.prev == null) {
            firstNode = elementNode;
        } else {
            node.prev.next = elementNode;
        }
        //旧节点的数据的节点下移，上一个节点为新节点的对象
        node.prev = elementNode;

    }

    /**
     * 获取节点值
     * @param index 需要转换的下标
     * @author lcy
     * @date 2020/9/7 13:04
     **/
    private Node<E> node(int index){

        int tempIndex = 0;
        Node<E> tempNode = firstNode;
        if (index > size >> 1) {
            tempIndex = size - 1;
            tempNode = lastNode;
        }

        while (true) {
            if (index == tempIndex) {
                return tempNode;
            }
            if (index > size >> 1) {
                tempNode = tempNode.prev;
                tempIndex--;
            } else {
                tempNode = tempNode.next;
                tempIndex++;
            }
        }

    }

    /**
     * 双向节点内部类
     * @author lcy
     * @date 2020/9/7 10:22
     **/
    static class Node<E> {

        /**
         * 当前节点值
         */
        E element;

        /**
         * 上一节点值
         */
        Node<E> prev;

        /**
         * 下个节点值
         */
        Node<E> next;

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

        }
    }

    @Override public String toString(){
        //获取第一个节点对象
        Node<E> node = firstNode;
        StringBuilder stringBuilder = new StringBuilder("DoubleLinkedList: size=")
                .append(size).append(" {");
        //遍历链表
        while (node != null) {
            stringBuilder.append("[").append(node.element).append("],");
            node = node.next;
        }
        //删除最后一个逗号（,）
        stringBuilder.setLength(stringBuilder.length() - 1);
        stringBuilder.append("}");
        return stringBuilder.toString();
    }

    public static void main(String[] args){
        DoubleLinkedList<Object> doubleLinkedList = new DoubleLinkedList<>();
        doubleLinkedList.add(null);
        System.out.println(doubleLinkedList);
        //doubleLinkedList.add("1");
        //doubleLinkedList.add("2");
        //doubleLinkedList.add("3");
        //System.out.println(doubleLinkedList);
        //doubleLinkedList.add(1,"3");
        //doubleLinkedList.add(4,"4");
        //doubleLinkedList.add("5");
        //doubleLinkedList.add("6");
        //System.out.println(doubleLinkedList);
        //doubleLinkedList.remove(0);
        //doubleLinkedList.remove(5);
        //System.out.println(doubleLinkedList);
        //System.out.println(doubleLinkedList.get(4));
        //System.out.println(doubleLinkedList.get(2));
    }

}

5.3 循环链表

/**
 * @Description 双向循环链表
 * @Author lcy
 * @Date 2020/9/7 10:18
 */
public class DoubleCycleLinkedList<E> extends AbstractLinear<E> {

    /**
     * 第一个节点值
     */
    private Node<E> firstNode;

    /**
     * 最后的节点值
     */
    private Node<E> lastNode;

    /**
     * 当前指针所在节点
     */
    private Node<E> current;

    @Override
    public void add(int index,E element){
        //校验下标
        rangeCheckAdd(index);

        //如果在头结点插入
        if (index == 0) {
            //判断链表是否为空
            if (size == 0) {
                //先创建一个节点
                Node<E> node = new Node<>(null,element,null);
                //所有的节点指针都指向该节点
                firstNode = node;
                lastNode = node;
                node.prev = node;
                node.next = node;
                current = node;
            } else {
                //流程为 原链表oldFirst->node1->oldLast->oldFirst
                //改为   原链表newFirst->oldFirst->node1->oldLast->newFirst
                //创建一个新节点 前指针指向旧的firstNode，后指针指向lastNode
                Node<E> node = new Node<>(lastNode,element,firstNode);
                //最后一个节点lastNode指向新的（头）结点
                lastNode.next = node;
                //旧的头结点的后指针指向新的节点。
                firstNode.prev = node;
                //最后firstNode改为新的节点
                firstNode = node;
            }
            //如果是在最后添加
        } else {
            //根据条件创建新的节点
            if (index == size) {
                //创建一个尾节点
                Node<E> node = new Node<>(lastNode,element,firstNode);
                //头结点指向新的尾节点
                firstNode.prev = node;
                //原本的尾结点是指向头结点，改为指向新的尾节点
                lastNode.next = node;
                //尾节点改为新节点
                lastNode = node;
            } else {
                //先获取原节点的值
                Node<E> indexNode = node(index);
                //创建新节点
                Node<E> node = new Node<>(indexNode.prev,element,indexNode);
                //原节点的上一个节点的下一个节点指向新的节点
                indexNode.prev.next = node;
                //原节点的上一个节点指向新的节点
                indexNode.prev = node;
            }
        }
        size++;
    }

    @Override
    public void set(int index,E element){
        rangeCheck(index);
        //获取节点的数据
        Node<E> node = node(index);
        //替换节点数据
        node.element = element;
    }

    @Override
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    @Override
    public void clear(){
        //删除对象的引用，gc自动回收节点的其他引用
        firstNode = null;
        lastNode = null;
        current = null;
    }

    @Override
    public int indexOf(E element){
        Node<E> node = firstNode;
        for (int i = 0; i < size; i++) {
            //判断对象是否为空
            if (element == null && node.element == null) {
                return i;
                //对象不为空，用equals
            } else if (element != null && element.equals(node.element)) {
                return i;
            }
            node = node.next;
        }

        return ELEMENT_NOT_FOUND;
    }

    @Override
    public E remove(int index){
        rangeCheck(index);
        Node<E> node;
        //如果是删除头结点或者尾，替换头尾节点的指向
        if (index == 0) {
            node = firstNode;
            //如果链表只有一个元素，因为所有指向都是指向自己，特殊处理
            if (size == 1) {
                firstNode = null;
                lastNode = null;
            } else {
                //头结点改为原头结点指向的
                firstNode = firstNode.next;
                //新的头结点指向最后的节点
                firstNode.prev = lastNode;
                //最后的节点指向新节点
                lastNode.next = firstNode;
            }
        } else if (index == size - 1) {
            //因为size == 1已经在上面处理，这里不需要处理
            node = lastNode;
            //尾结点改为原尾结点指向的
            lastNode = lastNode.prev;
            //新的头结点指向最后的节点
            firstNode.prev = lastNode;
            //最后的下一个节点指向头节点
            lastNode.next = firstNode;
        } else {
            //获取需要删除节点值
            node = node(index);
            //删除节点
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        size--;
        return node.element;
    }

    /**
     * 获取节点值
     * @param index 需要转换的下标
     * @author lcy
     * @date 2020/9/7 13:04
     **/
    private Node<E> node(int index){

        int tempIndex = 0;
        Node<E> tempNode = firstNode;
        if (index > size >> 1) {
            tempIndex = size - 1;
            tempNode = lastNode;
        }

        while (true) {
            if (index == tempIndex) {
                return tempNode;
            }
            if (index > size >> 1) {
                tempNode = tempNode.prev;
                tempIndex--;
            } else {
                tempNode = tempNode.next;
                tempIndex++;
            }
        }

    }

    /**
     * 重置当前的节点值为第一个节点
     */
    public void resetCurrent(){
        current = firstNode;
    }

    /**
     * 当前节点往前走一步
     */
    public E next(){
        if (current == null) {
            return null;
        }
        current = current.next;
        return current.element;
    }

    /**
     * 删除current节点
     */
    public E remove(){
        if (current == null) {
            return null;
        }
        //如果当前节点的下一个节点还是自己，删除当前节点
        if (current.next == current) {
            current = null;
            firstNode = null;
            lastNode = null;
            return null;
        }
        current.prev.next = current.next;
        current.next.prev = current.prev;
        current = current.next;
        return current.element;
    }

    /**
     * 双向节点内部类
     * @author lcy
     * @date 2020/9/7 10:22
     **/
    static class Node<E> {

        /**
         * 当前节点值
         */
        E element;

        /**
         * 上一节点值
         */
        Node<E> prev;

        /**
         * 下个节点值
         */
        Node<E> next;

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

        }

        @Override protected void finalize() throws Throwable{
            System.out.println("销毁节点：element:" + element);
        }

        @Override public String toString(){
            return "RedBlackNode[" + element + ']';
        }
    }

    @Override public String toString(){
        //获取第一个节点对象
        Node<E> node = firstNode;
        StringBuilder stringBuilder = new StringBuilder("DoubleLinkedList: size=")
                .append(size).append(" {");
        //遍历链表
        while (node != lastNode) {
            stringBuilder.append(node).append(",");
            node = node.next;
        }
        stringBuilder.append(lastNode);
        stringBuilder.append("}");
        return stringBuilder.toString();
    }

    /**
     * 约瑟夫问题
     */
    public static <E> E josephus(Node<E> node){
        return null;
    }

    public static void main(String[] args){
        DoubleCycleLinkedList<Object> doubleLinkedList = new DoubleCycleLinkedList<>();
        doubleLinkedList.add(null);
        System.out.println(doubleLinkedList);
        doubleLinkedList.add("1");
        doubleLinkedList.add("2");
        doubleLinkedList.add("3");
        System.out.println(doubleLinkedList);
        doubleLinkedList.add(1,"3");
        doubleLinkedList.add(4,"4");
        doubleLinkedList.add("5");
        doubleLinkedList.add("6");
        System.out.println(doubleLinkedList);
        doubleLinkedList.remove(0);
        doubleLinkedList.remove(5);
        System.out.println(doubleLinkedList);
        System.out.println(doubleLinkedList.get(4));
        System.out.println(doubleLinkedList.get(2));
    }

}

5.4 双向循环链表（虚拟节点）

由于增加虚拟节点，加大了内存的开销，实际情况下不如5.3的双向循环链表

/**
 * @Description 双向循环链表--虚拟节点
 * @Author lcy
 * @Date 2020/9/7 10:18
 */
public class DoubleVirtualCycleLinkedList<E> extends AbstractLinear<E> {

    /**
     * 虚拟节点（第一个节点）
     */
    private final Node<E> virtualNode;

    /**
     * 当前指针所在节点
     */
    private Node<E> current;

    public DoubleVirtualCycleLinkedList(){
        //创建虚拟节点
        Node<E> node = new Node<>(null,null,null);
        node.next = node;
        node.prev = node;
        virtualNode = node;
        current = virtualNode;
    }

    @Override
    public void add(int index,E element){
        //校验下标
        rangeCheckAdd(index);

        Node<E> node = node(index);
        Node<E> newNode = new Node<>(node.prev,element,node);
        node.prev.next = newNode;
        node.prev = newNode;
        if (size == 0) {
            current = virtualNode.next;
        }
        size++;
    }

    @Override
    public void set(int index,E element){
        rangeCheck(index);
        //获取节点的数据
        Node<E> node = node(index);
        //替换节点数据
        node.element = element;
    }

    @Override
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    @Override
    public void clear(){
        //删除对象的引用，gc自动回收节点的其他引用
        virtualNode.next = virtualNode;
        virtualNode.prev = virtualNode;
        current = virtualNode;
    }

    @Override
    public int indexOf(E element){
        Node<E> node = virtualNode.next;
        for (int i = 0; i < size; i++) {
            //判断对象是否为空
            if (element == null && node.element == null) {
                return i;
                //对象不为空，用equals
            } else if (element != null && element.equals(node.element)) {
                return i;
            }
            node = node.next;
        }

        return ELEMENT_NOT_FOUND;
    }

    @Override
    public E remove(int index){
        rangeCheck(index);
        Node<E> node = node(index);

        node.prev.next = node.next;
        node.next.prev = node.prev;
        if (size == 1) {
            current = virtualNode;
        }
        size--;
        return  node.element;
    }

    /**
     * 获取节点值
     * @param index 需要转换的下标
     * @author lcy
     * @date 2020/9/7 13:04
     **/
    private Node<E> node(int index){

        int tempIndex = 0;
        Node<E> tempNode = virtualNode.next;
        if (index > size >> 1) {
            tempIndex = size;
            tempNode = virtualNode;
        }

        while (true) {
            if (index == tempIndex) {
                return tempNode;
            }
            if (index > size >> 1) {
                tempNode = tempNode.prev;
                tempIndex--;
            } else {
                tempNode = tempNode.next;
                tempIndex++;
            }
        }

    }

    /**
     * 重置当前的节点值为第一个节点
     */
    public void resetCurrent(){
        if (size == 0) {
            current = virtualNode;
        } else {
            current = virtualNode.next;
        }
    }

    /**
     * 当前节点往前走一步
     */
    public void next(){
        current = current.next;
        if (current == virtualNode) {
            current = virtualNode.next;
        }
    }

    /**
     * 删除current节点
     */
    public void remove(){
        current.prev.next = current.next;
        current.next.prev = current.prev;
        current = current.next;
    }

    /**
     * 双向节点内部类
     * @author lcy
     * @date 2020/9/7 10:22
     **/
    static class Node<E> {

        /**
         * 当前节点值
         */
        E element;

        /**
         * 上一节点值
         */
        Node<E> prev;

        /**
         * 下个节点值
         */
        Node<E> next;

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

        }

        @Override protected void finalize() throws Throwable{
            System.out.println("销毁节点：element:" + element);
        }

        @Override public String toString(){
            return "RedBlackNode[" + element + ']';
        }
    }

    @Override public String toString(){
        //获取第一个节点对象
        Node<E> node = virtualNode.next;
        StringBuilder stringBuilder = new StringBuilder("DoubleLinkedList: size=")
                .append(size).append(" {");
        //遍历链表
        while (node != virtualNode) {
            stringBuilder.append(node).append(",");
            node = node.next;
        }
        //删除最后一个逗号（,）
        stringBuilder.setLength(stringBuilder.length() - 1);
        stringBuilder.append("}");
        return stringBuilder.toString();
    }

    public static void main(String[] args){
        DoubleVirtualCycleLinkedList<Object> doubleLinkedList = new DoubleVirtualCycleLinkedList<>();
        doubleLinkedList.add(null);
        System.out.println(doubleLinkedList);
        doubleLinkedList.add("1");
        doubleLinkedList.add("2");
        doubleLinkedList.add("3");
        System.out.println(doubleLinkedList);
        doubleLinkedList.add(1,"3");
        doubleLinkedList.add(4,"4");
        doubleLinkedList.add("5");
        doubleLinkedList.add("6");
        System.out.println(doubleLinkedList);
        doubleLinkedList.remove(0);
        doubleLinkedList.remove(5);
        System.out.println(doubleLinkedList);
        System.out.println(doubleLinkedList.get(4));
        System.out.println(doubleLinkedList.get(2));
    }

}

六、总结

链表是一种常见的数据结构，具有动态性、高效的插入和删除操作等特点，适用于各种需要动态管理和操作数据的场景。链表可以根据指针的类型和节点的连接方式分为多种类型，每种类型都有着不同的应用场景和适用范围。对链表的深入理解和熟练运用，有助于提高程序的效率和性能。