链表的基础知识

单链表插入：cur.next、newNode.next都是引用，不改变值，只改变位置
public void insertHead(int data){      //插入链表的头部     data就是插入的数据
   ListNode newNode = new ListNode(data);
   //如果原来就有数据呢？
   newNode.next = head;      //栈内存的引用
   head = newNode;
   
   //插入O(1)
}

public void insertNth(int data,int position){     //插入链表的中间 假设定义在第N个插入 O(n)
   if(position == 0) {       //这个表示插入在头部了
      insertHead(data);
   }else{
      ListNode cur = head; // 表示当前节点
      for(int i = 1; i < position ; i++){ 因为是<，从head开始,所以要往后取
         cur = cur.next;       //一直往后遍历   p=p->next;  ->是c++里面的往后找指针
      }
      ListNode newNode = new ListNode(data);
      // 新加的节点的后面指向之前的节点
      newNode.next = cur.next;      //新加的点指向后面 保证不断链
      cur.next = newNode;          //把当前的点位置指向新加的点
   }
}

单链表删除：

public void deleteHead(){//O(1)
   head = head.next; // 头节点的下一个指向头节点
}

public void deleteNth(int position){//O(n)
   if(position == 0) { // 删除头节点
      deleteHead();
   }else{
      ListNode cur = head; 
      for(int i = 1; i < position ; i ++){ // 小于号，要取到下一个节点
         cur = cur.next; 
      }

      cur.next = cur.next.next; //cur.next 表示的是删除的点，后一个next就是我们要指向的
   }
}

双向链表的插入：

public void inserHead(int data){
   DNode newNode = new DNode(data);
   if(head == null){
      tail = newNode;
   }else{
      head.pre = newNode;
      newNode.next = head;
   }
   head = newNode;
}

双向链表的删除：

public void deleteHead(){
   if(head == null) return ;     //没有数据
   if(head.next == null){    //就一个点
      tail = null;
   }else{
      head.next.pre = null;  
   }
   head = head.next;
}
public void deleteKey(int data){
   DNode current = head;
   while (current.value != data) {
      if (current.next == null) {
         System.out.println("没找到节点");
         return ;
      }
      current = current.next;  // current表示当前要删除的节点
   }
   if (current == head) {// 指向下个就表示删除第一个
      deleteHead();
   } else {
      current.pre.next = current.next;
      if(current == tail){      //删除的是尾部
         tail = current.pre;
         current.pre = null;
      }else{
         current.next.pre = current.pre;
      }
   }
}