链表

定义链表

public class ListNode {
    int val; //数据域
    ListNode next; //指针域
    ListNode(int val) { this.val = val; next=null;}//构造方法 指针域指向空
}

构造链表的方法

//headA [4,1,8,4,5]
ListNode headA = new ListNode(4);
headA.next = new ListNode(1);
ListNode c = new ListNode(8);
ListNode d = new ListNode(4);
ListNode e = new ListNode(5);
headA.next.next = c;
headA.next.next.next = d;
headA.next.next.next.next = e;

交叉链表

找到两个链表的交叉点(交叉点的地址相同)

public static ListNode arrayToList(int[] arr) {  
    // 1. 处理边界情况：数组为 null 或长度为 0，直接返回 null    if (arr == null || arr.length == 0) {  
        return null;  
    }  
  
    // 2. 创建链表头节点（用数组第一个元素初始化）  
    ListNode head = new ListNode(arr[0]);  
    // 3. 定义当前节点指针（初始指向头节点，用于遍历连接后续节点）  
    ListNode current = head;  
  
    // 4. 遍历数组剩余元素（从索引 1 开始），依次创建节点并连接  
    for (int i = 1; i < arr.length; i++) {  
        // 为当前数组元素创建新节点  
        ListNode newNode = new ListNode(arr[i]);  
        // 把当前节点的 next 指向新节点（连接）  
        current.next = newNode;  
        // 当前节点指针后移，指向新节点（准备下一次连接）  
        current = newNode;  
    }  
    // 5. 返回链表头节点（通过头节点可访问整个链表）  
    return head;  
}  
  
public static void printLinkedList(ListNode head) {  
    // 定义临时指针，避免修改原链表头节点  
    ListNode temp = head;  
    // 用 StringBuilder 拼接节点值，提升效率  
    StringBuilder sb = new StringBuilder();  
  
    while (temp != null) {  
        // 拼接当前节点值  
        sb.append(temp.val);  
        // 若不是最后一个节点，拼接 "->"        if (temp.next != null) {  
            sb.append(" -> ");  
        }  
        // 指针后移  
        temp = temp.next;  
    }  
    System.out.println("链表内容：" + sb.toString());  
}

手搓HashMap(好爽)

没考虑用红黑树了，实现起来太麻烦了，转二叉树倒是还能写

package org.example;  
  
import java.util.*;  
  
public class MyHashMap<K,V> {  
    // 默认初始容量（保持为2的幂）  
    static final int DEFAULT_INITIAL_CAPACITY = 16;  
    // 默认负载因子  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;  
    int size = 0;  
    Node<K,V>[] table = new Node[DEFAULT_INITIAL_CAPACITY];  
    public V put(K key, V value){  
        int hash = hash(key);  
        int index = indexFor(hash, table.length); // 单独的索引计算方法  
  
        Node<K,V> head = table[index];  
        if (head == null){  
            table[index] = new Node<>(hash, key, value);  
            size++;  
            resizeIfNecessary();  
            return null;  
        }  
  
        while(true){  
            // 先比较hash再比较key，提高效率  
            if (head.hash == hash && Objects.equals(head.key, key)){  
                V oldValue = head.value;  
                head.value = value;  
                return oldValue;  
            }  
            if (head.next == null) {  
                head.next = new Node<>(hash, key, value);  
                size++;  
                resizeIfNecessary();  
                return null;  
            }  
            head = head.next;  
        }  
    }  
  
  
    public V get(K key){  
        int hash = hash(key);  
        int index = indexFor(hash, table.length);  
        Node<K,V> head = table[index];  
  
        while (head != null){  
            if (head.hash == hash && Objects.equals(head.key, key)){  
                return head.value;  
            }  
            head = head.next;  
        }  
        return null;  
    }  
  
    public V remove(K key){  
        int hash = hash(key);  
        int index = indexFor(hash, table.length);  
        Node<K,V> head = table[index];  
  
        if (head == null) return null;  
        // 检查头节点  
        if (head.hash == hash && Objects.equals(head.key, key)){  
            table[index] = head.next;  
            size--;  
            return head.value;  
        }  
  
        Node<K,V> pre = head;  
        Node<K,V> cur = head.next;  
        while (cur != null){  
            if (cur.hash == hash && Objects.equals(cur.key, key)){  
                pre.next = cur.next;  
                size--;  
                return cur.value;  
            }  
            pre = pre.next;  
            cur = cur.next;  
        }  
        return null;  
    }  
  
    public boolean containsKey(K key){  
        int hash = hash(key);  
        int index = indexFor(hash, table.length);  
        Node<K,V> head = table[index];  
  
        while (head != null){  
            if (head.hash == hash && Objects.equals(head.key, key)){  
                return true;  
            }  
            head = head.next;  
        }  
        return false;  
    }  
  
    public int size(){  
        return size;  
    }  
  
    /**  
     * 哈希计算：高低16位异或  
     */  
    public int hash(K key){  
        if (key == null) return 0;  
        int h = key.hashCode();  
        // 关键改进：将高16位 与 低16位异或  
        return h ^ (h >>> 16);  
    }  
  
    /**  
     * 计算索引：利用位运算替代取模  
     */  
    private int indexFor(int hash, int length) {  
        return hash & (length - 1);  
    }  
  
    private void resizeIfNecessary(){  
        if (size <= table.length * DEFAULT_LOAD_FACTOR){  
            return;  
        }  
  
        // 扩容为当前容量的2倍（保持2的幂）  
        Node<K,V>[] newTable = new Node[table.length * 2];  
        for (Node<K, V> head : this.table) {  
            if (head == null) continue;  
            Node<K,V> cur = head;  
  
            while (cur != null){  
                Node<K,V> next = cur.next; // 先保存下一个节点  
                int newIndex = indexFor(cur.hash, newTable.length);  
  
                // 头插法迁移  
                cur.next = newTable[newIndex];  
                newTable[newIndex] = cur;  
                cur = next;  
            }  
        }  
        this.table = newTable;  
        System.out.println("扩容成功：" + table.length);  
    }  
  
    /**  
     * 节点类增加hash存储，减少重复计算  
     */  
    static class Node<K,V>{  
        final int hash; // 存储哈希值  
        final K key;  
        V value;  
        Node<K,V> next;  
  
        public Node(int hash, K key, V value){  
            this.hash = hash;  
            this.key = key;  
            this.value = value;  
        }  
    }  
}

手搓LRUCache(经典力扣LRU双向链表)

import java.util.*;  
  
class LRUCache {  
    public static void main(String[] args) {  
        //时间  
        long start = System.currentTimeMillis();  
        LRUCache lRUCache = new LRUCache(2);  
        lRUCache.put(1, 1); // 缓存是 {1=1}        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}        lRUCache.get(1);    // 返回 1        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}        lRUCache.get(2);    // 返回 -1 (未找到)  
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}        lRUCache.get(1);    // 返回 -1 (未找到)  
        lRUCache.get(3);    // 返回 3        lRUCache.get(4);    // 返回 4        long end = System.currentTimeMillis();  
        System.out.println("耗时：" + (end - start));  
    }  
  
    static class DoubleListNode {  
        int key;  
        int value;  
        DoubleListNode prev;  
        DoubleListNode next;  
        public DoubleListNode(){}  
        public DoubleListNode(int key, int value) {  
            this.key = key;  
            this.value = value;  
            this.prev = null;  
            this.next = null;  
        }  
    }  
    HashMap<Integer, DoubleListNode> cache = new HashMap<Integer, DoubleListNode>();  
    int size = 0;  
    DoubleListNode head;  
    DoubleListNode tail;  
    //初始化缓存容量  
    public LRUCache(int capacity) {  
        this.size = capacity;  
        head = new DoubleListNode();  
        tail = new DoubleListNode();  
        head.next = tail;  
        tail.prev = head;  
    }  
      
    public int get(int key) {  
        if (!cache.containsKey(key)){  
            return -1;  
        }  
        DoubleListNode SinceNode = cache.get(key);  
        removeNode(SinceNode);  
        addToHead(SinceNode);  
        return SinceNode.value;  
    }  
      
    public void put(int key, int value) {  
        if(cache.containsKey(key)){  
            DoubleListNode newNode = cache.get(key);  
            cache.remove(key);  
            removeNode(newNode);  
            newNode.value = value;  
            addToHead(newNode);  
            cache.put(key, newNode);  
        }else{  
            //缓存容量已满  
            if (size == cache.size()){  
                DoubleListNode prev = tail.prev;  
                removeNode(prev);  
                cache.remove(prev.key);  
            }  
            DoubleListNode newNode = new DoubleListNode(key, value);  
            cache.put(key, newNode);  
            addToHead(newNode);  
        }  
    }  
    //删除节点  
    public void removeNode(DoubleListNode node) {  
        node.prev.next = node.next;  
        node.next.prev = node.prev;  
    }  
    //添加到节点头部  
    public void addToHead(DoubleListNode node) {  
        node.prev = head;  
        node.next = head.next;  
        head.next.prev = node;  
        head.next = node;  
    }  
}