数据结构与算法-链表

r囧r小猫 2024-03-31 14:15 84阅读 0赞

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

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

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

**链表 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--;
        }
    }

**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));
        }

**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