链表

1.链表的定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

摘自 维基百科

从底层结构上来说，顺序表也就是数组，在初始化的时候，必须分配连续的内存块；而链表的内存分布则是零散的。直观的说，比如我们申请一个10M的数组，当内存中没有连续的、足够装下10M的空间，即使总使用空间大于10M，数组依旧会分配失败，链表的话则可以申请成功。

2.链表的分类

2.1单链表

链表的定义里讲过，链表是零散的数据块串联到一起，这里的零散的数据块我们通常定义为节点。在单链表里，节点又包括一个数据域和一个指向下一个节点的指针，叫做后继指针 next

YyThFK.png

从单链表图中可以看出，有两个节点比较特殊，它们分别是第一个节点和和最后一个节点。第一个节点我们通常叫首节点，它保存了我们链表的基地址，有了首节点，我们就可以通过遍历获取到链表上的任意节点。最后一个节点通常叫尾节点，它的后继指针通常为空。

与数组一样，链表也支持 新增、删除和修改节点

• 新增节点

  1. 构造一个新节点newnode

  2. 遍历找到待插入位置的前一个节点prev

  3. 把新节点newnode的next指向待插入位置的前一个节点prev的下一个节点

  4. 然后把prev节点的next指向newnode

• 删除节点

  1. 遍历找到待删除节点的前一个节点prev

  2. 保存当前节点

  3. 把prev的next指向它的下下个节点

  4. 把当前节点的指针置空，为了更快的垃圾回收

• 修改节点

  修改节点就是遍历找到当前节点，并且修改当前节点的data域

2.1.1单链表的实现

package com.allen.dayup.arithmetic;

/**
 * @Auther: 20190598
 * @Date: 2020/5/7 10:47
 * @Description:
 */
public class LinkedList {

    private Node head;
    private int size;

    public LinkedList() {
        this.head = new Node();
        this.size = 0;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addHead(0);
        list.addHead(1);
        list.addHead(2);
        list.iterate();

        System.out.println(list.get(0));

        list.remove(1);
        System.out.println();
        list.iterate();

    }

    public Object get(int index){
        if( index > size || index < 0 ){
            throw new IndexOutOfBoundsException();
        }

        Node currentNode = head;

        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }

        return currentNode.data;
    }

    public void addHead(Object data){
        add(0,data);
    }

    public void addTail(Object data){
        add(size,data);
    }


    public void add(int index,Object data){
        if( index > size || index < 0 ){
            throw new IndexOutOfBoundsException();
        }
        int i = 0;

        size++;
        Node pred = head;
        for (int j = 0; j < index; j++) {
            pred = pred.next;
        }

        Node newNode = new Node(data);
        newNode.next = pred.next;
        pred.next = newNode;

    }

    public boolean remove(int index){
        if( index > size || index < 0 ){
            throw new IndexOutOfBoundsException();
        }

        Node pred = head;
        for (int j = 0; j < index; j++) {
            pred = pred.next;
        }

        Node currentNode = pred.next;
        pred.next = pred.next.next;
        currentNode = null;
        return true;

    }

    public void iterate(){

        Node pred = head;
        while ( pred.next != null){
            pred = pred.next;
            System.out.print(pred.data + ",");
        }
    }

    class Node {
        Node next;
        Object data;

        public Node() {
        }

        public Node(Object data) {
            this.data = data;
        }

        private boolean hasNext(){
            boolean result = false;
            if( next != null ){
                result = true;
            }
            return result;
        }
    }

}

2.2 循环链表

循环链表就是一种特殊的单链表，唯一的区别就是链表的尾指针不为null，而是指向链表的首指针。

当处理的数据具有环形的特点时，用循环链表就比较合适

2.3 双联表

双链表与单链表的区别是，双链表的每个节点包括一个前驱节点、一个后驱节点和一个数据域。

双链表相对于单链表的优势就在于，遍历节点时，可以重后往前遍历。比如java里的LInkedList，底层就用的双链表来实现的，当插入的元素比较靠近尾节点时，就从后往前遍历。

这是一种典型的用空间换时间的思想。

链表的应用

链表是一种非常基础的数据结构，比较常见的应用，像java里的LinkedList的实现，以及缓存里的LRU算法等等

小结

链表和数组都是比较基础的数据结构，都属于线性表。相对于数组来说，链表在插入和删除节点上更有性能优势。链表根据自身结构特点呢，又分为单链表、双链表和循环链表。