链表的增删

单向链表的每一个结点包含两部分，一部分是存放数据的变量data，另一部分是指向下一个结点的指针next。

private static class Node {
    int data;
    Node next;
}

​

链表的第1个结点被称为头结点，最后1个结点被称为尾结点，尾结点的next指针指向空。

双向链表除了有data和next指针，还有指向前置结点的prev指针。

链表在内存中的存储方式则是随机存储。

​

链表的查询

从头部结点开始，向后一个一个结点逐一查找。

//查询链表
public Node search(int index) throws IndexOutOfBoundsException{
    if (index<0 || index>=size) {
        throw new IndexOutOfBoundsException("search：index超出链表范围！");
    }

    Node searchNode;
    if (index == 0) {   //头部查询
        searchNode = head;
    } else if (index == size - 1) {     //尾部查询
        searchNode = tail;
    } else {    //中间查询
        searchNode = head;
        for (int i = 0;i<index;i++) {
            searchNode =searchNode.next;
        }
    }

    return searchNode;
}

链表的插入

链表插入结点时，分为3种情况：

• 头部插入
• 尾部插入
• 中间插入

头部插入，将新结点的next指针指向head结点，再让head结点指向新结点。
尾部插入，将tail结点的next指针指向新结点，再让tail结点指向新结点。

中间插入，找到新结点要插入的index的前置结点，新结点的next指向前置结点的next，前置结点的next指向新结点。

//插入链表
    public void insert(int data,int index) throws IndexOutOfBoundsException {
        if (index<0 || index>size) {
            throw new IndexOutOfBoundsException("insert：index超出链表范围！");
        }

        Node insertNode = new Node(data);
        //第一个结点
        if (size==0) {
            head = insertNode;
            tail = insertNode;
            size ++;
            return;
        }

        if (index == 0) {   //插入头部
            insertNode.next = head;
            head = insertNode;
        }else if (index == size) {  //插入尾部
            tail.next = insertNode;
            tail = insertNode;
        }else {    //插入中间
            Node prev = search(index-1);
            Node next = prev.next;
            prev.next = insertNode;
            insertNode.next = next;
        }

        size++;
    }

​

链表的删除

链表删除结点时，分为3种情况：

• 头部删除
• 尾部删除
• 中间删除

//链表的删除
	public void delete(int index) throws IndexOutOfBoundsException {
        if (index<0 || index>=size) {
            throw new IndexOutOfBoundsException("delete：index超出链表范围！");
        }

        //只有一个结点
        if (size==1) {
            head = null;
            tail = null;
            size--;
            return;
        }

        if (index == 0) {   //删除头部结点
            head = head.next;
        } else if (index == size-1) {   //删除尾部结点
            Node prev = search(index-1);
            prev.next = null;
            tail = prev;
        } else {    //删除中间结点
            Node prev = search(index-1);
            Node next = prev.next.next;
            prev.next = next;
        }

        size--;
    }