Java数据结构---链表的基本用法（如创建等基本使用方法）

目录

一、单链表

（1）addFirst

（2）addLast

（3）遍历

（4）get

（5）insert

（6）removeFirst

（7）remove

二、双向链表

（1）insert

（2）remove

（3）addLast

（4） removeLast

三、双向环形链表

（1）添加

（2）删除首部和尾部

（3）删除或者寻找对应值的节点

---

一、单链表

//单向链表类
public class LinkedList {
    //头指针
    private Node head=null;
   private static class Node{
       int value;
       Node next;
       public Node(int value,Node next){
           this.value=value;
           this.next=next;
       }
   }

}

（1）addFirst

//头部添加元素
    public void addFirst(int value){
         head=new Node(value,head);
    }

（2）addLast

 //找到链表中的最后一个节点
    public Node findLast(){
       if(head==null){
           return null;
           //空链表
       }
       Node p;
       for(p=head;p.next!=null;p=p.next){
       }
       return p;
    }
    //向链表尾部添加元素
    public void addLast(int value){
       Node last=findLast();
       if(last==null){
           addFirst(value);
           return;
       }
       last.next=new Node(value,null);
    }

（3）遍历

//遍历链表
    public void loop(){
       Node p=head;
       while(p!=null){
           System.out.print(p.value+" ");
           p=p.next;
       }
       System.out.println();
    }

（4）get

获取指定索引的节点的value值。

这里注意一下findNode方法是获取指定索引处的节点，所以需要一个计量器i，让这个i=0开始，为什么呢？因为head其实就是第一个节点，后面双向链表计量i是=-1开始的，但是双向链表中的head并不是第一个节点，它的next才是第一个节点，所以一定要特别注意单向链表中的head与双向链表的head的区别（个人看法）

//找到指定索引处的节点
    public Node findNode(int index){

       int i=0;
       for(Node p=head;p.next!=null;p=p.next,i++){
           if(i==index){
               return p;
           }
       }
       return null;//没有找到该节点
    }
    //获取指定索引处的节点的值（value）
    public int get(int index){
       Node p=findNode(index);
       if(p==null){
           throw new IllegalArgumentException(String.format("index[%d]不合法",index));
       }
       return p.value;
    }

（5）insert

//向索引位置插入
    public void insert(int index,int value){
       if(index==0){
           addFirst(value);
       }
       //找到上一个节点
        Node prev=findNode(index-1);
       if(prev==null){
           throw new IllegalArgumentException(String.format("index[$d]不合法",index));
       }
       prev.next=new Node(value,prev.next);
    }

（6）removeFirst

//删除第一个节点
    public void removeFirst(){
       if(head==null){
           throw new IllegalArgumentException(String.format("index[0]不合法"));
       }
       head=head.next;
    }

（7）remove

  //删除指定索引处的节点
    public void remove(int index){
       if(index==0){
           removeFirst();
           return;
       }
       Node prev=findNode(index-1);//上一个节点
        if(prev==null){
            throw new IllegalArgumentException(String.format("索引异常"));
        }
        Node removed=prev.next;//被删除的节点
        if(removed==null){
            throw new IllegalArgumentException(String.format("索引异常"));
        }
        prev.next=removed.next;
    }

二、双向链表

//双向链表类
public class DoubleLinkedList {
     private Node head;
     private Node tail;

    private static class Node{
       Node prev;
       int value;
       Node next;
       public Node(Node prev,int value,Node next){
           this.prev=prev;
           this.value=value;
           this.next=next;
       }
    }
  //初始化
    public DoubleLinkedList(){
        head=new Node(null,100,null);
        tail=new Node(null,999,null);
        head.next=tail;
        tail.prev=head;
    }


}

（1）insert

在指定索引处添加

//找到指定索引处的节点
    private Node findNode(int index){
        int i=-1;
        for(Node p=head;p!=tail;i++,p=p.next){
            if(i==index){
                return p;
            }
        }
        return null;
    }
    //向指定位置添加节点
    public void insert(int index,int value){
        Node prev=findNode(index-1);
        if(prev==null){
            throw new IllegalArgumentException(String.format("索引异常"));
        }
        Node next=prev.next;
        Node inserted=new Node(prev,value,next);
        prev.next=inserted;
        next.prev=inserted;
    }

（2）remove

删除指定索引处的节点

//删除指定索引处的节点
    public void remove(int index){
        Node prev=findNode(index-1);
        if(prev==null){
            throw new IllegalArgumentException(String.format("索引异常"));
        }
        Node removed=prev.next;
        //如果删除的元素是尾哨兵
        if(removed==tail){
            throw new IllegalArgumentException(String.format("索引异常"));
        }
        Node next=removed.next;

        prev.next=next;
        next.prev=prev;
    }

（3）addLast

?向尾部添加节点

 //向尾部添加元素
   public void addLast(int value){
        Node last=tail.prev;
        Node added=new Node(last,value,tail);
        last.next=added;
        tail.prev=added;
   }

（4） removeLast

//删除最后一个节点
    public void removeLast(){
        Node removed=tail.prev;
        if(removed==head){
            throw new IllegalArgumentException(String.format("索引异常"));
        }
        Node prev=removed.prev;
        prev.next=tail;
        tail.prev=prev;
    }

三、双向环形链表

?双向环形链表（我这里说的是有哨兵节点的）不同的地方在于，尾结点的next指向了哨兵节点，哨兵节点的next指向的是第一个节点，哨兵节点的prev指向的是尾节点。

//双向环形链表
//注意是有哨兵节点sentinel
//sentinel.next是第一个节点，sentinel.prev是最后一个节点

public class DoubleSentinelList {

    private static class Node{
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node sentinel=new Node(null,-1,null);//哨兵节点
    //初始化
    public DoubleSentinelList(){
        sentinel.next=sentinel;
        sentinel.prev=sentinel;
    }
}

（1）添加

//向首部添加
    public void addFirst(int value){
        Node a=sentinel;
        Node b=sentinel.next;
        Node added=new Node(a,value,b);
        a.next=added;
        b.prev=added;
    }
    //向尾部添加
    public void addLast(int value){
        Node a=sentinel.prev;
        Node b=sentinel;
        Node added=new Node(a,value,b);
        a.next=added;
        b.prev=added;
    }

（2）删除首部和尾部

 //删除首部
    public void removeFirst(){
        Node removed=sentinel.next;
        if(removed==sentinel){
            throw new IllegalArgumentException(String.format("非法"));
        }
        Node a=sentinel;
        Node b=removed.next;
        a.next=b;
        b.prev=a;
    }
    //删除尾部
    public void removeLast(){
        Node removed=sentinel.prev;
        if(removed==sentinel){
            throw new IllegalArgumentException(String.format("非法"));
        }
        Node a=removed.prev;
        Node b=sentinel;
        a.next=b;
        b.prev=a;
    }

（3）删除或者寻找对应值的节点

//根据值寻找对应的节点
    public Node findByValue(int value){
        Node p=sentinel.next;
        while(p!=sentinel){
            if(p.value==value){
                return p;
            }
            p=p.next;
        }
        return null;
    }
    //根据值删除对应的节点
    public void removeByValue(int value){
        Node removed=findByValue(value);
        if(removed==null){
            return;//不用删除，因为没找到
        }
        Node a=removed.prev;
        Node b=removed.next;
        a.next=b;
        b.prev=a;
    }

?