美文网首页
数数据结构入门——大师:链表(三)使用 dummyHead

数数据结构入门——大师:链表(三)使用 dummyHead

作者: Kino_7abb | 来源:发表于2019-01-28 23:14 被阅读0次

1.为什么用dummyHead虚拟头结点

对于add操作我们addFirst 总是和其他地方不一样,因为头结点是没有前一个结点的,因此我们要浪费一个空间使其为dummyHead这样链表总是以nul作为头结点


    /**
     * 内部类node,只有这个类可以访问到,用户不需要知道链表内部结构,
     * 也可以做成外部类
     */
    private class Node{
        public E e;
        /**
         * 指针 指向下一个节点
         */
        public Node next;

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }

        @Override
        public String toString(){
           return e.toString();
        }
    }

2.我们可以对链表初始化

//我们将第一个元素作为虚拟头结点
private Node dummyHead;

private int size;

    public LinkedList(){
        dummyHead = new Node(null, null);
        size = 0;
    }

3.添加元素

    public void add(int index, E e){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("error index");
        }
        Node prev = dummyHead ;
        //从第一个到要找的链表前面一个
        for(int i = 0; i <index; i++){
            prev = prev.next;
        }
        Node node = new Node(e);
           node.next = prev.next;
           prev.next = node;
    }

    public void addLast(E e){
        add(size,e);
    }

  
    public void addFirst(E e){
        add(0, e);
    }

这里我们主要add方法中的for循环为什么循环到index - 1

  • 这是因为我们有虚拟头结点,所以当index为0时候我们不需要循环,prev就是dummyhead 然后进行add操作
  • 如果index 为1的时候我们需要循环到0处....2时循环到1处.....这样每一个prev都是index前的一个结点
  • 同样有个虚拟头结点 get操作也很简单

4.get

 public E get(int index){
        if(index < 0 || index > size){
            throw new IllegalArgumentException("error index");
        }
        Node cur = dummyHead.next;
        for(int i = 0 ; i < index; i++){
            cur = cur.next;
        }
        return  cur.e;
    }

get(index)方法很简单 我们从虚拟头结点出发,每次指向的next正好是index处的位置,因此到index - 1处 cur.next刚好的是需要的元素我们只要 cur = cur.next;即可,同理得first和last很简单啦

 
    public E getFirst(){
        return get(0);
    }

    public E getLast(){
        return get(size);
    }

5.检查是否包含

 public boolean contains(E e){
        Node cur = dummyHead.next;
        while (cur!= null){
            if(cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

6.链表的删除

思路很简单 只要找到prev 然后将prev.next = delNode.next 然后delNode.next =null 方便JAVA的垃圾回收即可

相关文章

  • 数数据结构入门——大师:链表(三)使用 dummyHead

    1.为什么用dummyHead虚拟头结点 对于add操作我们addFirst 总是和其他地方不一样,因为头结点是没...

  • Redis有这一篇就够了

    Redis 数据结构 链表:列表建的底层实现(头指针和尾指针的双端链表) 字典:哈希键的底层实现 使用链地址法(数...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • Java数据结构算法(二)栈和队列

    本文旨作于收集整理使用!! 导航 Java数据结构算法(一)链表 Java数据结构算法(三)树 Java数据结构算...

  • 2017.5.25

    lua学习总结:数据结构: 使用Lua实现链表(单向链表和双向链表),队列 使用Lua保存图,用table保存,每...

  • HashMap常见面试题

    HashMap 的数据结构? 在JDK1.7里面,使用数组+链表的数据结构 在JDK1.8里面,使用数组+链表/红...

  • HashMap 1.7 和1.8区别

    一、数据结构区别 HashMap 1.7 使用数组+链表HashMap 1.8 使用Node数组+链表+红黑树(当...

  • 用Java写单向链表

    数据结构—单向链表 为了巩固自己的基础知识,这次就用 Java 来写一个单向链表。问:什么是单向链表?首先链表是数...

  • Redis-数据结构-对象

    对象 redis没有直接使用SDS、链表、字典、压缩列表、整数集合等数据结构来实现 键值对数据库,而是基于这些数...

  • 2018-12-01

    数据结构使用二级指针创建单链表以及单链表的各种操作 //单链表创建 #include #include #incl...

网友评论

      本文标题:数数据结构入门——大师:链表(三)使用 dummyHead

      本文链接:https://www.haomeiwen.com/subject/yjxtsqtx.html