数据结构与算法-链表

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

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

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

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