首页 > 其他分享 >数据结构-链表带哨兵

数据结构-链表带哨兵

时间：2023-07-12 21:36:11浏览次数：45  
标签：Node prev int value next 链表 哨兵 数据结构 public

一.链表带哨兵

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() {
​        //匿名内部类->带名字的内部类
​        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;//下一个节点指针

​        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-要执行的操作
​    public void loop(Consumer<Integer> consumer) {
​        Node p = head;
​        while (p != null) {
​            consumer.accept(p.value);
​            p = p.next;
​        }
​    }
​    //遍历链表2
​    //Params:consumer-要执行的操作
​    public void loop2(Consumer<Integer> consumer) {
​        for (Node p = head; p != null; p = p.next){
​            consumer.accept(p.value);
​        }
​    }
​    //遍历链表3(递归遍历)
​    //Params:consumer-要执行的操作
​    public void loop3(Consumer<Integer>before,//没有哨兵
​                      Consumer<Integer>after){
​        recursion(head,before,after);
​    }
​    private void recursion(Node curr,//当前节点
​                           Consumer<Integer>before,Consumer<Integer>after){//某个节点要进行的操作
​        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);
​        }
​        根据索引查找
Params:index-索引
Returns:找到，返回该索引位置节点的值
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);//找到上一个节点
​        if(prev==null){
​            illegalIndex(index);
​        }
​        prev.next=new Node(value,prev.next);

​    }
​    //1.问题
​    //删除头节点
​    public void removeFirst() throws IllegalAccessException {
​     remove(0);
​    }
​    public void remove(int index) throws IllegalAccessException {
​        Node prev=findNode(index-1);//上一个节点
​        if(prev==null){
​            illegalIndex(index);
​        }
​        Node removed=prev.next;//被删除的节点
​        if(removed==null){
​            illegalIndex(index);
​        }
​        prev.next=removed.next;

​    }
}

二.双向链表带哨兵

import java.util.Iterator;

//双向链表,带哨兵
public class shuju03 implements Iterable<Integer>{
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 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;
    }
  //根据值删除
   // 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;
    }



}

标签：Node,prev,int,value,next,链表,哨兵,数据结构,public
From： https://www.cnblogs.com/cgy-chen/p/17548890.html

相关文章

  • 说透MySQL：从数据结构到性能优化，附实际案例和面试题
    typora-copy-images-to:imgmysql索引第一章MySQL性能(掌握)1分析-数据库查询效率低下我们进入公司进行项目开发往往关注的是业务需求和功能的实现，但是随着项目运行的时间增加，数据量也就增加了，这时会影响到我们数据库的查询性能。所以我们要提高操作数据库的性能，有如下两种方式：1.......
  • 力扣-旋转链表
    1.问题描述给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。示例1:输入:1->2->3->4->5->NULL,k=2输出:4->5->1->2->3->NULL解释:向右旋转1步:5->1->2->3->4->NULL向右旋转2步:4->5->1->2->3->NULL 示例2:输入:0->1-&g......
  • 双链表实现
    题目实现一个双链表，双链表初始为空，支持$5$种操作：在最左侧插入一个数；在最右侧插入一个数；将第$k$个插入的数删除；在第$k$个插入的数左侧插入一个数；在第$k$个插入的数右侧插入一个数现在要对该链表进行$M$次操作，进行完所有操作后，从左到右输出整个链表。注意:题目中......
  • golang的list数据结构demo
    packagemainimport"container/list"funcmain(){varmylistlist.List//放在尾部mylist.PushBack("go")mylist.PushBack("grpc")mylist.PushBack("mysql")//头部放数据mylist.PushFront("gi......
  • 数据结构泛做
    为啥这个一向很讨厌ds题的人会在临考前做根号题呢,懂得都懂.(因为上课只有想这种不用脑子的东西才能想出来)10月15日CFeduF题不知道这题我为啥要想这么久,看来是应该好好休息一下了大意就是单点修改,询问[l,r]区间每个数的出现次数是否都是k的倍数第一,要知道分块是可以O(......
  • 数据结构学习2
    5、线性表的链式存储结构①定义链式存储:用一组任意的存储单元存储线性表中的数据元素。线性链表：用这种方法存储的线性表简称线性链表。特点:结点在存储器中的位置是随意的,即在逻辑上相邻的数据元素在物理上不一定相邻。实现:为了正确表示结点间的逻辑关系,在存储每个结点......
  • LeetCode 234. 回文链表
    classSolution{public:ListNode*reverse(ListNode*head)//翻转以head为头节点的链表{if(!head||!head->next)returnhead;autoa=head,b=head->next;while(b){autoc=b->next;b->next=a;......
  • Redis 数据结构 - 链表
    链表-List的底层实现链表提供了高效的节点重排能力，可以通过顺序访问的方式访问节点，并且支持增加删除节点调整长度。由于C语言原生并不支持链表，redis的链表是自己实现的。List的底层实现就是一个双向链表，支持从链表的两端进行push和pop操作，时间复杂度是O(1)。同时支持在......
  • docker 安装redis 6.0.8哨兵集群（一主两从三哨兵）
    准备三台主机并且安装了docker192.168.31.132192.168.31.134192.168.31.144linux版redis6.0.8下载下载地址：https://download.redis.io/releases/干啥用：拷贝出redis.conf文件，在此文件里配置主从关系，最好不要使用不同版本的配置文件，防止出现配置文件的参数不兼容问题安......
  • 数据结构与算法 #18 下跳棋，极富想象力的同向双指针模拟
    ⭐️本文已收录到AndroidFamily，技术和职场问题，请关注公众号[彭旭锐]和[BaguTreePro]知识星球提问。学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭将基于Java/Kotlin语言，为你分享常......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99