链表 Link List

一、链表数据结构

在计算机科学中，链表是数据元素的线性集合，元素的线性顺序不是由它们在内存中的物理地址给出的。
它是由一组节点组成的数据结构，每个元素指向下一个元素，这些节点一起，表示线性序列。

在最简单的链表结构下，每个节点由数据和指针（存放指向下一个节点的指针）两部分组成，这种数据结构允许在迭代时有效地从序列中的任何位置插入或删除元素。

链表的数据结构通过链的连接方式，提供了可以不需要扩容空间就更高效的插入和删除元素的操作，在适合的场景下它是一种非常方便的数据结构。
但在一些需要遍历、指定位置操作、访问任意元素的操作下，需要循环遍历，这将导致时间复杂度的提升。

简而言之就是链表的插入删除，直接操控节点，时间复杂度低，但是查询的操作需要遍历链表，时间复杂度高。

二、链表分类类型

链表的主要类型有：单向链表、双向链表、循环链表。

1、单向链表

单向链表包含具有数据字段的节点以及指向节点行中的下一个节点的“下一个字段”，可以对单链表执行的操作包括插入、删除、遍历。

2、双向链表

在双向链表中，除了下一个节点链接之外，每个节点还包括指向序列中“前一个”节点的第二个链接字段。这两个链接可以称为forwards和backwards or next和prev

3、循环链表

在链表的最后一个节点中，链接字段通常包含一个空引用，一个特殊的值用于指示缺少进一步的节点。
一个不太常见的约定是让它指向列表的第一个节点。
在这种情况下，列表被称为“循环”或“循环链接”；否则，它被称为“开放”或“线性”。
它是一个列表，其中最后一个指针指向第一个节点。

三、实现一个链表

1、链表节点代码

/**
 * ？表示不确定的 java 类型
 * T (type) 表示具体的一个java类型
 * K V (key value) 分别代表java键值中的Key Value
 * E (element) 代表Element
 */
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

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

链表的数据结构核心根基就在于节点对象的使用，并在节点对象中关联当前节点的上一个节点和下一个节点。通过这样的方式构建出链表结构。
但也因为在链表上添加每个元素的时候，都需要创建新的Node节点，所以这也是一部分耗时的操作。

2、头插节点

void linkFirst(E e){
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e , f);
    first = newNode;
    if (f == null){
        last = newNode;
    } else {
        f.prev = newNode;
    }
    size++;
}

头插的操作流程：先把头节点记录下来。之后创建一个新的节点，新的节点构造函数的头节点入参为null，通过这样的方式构建出一个新的头节点。
原来的头节点，设置f.prev连接到新的头节点，这样的就可以完成头插的操作了。
另外如果原来没有头节点，头节点设置为新的节点即可。最后记录当前链表中节点的数量。

3、尾插节点

void linkLast(E e){
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null){
        first = newNode;
    } else {
        l.next = newNode;
    }
    size++;
}

尾插节点与头插节点正好相反，通过记录当前的结尾节点，创建新的节点，并把当前的结尾节点，通过l.next关联到新创建的节点上。同时记录size。

4、拆链操作

E unLink(Node<E> x){
    final E item = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null){
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null){
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    return item;
}

unlink是一种拆链操作，只要给定一个元素，它就可以把当前这个元素的上一个节点和一个节点进行相连，之后把自己拆除。
这个方法常用于remove移除元素操作，因为整个操作过程不需要遍历，拆除元素后也不需要复制新的空间，所以时间复杂度O(1)

5、删除节点

public boolean remove(Object o) {
    if (o == null){
        for (Node<E> x = first; x != null; x = x.next){
            if (x.item == null){
                unLink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next){
            if (x.item.equals(o)){
                unLink(x);
                return true;
            }
        }
    }
    return false;
}

删除元素的过程需要for循环判断对比删除元素的值，找到对应的元素之后进行删除。
循环对比的过程是一个O(n)的操作，删除的过程是一个O(1)的操作。所以链表较大的话，循环对比的过程耗时较长。

四、使用测试

public class LinkedListTest {

    private final Logger logger = LoggerFactory.getLogger(LinkedListTest.class);

    @Test
    public void test_linked_list(){
        List<String> list = new LinkedList<>();
        // 添加元素
        list.add("a");
        list.addFirst("b");
        list.addLast("c");
        // 打印列表
        list.printLinkList();
        // 头插元素
        list.addFirst("d");
        // 删除元素
        list.remove("b");
        // 打印列表
        list.printLinkList();
    }
}

测试结果

目前的列表，头节点：b 尾节点：c 整体：b，a，c，
目前的列表，头节点：d 尾节点：c 整体：d，a，c，

五、常见面试问题

描述一下链表的数据结构？
Java中的LinkedList使用的是单向链表，双向链表还是循环链表？
链表中数据的插入、删除、获取元素，时间复杂度是多少？
什么场景下使用链表更合适？