数据结构与算法-链表

什么是链表
链表是一种物理单元上非连续、非顺序的存储结构，这种结构中的元素逻辑顺序由指针进行确定。不同于数组需要先确定内存大小，链表可以充分利用内存空间。链表主要结构是一个数据对象，一个指针。数据对象保存用户数据，指针则是指向下一个节点，这样通过指针串联一个个数据节点形成一个链。

算法原理
节点包含数据对象和指针，数据对象保存用户数据，指针则指向下一个节点，下一个节点内部也包含同样的节点结构且指针指向下下个节点。

链表分类
根据功能和操作方式不同可以分为：
单向链表：每次从头部插入新的节点
双向链表：可以从头部、尾部插入新的节点
循环链表：最后一个节点的指针指向头节点

链表 VS 数组
1、存储结构链表不连续，数组连续
2、内存分配链表动态分配，数组静态分配
3、内存区域链表一般保存在堆区，数组一般情况下是保存在栈区
4、查询时间复杂度链表O(N)，数组根据下标索引时间复杂度为O(1)
5、插入删除时间复杂度链表找到节点直接操作为O(1),数组找到元素删除后需要移动保证顺序为O(N)

小试牛刀
本次我们仅模拟双向链表，其他类型链表大同小异
1、增加链表头部、尾部插入元素，并提供根据元素删除节点

/**
 * 双向链表模拟
 * @author senfel
 * @version 1.0
 * @date 2022/12/2 11:24
 */
@Slf4j
@Data
public class LinkedList {

    /**
     * 链表长度
     */
    private int size;
    /**
     * 链表头部
     */
    private Node head;
    /**
     * 链表尾部
     */
    private Node tail;

    /**
     * 节点
     */
    @Data
    private static class Node{
        /**
         * 数据
         */
        private Object dataObj;
        /**
         * 下一个节点
         */
        private Node next;

        public Node(Object dataObj, Node next) {
            this.dataObj = dataObj;
            this.next = next;
        }
    }


    public LinkedList() {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }

    /**
     * 是否为空
     * @author senfel
     * @date 2022/12/2 11:39
     * @return java.lang.Boolean
     */
    public Boolean isEmpty(){
        return this.size == 0;
    }

    /**
     * 头部插入
     * @param obj
     * @author senfel
     * @date 2022/12/2 11:40
     * @return void
     */
    public void addFirst(Object obj){
        //创建节点
        Node node = new Node(obj, null);
        if(this.isEmpty()){
            this.tail = node;
            this.head = node;
        }else{
            //链表存在数据
            node.next = this.head;
            this.head = node;
        }
        this.size++;
    }

    /**
     * 尾部插入
     * @param obj
     * @author senfel
     * @date 2022/12/2 13:38
     * @return void
     */
    public void addLast(Object obj){
        Node node = new Node(obj, null);
        if(this.isEmpty()){
            this.head = node;
            this.tail = node;
        }else{
            //链表存在数据
            this.tail.next = node;
            this.tail = node;
        }
        this.size++;
    }


    /**
     * 删除节点
     * @param obj
     * @author senfel
     * @date 2022/12/2 13:44
     * @return void
     */
    public void remove(Object obj){
        if(this.isEmpty()){
            throw new RuntimeException("链表为空");
        }
        if(this.size == 1){
            this.head = null;
            this.tail = null;
        }else{
            //头部节点 获取需要删除的节点 及其上节点
            Node currentNode = this.head;
            Node currentHead = null;
            while (!currentNode.getDataObj().equals(obj)){
                currentHead = currentNode;
                currentNode = currentNode.next;
            }
            //删除节点
            if(Objects.isNull(currentHead)){
                //需要删除的节点就是头节点
                this.head = currentNode.next;
            }else{
                currentHead.next = currentNode.getNext();
                if(this.tail.getDataObj().equals(obj)){
                    //删除的尾部节点
                    this.tail = currentHead;
                }
            }
        }
        this.size--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

2、提供测试插入删除方法

  /**
     * toString
     * @param list
     * @return
     */
    public static String to(LinkedList list){
        if(Objects.isNull(list)){
            return null;
        }
        StringBuffer buffer = new StringBuffer();
        Node currentNode = list.getHead();
        int i = 1;
        buffer.append("链表层级为：\n"+i+"级节点元素为："+currentNode.getDataObj()+"\n");
        while (Objects.nonNull(currentNode.next)){
            i++;
            currentNode = currentNode.next;
            buffer.append(""+i+"级节点元素为："+currentNode.getDataObj()+"\n");
        }
        return buffer.toString();
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        //模拟头部进入3个元素,尾部进入3个元素
        for(int i=0;i<6;i++){
            if(i<3){
                linkedList.addFirst(i);
            }else{
                linkedList.addLast(i);
            }
        }
        log.error("\n模拟头部进入3个元素,尾部进入3个元素完成,当前链表{}", to(linkedList));
        linkedList.remove(2);
        log.error("\n模拟任意删除头0元素{}", to(linkedList));
        linkedList.remove(5);
        log.error("\n模拟任意删除尾部5元素{}", to(linkedList));
        linkedList.remove(3);
        log.error("\n模拟任意删除中部3元素{}", to(linkedList));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

3、查看测试结构并展示链表数据结构

模拟头部进入3个元素,尾部进入3个元素完成,当前链表链表层级为：
1级节点元素为：2
2级节点元素为：1
3级节点元素为：0
4级节点元素为：3
5级节点元素为：4
6级节点元素为：5

模拟任意删除头2元素链表层级为：
1级节点元素为：1
2级节点元素为：0
3级节点元素为：3
4级节点元素为：4
5级节点元素为：5

模拟任意删除尾部5元素链表层级为：
1级节点元素为：1
2级节点元素为：0
3级节点元素为：3
4级节点元素为：4

模拟任意删除中部3元素链表层级为：
1级节点元素为：1
2级节点元素为：0
3级节点元素为：4