一.鏈表帶哨兵

import java.util.Iterator;
import java.util.function.Consumer;
//帶哨兵
public class shuju02 implements Iterable<Integer> {//整體
    private Node head=new Node(666,null);//頭指針

?    @Override
?    public Iterator<Integer> iterator() {
?        //匿名內(nèi)部類->帶名字的內(nèi)部類
?        return new NodeIterator();
?    }
?    private class NodeIterator implements Iterator<Integer> {
?        Node p=head.next;

?        @Override
?        public boolean hasNext() {//是否有下一個元素
?            return p!=null;//不空返回真
?        }

?        @Override
?        public Integer next() {//返回當前值,并指向下一個元素
?            int v=p.value;
?            p=p.next;
?            return v;
?        }
?    }

?    private static class Node {
?        int value;//值
?        Node next;//下一個節(jié)點指針

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

?    public void addFirst(int value) throws IllegalAccessException {
?        //1.鏈表為空
?        // head=new Node(value,null);
?        //2.鏈表非空(頭插)
?       /* head = new Node(value, head);*/
?        insert(0,value);
?    }

?    //遍歷鏈表
?    //Params:consumer-要執(zhí)行的操作
?    public void loop(Consumer<Integer> consumer) {
?        Node p = head;
?        while (p != null) {
?            consumer.accept(p.value);
?            p = p.next;
?        }
?    }
?    //遍歷鏈表2
?    //Params:consumer-要執(zhí)行的操作
?    public void loop2(Consumer<Integer> consumer) {
?        for (Node p = head; p != null; p = p.next){
?            consumer.accept(p.value);
?        }
?    }
?    //遍歷鏈表3(遞歸遍歷)
?    //Params:consumer-要執(zhí)行的操作
?    public void loop3(Consumer<Integer>before,//沒有哨兵
?                      Consumer<Integer>after){
?        recursion(head,before,after);
?    }
?    private void recursion(Node curr,//當前節(jié)點
?                           Consumer<Integer>before,Consumer<Integer>after){//某個節(jié)點要進行的操作
?        if(curr==null){
?            return;
?        }
?        before.accept(curr.value);
?        recursion(curr.next,before,after);//放前邊倒敘,放后面順序->指這句話
?        after.accept(curr.value);
?    }

?    private Node findLast(){
?        Node p;
?        for(p=head;p.next!=null;p=p.next){

?        }
?        return p;
?    }
?    public void addLast(int value){
?        Node last=findLast();
?        last.next=new Node(value,null);
?    }
  /* public void test(){
?        int i=0;
?        for(Node p=head;p!=null;p=p.next,i++){
?            System.out.println(p.value+"索引是:"+i);
?        }
?        根據(jù)索引查找
Params:index-索引
Returns:找到，返回該索引位置節(jié)點的值
Throws:IlLegalArgumentException-找不到，拋出index非法異常
   }*/

?    private Node findNode(int index){//給定索引位置
?        int i=-1;
?        for(Node p=head ;p!=null;p=p.next,i++){
?            if(i==index){
?                return p;
?            }
?        }
?        return null;//沒找到
?    }
?    public int get(int index) throws IllegalAccessException {
?        Node node=findNode(index);
?        if(node==null){
?            //拋異常
?            illegalIndex(index);
?        }
?        return node.value;
?    }
?    //異常處理(重點)
?    private static void illegalIndex(int index) throws IllegalAccessException {
?        throw new IllegalAccessException(
?                String.format("index[%d] 不合法%n", index)
?        );
?    }


?    /*
向索引位置插入
 */
?    public void insert(int index,int value) throws IllegalAccessException {
?        Node prev=findNode(index-1);//找到上一個節(jié)點
?        if(prev==null){
?            illegalIndex(index);
?        }
?        prev.next=new Node(value,prev.next);

?    }
?    //1.問題
?    //刪除頭節(jié)點
?    public void removeFirst() throws IllegalAccessException {
?     remove(0);
?    }
?    public void remove(int index) throws IllegalAccessException {
?        Node prev=findNode(index-1);//上一個節(jié)點
?        if(prev==null){
?            illegalIndex(index);
?        }
?        Node removed=prev.next;//被刪除的節(jié)點
?        if(removed==null){
?            illegalIndex(index);
?        }
?        prev.next=removed.next;

?    }
}

二.雙向鏈表帶哨兵

import java.util.Iterator;

//雙向鏈表,帶哨兵
public class shuju03 implements Iterable<Integer>{
static class Node{
    Node prev;//上一個節(jié)點指針
    int value;
    Node next;//下一個節(jié)點指針

    public Node(Node prev, int value, Node next) {
        this.prev = prev;
        this.value = value;
        this.next = next;
    }
}
private Node head;//頭哨兵
private Node tail;//尾哨兵

    public shuju03(){
        head=new Node(null,666,null);
        tail=new Node(null,666,null);
       head.next=tail;
       tail.prev=head;
    }

    private Node findNode(int index){
        int i=-1;
        for(Node p=head;p!=tail;p=p.next,i++){
            if(i==index){
                return p;
            }
        }
        return null;
    }

    public void addFirst(int value) throws IllegalAccessException {
        insert(0,value);
    }
    public void removeLast() throws IllegalAccessException {
        Node removed=tail.prev;
        if(removed==head){
            illegalIndex(0);
        }
        Node prev=removed.prev;
        prev.next=tail;
        tail.prev=prev;
    }


    public void addLast(int value){
     Node last=tail.prev;
     Node added=new Node(last,value,tail);
     last.next=added;
     tail.prev=added;
    }

    public void insert(int index,int value) throws IllegalAccessException {
        Node prev=findNode(index-1);
        if(prev==null){
           illegalIndex(index);
        }
        Node next=prev.next;
        Node inserted=new Node(prev,value,next);
        prev.next=inserted;
        next.prev=inserted;
    }

    public void remove(int index) throws IllegalAccessException {
        Node prev=findNode(index-1);
        if(prev==null){
            illegalIndex(index);
        }
        Node removed=prev.next;
        if(removed==tail){
            illegalIndex(index);
        }
        Node next=removed.next;

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

    }
    private static void illegalIndex(int index) throws IllegalAccessException {
        throw new IllegalAccessException(
                String.format("index[%d] 不合法%n", index)
        );
    }
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p=head.next;
            @Override
            public boolean hasNext() {
                return p!=tail;
            }

            @Override
            public Integer next() {
                int value=p.value;
                return value;
            }
        };
    }
}

三.雙向鏈表

import java.util.Iterator;

public class shuju04 implements Iterable<Integer> {
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p=sentinel.next;
            @Override
            public boolean hasNext() {
                return p!=sentinel;
            }

            @Override
            public Integer next() {
                int value= p.value;
                p=p.next;
                return value;
            }
        };
    }

    /*
           s->1->2->3->1->s
             */
    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 shuju04(){
            sentinel.prev=sentinel;
            sentinel.next=sentinel;
        }
        //添加到第一個
    //Params value-待添加值
    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;
    }
    //添加到最后一個
    //Params:value-待添加值
    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;
    }
    //刪除第一個
    public void removeFirst() {
            Node removed=sentinel.next;
            if(removed==sentinel){
                throw new IllegalArgumentException("非法");
            }
            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("非法");
            }
            Node a=removed.prev;
            Node b=sentinel;

            a.next=b;
            b.prev=a;
    }
  //根據(jù)值刪除
   // Params:value-目標值
    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;
    }
    private Node findByValue(int value){
           Node p=sentinel.next;
           while(p!=sentinel){
               if(p.value==value){
                   return p;
               }
               p=p.next;
           }
           return null;
    }



}

文章來源地址http://www.zghlxwxcb.cn/news/detail-551150.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-鏈表帶哨兵的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！