投稿
  1. 首页
  2. java

[双向链表]实现一个双向链表

code • 2022-5-15 • java • 阅读 16

[双向链表]实现一个双向链表,第1张

文章目录
  • 学习内容
  • 完整代码：
  • 代码分解：

学习内容

使用java实现一个双向链表的增删改查

完整代码： 
//双向链表的节点，需要记录next和prev
class Node{
    int val;
    Node next;
    Node prev;

    public Node(int val){
        this.val = val;
    }

}
//实现一个双向链表
public class MyLinkedList {
    //记录头节点的位置
    private Node head;
    //记录尾节点的位置
    private Node tail;
    //链表的元素个数
    private int length;

    public MyLinkedList(){
        //此处没有使用傀儡节点
        head = null;
        tail = null;
    }

    public int length(){
        return this.length;
    }

//插入节点
    //头插
    public void addFirst(int val){
        Node newNode = new Node(val);
        if(head == null) {
            head = newNode;
            tail = newNode;
            length++;
            return;
        }
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
            length++;
            return;
    }
    //尾插
    public void addTail(int  val){
        Node newNode = new Node(val);
        tail = head;
        if(head == null){
            head = newNode;
            tail = newNode;
            length++;
            return;
        }
        while (tail.next != null){
            tail = tail.next;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail =  newNode;
        length++;

    }
    //指定位置插入
    public void add(int index,int val){
        if(index < 0 || index > length){//如果index = length，就相当于尾插
            return;
        }
        if(index ==  0 ){//头插
            addFirst(val);
            return;
        }
        if(index == length){//尾插
            addTail(val);
            return;
        }
        Node newNode = new Node(val);
        Node nextNode = getNode(index);
        Node prevNode = newNode.prev;
        /**
         * 接下来要往cur之前插入newNode，因为要让newNode的下标变为val;
         * 如果是cur之后，那就变成了val＋1
         */
        prevNode.next = newNode;
        newNode.prev = prevNode;

        newNode.next = nextNode;
        nextNode.prev = newNode;
        length++;
    }


//删除
    public void removeByIndex(int index) {
        if(index < 0 || index >= length || head == null){
            return;
        }
        //头删
        if(head.next == null){
            head = null;
            tail = null;
            length = 0;
            return;
        }
        if(index == 0){
            Node newNode = head;
            newNode = newNode.next;
            newNode.prev = null;
            head = newNode;
            return;
        }
        //尾删
        if(index == length - 1){
            Node newNode = head;
            while (newNode.next != null){
                newNode = newNode.next;
            }
            newNode.prev.next = null;
            tail = newNode.prev;
            length--;
            return;
        }
        Node newNode = getNode(index);

        newNode.prev.next = newNode.next;
        newNode.next.prev = newNode.prev;
        length--;
    }
    public void removeByValue(int val){

        int index = indexof(val);
        if(index == -1){
            return;
        }
        removeByIndex(index);
    }

//查找
    public int get(int index){
        return getNode(index).val;
    }

    public int indexof(int val){
        if(head == null){
            return -1;
        }
        Node cur = head;
        for(int i = 0;i < length;i++){
            if(cur.val == val){
                return i;
            }
            cur = cur.next;
        }
        return -1;
    }

//根据取下标得到节点
    public Node getNode(int index){
        if(index < 0 || index >= length || head == null){
            return null;
        }
        Node cur = head;
        for(int i = 0;i < index;i++){
            cur = cur.next;
        }
        return cur;
    }

//修改
    public void set(int index,int val){
        Node cur = getNode(index);
        cur.val = val;

    }
    //给定值查找下标
    public int getIndex(int val){
        if(head == null){
            return -1;
        }
        for(int i = 0; i < length;i++){
            if(head.val == val){
                return i;
            }
            head = head.next;
        }
        return -1;
    }
}
代码分解：
  • 建立一个Node类,因为是双向链表，所以需要一个next，一个prev
//双向链表的节点，需要记录next和prev
class Node{
    int val;
    Node next;
    Node prev;

    public Node(int val){
        this.val = val;
    }
}
  • 设置参数
    //记录头节点的位置
   private Node head;
   //记录尾节点的位置
   private Node tail;
   //链表的元素个数
   private int length;

   public MyLinkedList(){
       //此处没有使用傀儡节点
       head = null;
       tail = null;
   }

   public int length(){
       return this.length;
   }
  • 增 —— 头插插入节点
    原理如上图，其他插入也是同理，因为是双向链表，所以next和prev指向什么都要写清楚，最后对相应的变量进行更新。
public void addFirst(int val){
       Node newNode = new Node(val);chu
       if(head == null) {
           head = newNode;
           tail = newNode;
           length++;
           return;
       }
       //双向链表
           newNode.next = head;
           head.prev = newNode;
           head = newNode;
           length++;
           return;
   }
  • 尾插
 public void addTail(int  val){
       Node newNode = new Node(val);
       tail = head;
       if(head == null){
           head = newNode;
           tail = newNode;
           length++;
           return;
       }
       while (tail.next != null){
           tail = tail.next;
       }
       tail.next = newNode;
       newNode.prev = tail;
       tail =  newNode;
       length++;

   }
  • 指定位置插入：
//根据取下标得到节点,这步后面会多次用到，为了方便，所以单独写成一个方法。
   public Node getNode(int index){
       if(index < 0 || index >= length || head == null){
           return null;
       }
       Node cur = head;
       for(int i = 0;i < index;i++){
           cur = cur.next;
       }
       return cur;
   }

public void add(int index,int val){
       if(index < 0 || index > length){//如果index = length，就相当于尾插
           return;
       }
       if(index ==  0 ){//头插
           addFirst(val);
           return;
       }
       if(index == length){//尾插
           addTail(val);
           return;
       }
       Node newNode = new Node(val);
       Node nextNode = getNode(index);//调用上面的方法
       Node prevNode = newNode.prev;
       /**
        * 接下来要往cur之前插入newNode，因为要让newNode的下标变为val;
        * 如果是cur之后，那就变成了val＋1
        */
       prevNode.next = newNode;
       newNode.prev = prevNode;

       newNode.next = nextNode;
       nextNode.prev = newNode;
       length++;
   }

指定位置插入考虑的较多，如果指定的 位置为0，即为头插，则调用尾插的方法，如果指定的 位置和 他的长度一样，即为尾插，则调用尾插的方法。

  • 删除和查找
//根据给定的下标得到节点
   public Node getNode(int index){
       if(index < 0 || index >= length || head == null){
           return null;
       }
       Node cur = head;
       for(int i = 0;i < index;i++){
           cur = cur.next;
       }
       return cur;
   }

//根据给定的值查找下标
 public int indexof(int val){
       if(head == null){
           return -1;
       }
       Node cur = head;
       for(int i = 0;i < length;i++){
           if(cur.val == val){
               return i;
           }
           cur = cur.next;
       }
       return -1;
   }


//根据下标删除
 public void removeByIndex(int index) {
       if(index < 0 || index >= length || head == null){
           return;
       }
       //头删
       if(head.next == null){
           head = null;
           tail = null;
           length = 0;
           return;
       }
       if(index == 0){
           Node newNode = head;
           newNode = newNode.next;
           newNode.prev = null;
           head = newNode;
           return;
       }
       //尾删
       if(index == length - 1){
           Node newNode = head;
           while (newNode.next != null){
               newNode = newNode.next;
           }
           newNode.prev.next = null;
           tail = newNode.prev;
           length--;
           return;
       }
//非头删和尾删
       Node newNode = getNode(index);//通过getNode方法，找到下标为index的节点，进行删除
       newNode.prev.next = newNode.next;
       newNode.next.prev = newNode.prev;
       length--;
   }
   
   //根据值删除
   public void removeByValue(int val){
       int index = indexof(val);//通过indxof方法找到值为val所对应的下标，此时根据值删除就转化为了根据下标删除
       if(index == -1){
           return;
       }
       removeByIndex(index);//此时就可以调用上面的根据下标删除方法 
   }
  • 修改
//根据取下标得到节点
  public Node getNode(int index){
      if(index < 0 || index >= length || head == null){
          return null;
      }
      Node cur = head;
      for(int i = 0;i < index;i++){
          cur = cur.next;
      }
      return cur;
  }

//修改，根据给定的下标找到对应的 节点，然后修改该节点存储的值
  public void set(int index,int val){
      Node cur = getNode(index);
      cur.val = val;

  }
  • 查找
//根据取下标得到节点
   public Node getNode(int index){
       if(index < 0 || index >= length || head == null){
           return null;
       }
       Node cur = head;
       for(int i = 0;i < index;i++){
           cur = cur.next;
       }
       return cur;
   }

//给定下标进行查找，此时可以调用上面的方法，找到下标对应的节点，然后将该节点的值返回
   public int get(int index){
       return getNode(index).val;
   }

//给定值查找下标
public int getIndex(int val){
       if(head == null){
           return -1;
       }
       for(int i = 0; i < length;i++){
           if(head.val == val){
               return i;
           }
           head = head.next;
       }
       return -1;
   }

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/906238.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-15
下一篇 2022-05-15

发表评论

登录后才能评论

评论列表（0条）

保存