手写一个泛型双向链表

前言

在当前大环境的背景下面试不问点算法都不算个合格的面试了（卷），而与算法紧密相关的数据结构也是经常问到的，像集合、链表、树、图、栈、堆、队列、矩阵 等等等等。

是不是感觉难度如下：

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

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

属性定义

双向链表的属性内容上节点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;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13

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

    public Node headNode;
    public Node tailNode;
1
2

ADD方法

add方法没有返回值，在没有有参构造函数的情况下第一次进入add时类的属性内容都是空的，就是上面的headNode跟tailNode。

add的第一步：要先根据add的内容创建Node对象，前节点是当前的尾部节点，下一个节点没有

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

add的第二步：判断headNode跟tailNode都为空时进行初始化

    private void add(T data) {
        Node node = new Node<>(tailNode,data,null);
        if (headNode == null && headNode == null){
            headNode = node;
            tailNode = node;
        }
    }
1
2
3
4
5
6
7

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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

循环100次add方法进行验证，如下图：

尾部节点记录了循环最后一次的99，头部节点记录了循环第一次的0

DELETE方法

delete的第一步：定义局部变量引用头部节点，不影响头部跟尾部的节点位置

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

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

    private void delete(T data) {
        Node now = headNode;
        while (now != null){
        
        }
    }
1
2
3
4
5
6

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;
        }
    }
1
2
3
4
5
6
7
8
9
10

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;
    }
1
2
3
4
5
6
7
8
9
10

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12

验证：

先add一个Map对象再add一个int值，这样链表的第一位为Map对象，再执行set方法将第一位Map对象修改为int值8546

    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);
    }
1
2
3
4
5
6
7
8
9
10
11

第一个断点：目前第一个节点对象属性还是Map

第二个断点：现在第一个节点对象属性就变成了Integer

以上完成了一个双向链表基础的crud