链表简介前言

链表为数据结构中第二种基本结构，一般链表就是指在物理结构上非连续，非有序的数据结构，链表又分为单向链表和双向链表，单向链表一般可以如下定义

class Node{    // 链表节点存放数字    int data;    // 节点的后指针    Node next;}

结构图如下

因为单向链表搜索顺序只能由左到右，显然对检索效率有一定影响，这时候就要推出双向链表，顾名思义就是在单项链表的基础上新增一个prev前指针既可以向前搜索也可以向后搜索，定义如下

class Node1{    // 链表节点存放数字    int data;    // 节点的后指针    Node next;    // 节点的前指针    Node prev;}

结构图如下

链表的基本操作

为实现方便下面代码采用单项链表

链表插入操作

链表插入和数组插入同样需要考虑如下的问题

队头插入

将一个新的Node节点从链表的头部插入，注意这里不用像数组一样还需要移动其它元素，这个过程分为两步

将新的Node节点的next指针指向原Head头节点。链表Head头节点指向新Node节点。队尾插入

队尾插入和队头插入类似，同样分为两步

将新的Node节点next指针置为NULL。将原队尾节点的next指针指向新的Node节点中间插入

中间插入和其余两种完全不同，这个过程分为三个步骤

获取插入位置的前一个元素，因为链表是单向的，直接获取插入位置元素后将无法获取插入位置前的元素。将新Node节点的next指针指向需要插入的位置。将插入位置的前一个元素的next指针指向新的Node节点，形成链表。

按照这个思路整理代码如下

public class LinkedDemo {    /**     * 定义单向链表节点     */    private static class Node{        // 链表节点存放数字        int data;        // 链表的下一个节点        Node next;        public Node(int data){            this.data = data;            this.next = null;        }        @Override        public String toString() {            return "Node{" +                    "data=" + data +                    ", next=" + next +                    '}';        }    }    // 头指针    private Node head;    // 尾指针（为了尾部插入方便）    private Node last;    // 链表长度    private int size;    /**     * 链表插入     * @param index     * @param date     */    public void insert(int index,int date){        if (index < 0 || index > size){            throw new RuntimeException("下标值有误");        }        Node insertData = new Node(date);        if (size == 0){            // 空链表            head = insertData;            last = insertData;        } else if (index == 0){            // 队头插入            insertData.next = head;            head = insertData;        }else if(index == size){            // 队尾插入            last.next = insertData;            last = insertData;        }else {            // 链表中间插入            // 先要去获取index下标的前一个Node节点（注意不是index下标的节点）            Node indexNode = getIndexNode(index-1);            insertData.next = indexNode.next;            indexNode.next = insertData;        }        size++;    }    public void show(){        Node temp = head;        do {            System.out.println(temp.toString());            temp = temp.next;        }while (temp!=null);    }    /**     * 获取执行下标的Node节点     * @param index 下标应该位于[0,size)之间     * @return     */    public Node getIndexNode(int index){        Node temp = head;        for (int i = 0; i < index ; i++) {            temp = temp.next;        }        return temp;    }    public static void main(String[] args) {        LinkedDemo linkedDemo = new LinkedDemo();        linkedDemo.insert(0,12);        linkedDemo.insert(1,33);        linkedDemo.insert(2,45);        linkedDemo.insert(3,3);        linkedDemo.insert(0,999);        linkedDemo.show();    }}

理解了链表的插入操作，链表的删除操作也是类似了，同样分为三种方式

队头删除

队头节点就是head，那么删除步骤分为

获取队头节点的下一个节点newHead。将原对头节点的next指针置为NULL，对于JAVA语言对象回收由GC处理，所以只需要让Node对象无引用即可。将head头节点指向原头节点的下一个节点newHead。队尾删除

队尾删除的关键就是获取队尾的前一个节点，将队尾的前一个节点的next指针置为NULL即可。

中间删除

中间删除较为复杂分为如下几步

获取删除元素的前一个节点和后一个节点。将删除元素的next指向指向NULL。将删除元素的前一个节点指向删除元素的后一个节点。

综上删除代码如下

    /**     * 删除元素     */    public void delete(int index){        if (index < 0 || index >= size){            throw new RuntimeException("下标值有误");        }        if (index == 0){            // 队头删除            Node next = head.next;            head.next = null;            head = next;        }else if (index == size){            // 队尾删除            // 获取队尾的前一个节点            Node node = getIndexNode(index - 1);            last = node;        }else {            // 获取index节点的前一个节点            Node beforeNode = getIndexNode(index - 1);            // 获取index节点的后一个节点            Node afterNode = beforeNode.next.next;            // index下标的节点            Node node = beforeNode.next;            node.next = null;            beforeNode.next = afterNode;        }        size--;    }

至于查询和修改操作不涉及到指针变化，但由于链表的存储特点，所以查询和修改都需要遍历链表才能完成，所以查询和修改的时间复杂度为O(n)，而插入和删除的时间复杂度为O(1)，这正好和数组的特征相反。

综上数组的优点是快速定位所以读多写少的场景会很适合，而链表的优势在于插入和删除更加灵活。