数据结构-单链表

链表使用地方较多，多出源码中均有出现的地方，毕竟链表作为基础数据结构在申请内存时比数组唯一好处就是不用申请连续内存（数组在内存中必须是连续的），因此掌握链表很有必要

下面以java代码为例 写了个简单的实现

package com.chinanums.hh.study.base;



public class SinglelinkedList {

    // 头结点
    private Node head;
    // 尾结点
    private Node tail;
    // 链表大小
    private int count;


    
    public void add(T data) {
        insert(new Node(data));
    }

    
    public void add(T data,int index){insert(new Node<>(data),index);}
   
    
    private void insert(Node tNode) {

        // 说明是第一次插入
        if (head == null) {
            head = tNode;
        } else {
            // 追加到队列尾部
            tail.next = tNode;
        }
        tail = tNode;
        count++;
    }

    
    private void insert(Node tNode, int index) {

        Node p = head;
        // 说明是第一次插入
        if (head == null) {
            head = tNode;
            tail = head;
            count++;
        } else {
            // 这个作为指针 记录查找到符合值的上一个节点
            Node q = null;
            int i = 0;
            while (p != null && i != index) {
                q = p;
                p = p.next;
                i++;
            }

            // 说明找到了
            if (p != null) {

                // q为null 说明即将插入的tNode是头结点
                if (q == null) {
                    tNode.next = head;
                    head = tNode;

                    // 插入到队列中间
                } else {
                    // q 上一个节点 改变上一个节点的next指向
                    q.next = tNode;
                    // 保持连贯 新节点next指向原节点p
                    tNode.next = p;
                }
                count++;

                // 插入到尾部
            } else if (q == tail) {
                tail.next = tNode;
                tail = tNode;
                count++;
            }
        }
    }

    
    public T find(int index) {
        // 获取当前队列中index的值
        if (index >= count || index < 0) {
            return null;
        }
        // 从头开始找
        Node p = head;
        int i = 0;
        // 如果链表中没有 那么while循环走完之后 p节点应该是个null
        while (p != null && i != index) {
            p = p.next;
            i++;
        }

        // p!=null  说明找到了符合下标的
        if (p != null) {
            return p.data;
        }

        return null;
    }


    
    public void remove(T data) {
        // 从头开始遍历查找删除
        Node p = head;
        // 这个作为指针 记录查找到符合值的上一个节点
        Node q = null;
        while (p != null && p.data != data) {
            q = p;
            p = p.next;
        }

        // 说明找到了
        if (p != null) {

            // 找到的节点可能是首尾 或者中间节点

            // q为null 说明即将删除的p是头结点
            if (q == null) {
                head = p.next;
            } else {
                // 删除节点的下一个节点引用赋值给上一个节点的next
                q.next = p.next;
            }
            count--;
        }
    }

    public int size() {
        return count;
    }

    
    private static class Node {
        // 数据
        private T data;
        private Node next;

        Node(T data) {
            this.data = data;
        }
    }

}

链表作为大厂面试笔试中较高的出现频率 我觉得也有必要学