单链表的实现与操作

单链表的实现与操作

• 节点

public class listNode {
    int val;
    listNode next;
    public listNode(int val){
        this.val=val;
        next=null;
    }
    public listNode(int val,listNode next){
        this.val=val;
        this.next=next;
    }
}

• 头插法

   public void headInsert(int val){
          listNode newNode=new listNode(val);
          listNode temp=head.next;
          head.next=newNode;
          newNode.next=temp;
          head.val++;
      }

• 尾插法

  private listNode getTail(){
          if(head.next==null)
              return head;
          listNode point=head.next;
          while (point.next != null){
              point=point.next;
          }
          return point;
      }
   public void tailInsert(int val){
          listNode newNode=new listNode(val);
          listNode point=getTail();
          point.next=newNode;
          head.val++;
      }

• 查找节点的位置

   public int localSearch(int val){
          int index=1;
          boolean flag=false;
          listNode point=head.next;
          while (point.val!=val&&point.next!=null){
              index++;
              point=point.next;
              if(point.val==val)
                  flag=true;
          }
          if (!flag)
              index=-1;
          return index;
      }

• 节点的删除(通过位置)

  public void localDelete(int posit){
          if(posit> head.val)
              return;
          listNode point=head;
          for(int i=0;i<posit-1;i++){
              point=point.next;
          }
          point.next=point.next.next;
          head.val--;
      }

• 节点删除(通过值)

  public void valueDelete(int val){
          listNode cur=head.next;
          boolean flag=true;
          while (cur!=null){
              if(cur.val==val){
                  flag=false;
                  break;
              }
              cur=cur.next;
          }
          if(flag)
              System.err.println("Does not have this value");
      }

• 判断链表是否为空

  public boolean isEmpty(){
          return head.next==null;
      }

• 销毁链表

    public void destroyList(){
          head.next=null;
      }

• 插入节点

  public void insert(int val,int posit){
          listNode point=head.next;
          if(posit>=head.val){
              tailInsert(val);
              return;
          }
          else if(posit<=1){
              headInsert(val);
              return;
          }
          for(int i=0;i<posit-2;i++){
              point=point.next;
          }
          listNode newNode=new listNode(val);
          listNode cur=point.next;
          point.next=newNode;
          newNode.next=cur;
      }

• 反转链表

  public void revers(){
          listNode prev = null;
          listNode curr = head.next;
          while (curr != null) {
              listNode next = curr.next;
              curr.next = prev;
              prev = curr;
              curr = next;
          }
          head.next=prev;
      }

• 完整代码

  package top.lphblog.list;
  public class List {
      private final listNode head=new listNode(0);//第一个节点存储链表的长度
      public void headInsert(int val){
          listNode newNode=new listNode(val);
          listNode temp=head.next;
          head.next=newNode;
          newNode.next=temp;
          head.val++;
      }
      public void display(){
          listNode point=head.next;
          while (point.next!=null){
              System.out.print(point.val+"-->");
              point=point.next;
          }
          System.out.println(point.val);
      }
      public int length(){
          return head.val;
      }
      private listNode getTail(){
          if(head.next==null)
              return head;
          listNode point=head.next;
          while (point.next != null){
              point=point.next;
          }
          return point;
      }
      public void tailInsert(int val){
          listNode newNode=new listNode(val);
          listNode point=getTail();
          point.next=newNode;
          head.val++;
      }
      public int localSearch(int val){
          int index=1;
          boolean flag=false;
          listNode point=head.next;
          while (point.val!=val&&point.next!=null){
              index++;
              point=point.next;
              if(point.val==val)
                  flag=true;
          }
          if (!flag)
              index=-1;
          return index;
      }
      public void localDelete(int posit){
          if(posit> head.val)
              return;
          listNode point=head;
          for(int i=0;i<posit-1;i++){
              point=point.next;
          }
          point.next=point.next.next;
          head.val--;
      }
      public boolean isEmpty(){
          return head.next==null;
      }
      public void destroyList(){
          head.next=null;
      }
      public void insert(int val,int posit){
          listNode point=head.next;
          if(posit>=head.val){
              tailInsert(val);
              return;
          }
          else if(posit<=1){
              headInsert(val);
              return;
          }
          for(int i=0;i<posit-2;i++){
              point=point.next;
          }
          listNode newNode=new listNode(val);
          listNode cur=point.next;
          point.next=newNode;
          newNode.next=cur;
      }
     public void revers(){
          listNode prev = null;
          listNode curr = head.next;
          while (curr != null) {
              listNode next = curr.next;
              curr.next = prev;
              prev = curr;
              curr = next;
          }
          head.next=prev;
      }
      public void valueDelete(int val){
          listNode cur=head.next;
          boolean flag=true;
          while (cur!=null){
              if(cur.val==val){
                  flag=false;
                  break;
              }
              cur=cur.next;
          }
          if(flag)
              System.err.println("Does not have this value");
      }
  
  }