我正在参加创作者训练营第6期,点击了解活动概况

前语

在当时大环境的背景下面试不问点算法都不算个合格的面试了(),而与算法严密相关的数据结构也是经常问到的,像集合链表行列矩阵 等等等等。

是不是感觉难度如下:

  • 集合:有手就行
  • 链表:简简单单
  • 行列:根底操作
  • 二叉树:也还行吧
  • 平衡二叉树:普普通通
  • 红黑树:有点难度了
  • 堆/栈:难度提升了
  • :今天是高端局

这么一套组合拳下来,仍是有点难度的,本篇就先手写简简单单的链表,链表里有单向链表跟双向链表,会双向链表还能不会单向链表吗,直接上双向链表。

特点界说

双向链表的特点内容上节点prev跟下节点next是必定要有的,data特点我们运用泛型界说,这样一个双向链表的特点内容如下:

    private class Node<T>{
        private Node prev;
        private T data;
        private Node next;
        public Node(LinkedTable.Node prev,T data,LinkedTable.Node next){
            this.prev = prev;
            this.data = data;
            this.next = next;
        }
    }

上面是存储节点的结构,实际对外的类要设置头部节点跟尾部节点,这样可以直接选择从头或许从尾遍历。

    public Node headNode;
    public Node tailNode;

ADD办法

add办法没有返回值,在没有有参结构函数的情况下第一次进入add时类的特点内容都是空的,就是上面的headNodetailNode

add的第一步:要先根据add的内容创立Node目标,前节点是当时的尾部节点,下一个节点没有

    private void add(T data) {
        Node node = new Node<>(tailNode,data,null);
    }

add的第二步:判别headNodetailNode都为空时进行初始化

    private void add(T data) {
        Node node = new Node<>(tailNode,data,null);
        if (headNode == null && headNode == null){
            headNode = node;
            tailNode = node;
        }
    }

add的第三步:判别尾部节点是否为空,不为空将尾部节点的next指向创立节点,替换尾部节点为当时节点

    private void add(T data) {
        Node node = new Node<>(tailNode,data,null);
        if (headNode == null && headNode == null){
            headNode = node;
            tailNode = node;
        }else{
            if (tailNode != null){
                tailNode.next = node;
            }
            tailNode = node;
        }
    }

循环100次add办法进行验证,如下图:

手写一个泛型双向链表
尾部节点记录了循环最终一次的99,头部节点记录了循环第一次的0

DELETE办法

delete的第一步:界说局部变量引证头部节点,不影响头部跟尾部的节点方位

    private void delete(T data) {
        Node now = headNode;
    }

delete的第二步while循环判别now节点非空

    private void delete(T data) {
        Node now = headNode;
        while (now != null){
        }
    }

delete的第三步:循环内判别now节点data值是否等于参数值,如果是将上个节点的next指针指向当时的下个节点,意思就是爷爷直接指向孙子,爸爸被删除了,然后直接返回。不然当时节点指向下个节点继续循环。

    private void delete(T data) {
        Node now = headNode;
        while (now != null){
            if (now.data == data){
                now.prev.next = now.next;
                return;
            }
            now = now.next;
        }
    }

GET办法

既然放了数据必定要原封不动的取出来,界说一个get办法,代码跟上面的删除相同,无非是把第三步修正一下

    private T get(T data){
        Node<T> now = headNode;
        while (now != null){
            if (now.data == data){
                return now.data;
            }
            now = now.next;
        }
        return null;
    }

SET办法

set办法就当做覆盖更新,set指定方位的内容,这一步需求index标识。

    private boolean set(Integer index, T data){
        Node<T> now = headNode;
        AtomicInteger i = new AtomicInteger(0);
        while (now != null){
            if (i.getAndAdd(1) == index){
                now.data = data;
                return true;
            }
            now = now.next;
        }
        return false;
    }

验证:

add一个Map目标再add一个int值,这样链表的第一位为Map目标,再执行set办法将第一位Map目标修正为int8546

    public static void main(String[] args) {
        LinkedTable table = new LinkedTable();
        HashMap hashMap = new HashMap(){{
           put("哈喽","xxx");
        }};
        table.add(hashMap);
        table.add(1);
        System.out.println(table);
        table.set(0,8546);
        System.out.println(table);
    }

第一个断点:目前第一个节点目标特点仍是Map

手写一个泛型双向链表

第二个断点:现在第一个节点目标特点就变成了Integer

手写一个泛型双向链表

以上完成了一个双向链表根底的crud

发表回复

您的电子邮箱地址不会被公开。