数据结构与算法刷题——数据结构-基础(1.2)

发表于 分类于 ， 阅读时长 ≈ 7 分钟

一 概述

1
2
3
4
1. 实现一个栈 / 队列 / 链表
2. 实现 ArrayList（动态数组）
3. 实现 LinkedList（单向/双向）
4. 实现 HashMap / LRU 缓存机制

二 解答(仅供参考)

2.1 实现一个栈 / 队列 / 链表

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
一、栈（Stack）

import java.util.LinkedList;
public class MyStack<T> {
    private LinkedList<T> list = new LinkedList<>();

    public void push(T value) {
        list.addFirst(value);
    }

    public T pop() {
        return list.removeFirst();
    }

    public T peek() {
        return list.getFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}
 
二、队列（Queue）

import java.util.LinkedList;
public class MyQueue<T> {
    private LinkedList<T> list = new LinkedList<>();

    public void offer(T value) {
        list.addLast(value);
    }

    public T poll() {
        return list.removeFirst();
    }

    public T peek() {
        return list.getFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}

三、单向链表（LinkedList）
public class MyLinkedList {
    static class Node {
        int value;
        Node next;

        Node(int val) {
            value = val;
        }
    }

    private Node head;

    public void add(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }

    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

2.2 实现 ArrayList（动态数组）

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
一、自定义 MyArrayList 实现
public class MyArrayList<T> {
    private Object[] data;
    private int size = 0;
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList() {
        data = new Object[DEFAULT_CAPACITY];
    }

    public void add(T value) {
        ensureCapacity();
        data[size++] = value;
    }

    public T get(int index) {
        checkIndex(index);
        return (T) data[index];
    }

    public void remove(int index) {
        checkIndex(index);
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null; // 防止内存泄漏
    }

    public int size() {
        return size;
    }

    private void ensureCapacity() {
        if (size == data.length) {
            int newCapacity = data.length * 2;
            Object[] newData = new Object[newCapacity];
            System.arraycopy(data, 0, newData, 0, data.length);
            data = newData;
        }
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引超出范围: " + index);
        }
    }
}

二、简单测试代码：
public class Main {
    public static void main(String[] args) {
        MyArrayList<String> list = new MyArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        System.out.println("元素个数: " + list.size());
        System.out.println("第 1 个元素: " + list.get(0));
        list.remove(1);
        System.out.println("移除后第 2 个元素: " + list.get(1));
    }
}

2.3 实现 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
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
一、单向链表（Singly Linked List）

public class SinglyLinkedList {
    static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    private Node head;

    // 添加到尾部
    public void add(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = newNode;
    }

    // 删除指定值（只删除第一个）
    public void remove(int val) {
        if (head == null) return;
        if (head.val == val) {
            head = head.next;
            return;
        }
        Node cur = head;
        while (cur.next != null && cur.next.val != val) {
            cur = cur.next;
        }
        if (cur.next != null) {
            cur.next = cur.next.next;
        }
    }

    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}

二、双向链表（Doubly Linked List）
public class DoublyLinkedList {
    static class Node {
        int val;
        Node prev, next;

        Node(int val) {
            this.val = val;
        }
    }

    private Node head, tail;

    // 添加到尾部
    public void add(int val) {
        Node newNode = new Node(val);
        if (tail == null) {
            head = tail = newNode;
            return;
        }
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    // 删除指定值（只删除第一个）
    public void remove(int val) {
        Node cur = head;
        while (cur != null && cur.val != val) {
            cur = cur.next;
        }
        if (cur == null) return;

        if (cur.prev != null) cur.prev.next = cur.next;
        else head = cur.next;

        if (cur.next != null) cur.next.prev = cur.prev;
        else tail = cur.prev;
    }

    public void printForward() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void printBackward() {
        Node cur = tail;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.prev;
        }
        System.out.println();
    }
}

2.4 实现 HashMap / LRU 缓存机制

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
一、自定义 HashMap 简易版实现（基于链地址法）

public class MyHashMap<K, V> {
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;
        Node(K k, V v) {
            key = k;
            value = v;
        }
    }

    private Node<K, V>[] buckets;
    private int capacity = 16;

    public MyHashMap() {
        buckets = new Node[capacity];
    }

    public void put(K key, V value) {
        int index = indexFor(key);
        Node<K, V> cur = buckets[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        Node<K, V> newNode = new Node<>(key, value);
        newNode.next = buckets[index];
        buckets[index] = newNode;
    }

    public V get(K key) {
        int index = indexFor(key);
        Node<K, V> cur = buckets[index];
        while (cur != null) {
            if (cur.key.equals(key)) return cur.value;
            cur = cur.next;
        }
        return null;
    }

    public void remove(K key) {
        int index = indexFor(key);
        Node<K, V> cur = buckets[index], prev = null;
        while (cur != null) {
            if (cur.key.equals(key)) {
                if (prev == null) {
                    buckets[index] = cur.next;
                } else {
                    prev.next = cur.next;
                }
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }

    private int indexFor(K key) {
        return key.hashCode() & (capacity - 1);
    }
}

二、LRU 缓存机制（基于 HashMap + 双向链表）
import java.util.HashMap;
public class LRUCache<K, V> {
    class Node {
        K key;
        V value;
        Node prev, next;

        Node(K k, V v) {
            key = k;
            value = v;
        }
    }

    private final int capacity;
    private final HashMap<K, Node> map;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
    }

    public V get(K key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            if (map.size() == capacity) {
                map.remove(tail.key);
                removeTail();
            }
            addToHead(newNode);
            map.put(key, newNode);
        }
    }

    private void moveToHead(Node node) {
        if (node == head) return;
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(Node node) {
        if (node.prev != null) node.prev.next = node.next;
        else head = node.next;
        if (node.next != null) node.next.prev = node.prev;
        else tail = node.prev;
    }

    private void addToHead(Node node) {
        node.prev = null;
        node.next = head;
        if (head != null) head.prev = node;
        head = node;
        if (tail == null) tail = node;
    }

    private void removeTail() {
        if (tail != null) {
            if (tail.prev != null) tail.prev.next = null;
            else head = null;
            tail = tail.prev;
        }
    }
}
三、简单测试：
public class Main {
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(2);
        cache.put(1, "A");
        cache.put(2, "B");
        System.out.println(cache.get(1)); // A
        cache.put(3, "C"); // 淘汰 key=2
        System.out.println(cache.get(2)); // null
    }
}