java线性表（单向链表）

对于链表我们有很多种，有带头和不带头，双向和单项，循环和不循环。

我们实现的单向链表是不带头单向不循环链表。

链表不比顺序表，它可以连续也可以不连续，是链子型的每条链子两边都有节点（除首尾)。

单向链表的优缺点

1.它适用于增删，修改数据，时间复杂度是O（1）。

2.不适用于查找，时间复杂度是O（n），因为要从头找起。

单向链表的实现

单向链表有两个属性：一个是当前的数值，另一个是下一个节点的地址。

public class MySingleList {
    static class ListNode{
        public ListNode next;
        int value;


        public ListNode(int val){
            this.value = val;
        }
    }
 public ListNode head;
}

这里的head代表头节点。

一.增

1.头插和尾插

 public void addFirst(int data){
        ListNode listNode = new ListNode(data);
        listNode.next = head;
        head = listNode;

    }

头插只需将创建好的节点连接到当前的头节点，再将头节点设为新插入的节点。

其实链表的next就像一个带有方向的链子，通过next来使链子指向你想要指向的地址，我们会经常忽略这个问题，经常因为没有处理好next使链表变成了环形循环链表。

 public void addLast(int data){
        ListNode listNode = new ListNode(data);
        ListNode cur = head;
        if (cur == null){
            head = listNode;
            return;
        }
        while(cur.next != null){
            cur=cur.next;
        }
        cur.next = listNode;
    }

尾插就是通过头节点一直找到最后一个节点，进行插入操作，这也是链表不足的地方，因为顺序表有明确的位置可以直接找到尾部，而链表则需要从头找起，时间复杂度达到了O（n）。

2.任意插入

既然是任意插入插入的位置就得有讲究，我们得先判断是否合法，就像是顺序表处理下标一样。

在位置是头时，我们就用了头插的方法，这里我们用到了find..方法，该方法也体现了链表的特性。

作为链形的连接方式，就注定了一个节点断了，链表就毁了，所以在插入时我们得先找到前一个节点，让他先跟新节点连接起来，再让新节点连接下一个节点。

二.删

1.删除第一次出现key的节点

我们在删除时也是先要找到前一个节点，就像插入一样。

2.删除出现的所有key的节点

我们对比一项第一个方法和第二个方法，相似之处很多，只不过就是加了一个while循环。

三.查找

1.包含

2.查找指定数值的节点位置

这两个方法用到的都是一样的，还是通过遍历来查找数据key的位置。

四.改

改就是删除和添加的结合。