1. 单链表概念

对于所有的数据结构的基础都是创建+增删改查，学习链表重点也是学习链表的五种基本操作。

单向链表就像一个铁链一样，元素之间相互连接，包含多个结点，每个结点有一个指向后继元素的next指针。表中最后一个元素的next指向null。如下图：

对于单链表而言，一个结点只能有一个后继结点，但是可以多个结点指向同一个后继结点，如下图中c1被a2和b3同时指向。

在下图中c1结点有多个后继结点，则不满足链表的定义。

2. 创建链表

public class ListNode {
        private int data;
        private ListNode next;

        public ListNode(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }
    }

如果按照Java面向对象的理论，一个类中的属性权限修饰符应该为private，这体现了封装特性，别的方法想操作类ListNode中的值，只能通过类ListNode提供的get、set方法来实现。

/**
 * 单链表的定义
 * @author jay
 */
public class ListNode {
    public int value;
    public ListNode next;

    public ListNode(int value) {
        this.value = value;
        next = null;
    }
}

通常的链表定义如上所示，属性权限修饰符为public，创建对象后能直接使用ListNode.value 和ListNode.next来操作，虽然违背了面向对象的设计要求，但是使得该代码更为精简，在算法题中广泛应用。

3. 链表的增删改查

3.1. 遍历链表

    /**
     * 获取链表长度
     * @param head 链表头节点
     * @return 链表长度
     */
    public static int getLength(ListNode head) {
        int length = 0;
        ListNode listNode = head;
        while (listNode != null) {
            length++;
            listNode = listNode.next;
        }
        return length;
    }

3.2. 链表插入

3.2.1. 表头插入

（1）创建新结点newNode

（2）将新结点newNode连接到原来链表中的头结点，newNode.next = head

（3）将头指针指向新结点newNode，head = newNode

3.2.2. 中间插入

如果我们想在值为7的结点前插入新的结点，步骤如下

（1）创建新结点newNode

（2）找到7的前一个结点停下，newNode.next = listNode(15).next（图中虚线）

（3）15结点的下个结点指向newNode，listNode(15).next = newNode

步骤（2）和（3）顺序不能颠倒，假如先执行（3），便无法在找到结点7的地址，无法将newNode的将后续结点连接起来，见下图。

3.2.3. 结尾插入

（1）创建新结点newNode

（2）newNode.next = null

（3）将新结点newNode连接到原来链表中的尾结点，listNode(40).next = newNode

3.2.4. 代码

    /**
     * 链表插入
     * @param head       链表头节点
     * @param nodeInsert 待插入节点
     * @param position   待插入位置，取值从2开始
     * @return 插入后得到的链表头节点
     */
    public static ListNode insertNode(ListNode head, ListNode nodeInsert, int position) {
        // 需要判空，否则后面可能会有空指针异常
        if (head == null) {
            return nodeInsert;
        }
        // 越界判断
        int size = getLength(head);
        if (position > size + 1 || position < 1) {
            System.out.println("位置参数越界");
            return head;
        }

        // 在链表开头插入
        if (position == 1) {
            nodeInsert.next = head;
            // 将头指针指向新插入的这个结点 返回头指针
            head = nodeInsert;
            return head;
        }
        // 在链表中间插入和在链表结尾插入
        ListNode pNode = head;
        int count = 1;
        // 假如想插入的位置为5，那么需要找到位置4的结点并停下
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;

        return head;
    }

3.3. 链表删除

3.3.1. 删除表头结点

只需要执行head = head.next 就行了，如上图，将head向前移动一次之后，原来的结点不可达，会被JVM回收掉。

3.3.2. 删除最后一个结点

如果删除最后一个元素40，停在最后一个元素的前一个结点，直接执行cur.next = null，此时结点40变得不可达，最终会被JVM回收掉。

3.3.3. 删除中间结点

停在要删除元素的前一个结点，直接cur.next = cur.next.next，即可。

3.3.4. 代码

    /**
     * 删除节点
     * @param head     链表头节点
     * @param position 删除节点位置，取值从1开始
     * @return 删除后的链表头节点
     */
    public static ListNode deleteNode(ListNode head, int position) {
        if (head == null) {
            return null;
        }
        int size = getLength(head);
        if (position > size || position <1) {
            System.out.println("输入的参数有误");
            return head;
        }
        if (position == 1) {
            //curNode就是链表的新head
            return head.next;
        } else {
            ListNode cur = head;
            int count = 1;
            while (count < position - 1) {
                cur = cur.next;
                count++;
            }
            ListNode curNode = cur.next;
            cur.next = curNode.next;
        }
        return head;
    }