单链表

组成

每个节点 = 存储值 + 链接下一结点的引用字段

 
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { 
      val = x; 
    }
}

操作

若从链表头一直到尾都进行一次遍历，则需要O(N)时间，效率太低，那么该如何提升速度呢？多加一个变量－－头结点是一个很好的办法(头结点一般不设置值)。

插入操作

时间复杂度O(1)

要想插入一个新结点，我们只需要让新结点(cur)的指针先指向想插入地方的后者(next)，再让前者(prev)的指针指向新的结点(cur)，这样一个新的链接就形成了，是不是非常简单！

注意：一定要让新结点先与后方的结点连接上，试想看，如果先让prev直接指向cur会发生什么事情呢？直接进行连接的时候我们会发现，next直接会断掉，如果我们再想让cur连接上next是不是就于事无补了，这下好啦，根本就找不到next在哪里了(扶额苦笑)，如图

那假如我们有的时候就会忘记先连接后边怎么办呢，没关系！！！这有什么难的

我们直接先对这串链表进行一个存储的大动作，用另一个变量存起来，这样我想用就可以用咯，相当于拿了一个备份（虽然说浪费了一定的空间，但是不会再弄丢啦）

删除操作

时间复杂度O(N)

懂了插入操作之后，删除操作就更好理解了，操作链表的本质就是改变指针(引用)

我们假设想删除某一结点x，意思就是想要在链表中将x刨除，那么我们直接让指针越过该结点不就好了，让x的前指针(a)直接指向他的下一个结点(b)即可，删除操作就是这么简单！

特殊位置的增删改查

在开头增加结点

我们知道，头结点是链表在增删改查提高效率的一大关键，那么如果我们想要在某个链表的开头更新节点，应该怎么办呢

直接三步走

1. 初始化一个新结点 cur ；

2. 将新结点的后继指向头结点的后继；

3. 将头结点后继指向新结点 。

public void headInsert(int data){
  Node n = new Node(data);
  n.next = head.next;
  head.next = n;
  //head.next = new Node(data,head.next);
}

删除第一个结点

在已有链表上删除第一个结点

这还不简单，直接让头结点指向第二个节点即可

public void removeFirst(){
  Node first = head.next;
  head.next = first.next;
  //head.next = head.next.next;
 }

在末尾插入结点

这似乎比在开始的操作要复杂一些，但如果我们定义一个临时指针，让他做一个索引标记，指向实时位置，我们就知道现在遍历到何处了，这样就方便在尾巴进行插入操作啦

public void tailInsert(int data){
  Node temp = head;
  //遍历到结尾处
  while(temp.next!=null){
    temp = temp.next;
    }
  Node cur = new Node(data);
  cur = temp.next;
  //temp.next = new Node(data,null)
}

删除末尾结点

同理基础操作是遍历,但遍历只能让temp定位到最后一个结点，如果需要删除最后一个节点只能找到倒数第二个节点，让他的后继为空才行，于是需要多加一个变量找到temp的前一个结点（链表长度为空直接返回）

public void removeLast(){
    if(head.next==null){
        return;
    }
    Node temp = head.next;
    Node prev = head;
    while(temp.next!=null){
        prev = temp;
        temp = temp.next;
    }
    prev.next = null; 
}

头插头删 → 栈