数组和链表

数组

  1. 数组内存分配在连续的内存区域上。
  2. 数组需要预申请大小，可能造成内存浪费。
  3. 随机读取效率高，因为数组内存是连续的，知道每一个数据的地址，可以直接找到指定索引数据。
  4. 增删效率低，需要移动受影响的数据的位置。
  5. 由于内存区域连续，有CPU缓存命中高的优势，访问效率高。

链表

  1. 链表可分配在内存任意地方，不要求连续。
  2. 无需预指定大小，可自由调整数据量。
  3. 不支持随机读取，查询数据较慢，需要从头开始遍历查找。
  4. 增删速度快，只需要修改指针指向即可。
  5. 由于内存分散，往往前后节点数据不能同时处于缓存中，访问效率低。

时间复杂度

/ 数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(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
public class List<T>
{
    private T[] array;
    private int count;

    public int Count => count;

    public int Capacity => array.Length;

    private static T[] emptyArray = new T[0];

    public List()
    {
        array = emptyArray;
        count = 0;
    }

    public List(int capacity)
    {
        array = new T[capacity];
        count = 0;
    }

    public void Set(int index, T value)
    {
        if (count == Capacity)
            Resize((Capacity == 0) ? 4 : Capacity * 2);//容量从4起步，每次扩容翻倍

        array[index] = value;
        count++;
    }

    public T Get(int index)
    {
        if (index > count - 1)
        {
            throw new Exception("List out of range");
        }

        return array[index];
    }

    public void RemoveAt(int index)
    {
        for (int i = index; i < count ; i++)
        {
            array[i] = array[i + 1];
        }

        count--;

        //若实际数据小于当前容量的1/4，容量缩小至原本的1/2
        if (count > 0 && count <= Capacity / 4)
        {
            Resize(Capacity / 2);
        }
    }

    //调整内部数组大小，新开辟数组，并把旧数组内容拷贝至新数组
    private void Resize(int count)
    {
        T[] _array = new T[count];
        Array.Copy(array, 0, _array, 0, this.count);
        array = _array;
    }
}

单链表

实现

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
public class ListNode<T> where T : IComparable<T>
{
    public ListNode<T> next;
    public T value;

    public ListNode(T value)
    {
        this.value = value;
    }

    public ListNode(ListNode<T> next, T value)
    {
        this.next = next;
        this.value = value;
    }
}

class LinkedList<T> where T : IComparable<T>
{
    private ListNode<T> head;
    private int count;
    public int Count => count;

    public ListNode<T> First => head.next;


    public LinkedList()
    {
        head = new ListNode<T>(default(T));
    }

    public void AddFirst(T value)
    {
        AddFirst(new ListNode<T>(value));
    }

    public void AddFirst(ListNode<T> node)
    {
        if (node == null)
            return;

        AddNode(head, node);
    }

    public void AddLast(T value)
    {
        AddLast(new ListNode<T>(value));
    }

    public void AddLast(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> last = head;
        while (last.next != null)
        {
            last = last.next;
        }

        AddNode(last, node);
    }

    public void AddBefore(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddBefore(node, new ListNode<T>(value));
    }

    public void AddBefore(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            pre = pre.next;
            addNode = addNode.next;
        }

        if (addNode == null || addNode.value.CompareTo(node.value) != 0)
            return;

        AddNode(pre, value);
    }

    public void AddAfter(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddAfter(node, new ListNode<T>(value));
    }

    public void AddAfter(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            addNode = addNode.next;
        }

        if (addNode == null || addNode.value.CompareTo(node.value) != 0)
            return;

        AddNode(node, value);
    }

    public void DeleteNode(T value)
    {
        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode.value.CompareTo(value) != 0)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    public void DeleteNode(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode != node)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    private void DeleteNode(ListNode<T> pre, ListNode<T> deleteNode)
    {
        if (pre == null || deleteNode == null)
            return;

        ListNode<T> next = deleteNode.next;
        pre.next = next;
        count--;
    }

    public ListNode<T> Find(T value)
    {
        ListNode<T> node = First;
        while (node != null && node.value.CompareTo(value) != 0)
        {
            node = node.next;
        }

        return node;
    }

    private void AddNode(ListNode<T> pre, ListNode<T> node)
    {
        if (pre == null || node == null)
            return;

        ListNode<T> next = pre.next;
        pre.next = node;
        node.next = next;
        count++;
    }

    public void Clear()
    {
        head.next = null;
        count = 0;
    }
}

双链表

实现

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
public class ListNode<T> where T : IComparable<T>
{
    public ListNode<T> pre;
    public ListNode<T> next;
    public T value;

    public ListNode(T value)
    {
        this.value = value;
    }

    public ListNode(ListNode<T> pre, ListNode<T> next, T value)
    {
        this.pre = pre;
        this.next = next;
        this.value = value;
    }
}

class LinkedList<T> where T : IComparable<T>
{
    private ListNode<T> head;
    private ListNode<T> tail;
    private int count;
    public int Count => count;

    public ListNode<T> First
    {
        get
        {
            if (count > 0)
                return head.next;
            else
                return null;
        }
    }

    public ListNode<T> Last
    {
        get
        {
            if (count > 0)
                return tail.pre;
            else
                return null;
        }
    }


    public LinkedList()
    {
        head = new ListNode<T>(default(T));
        tail = new ListNode<T>(default(T));
        head.next = tail;
        tail.pre = head;
    }

    public void AddFirst(T value)
    {
        AddFirst(new ListNode<T>(value));
    }

    public void AddFirst(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> next = First;
        head.next = node;
        node.next = next;
        if (next != null) next.pre = node;
        count++;
    }

    public void AddLast(T value)
    {
        AddLast(new ListNode<T>(value));
    }

    public void AddLast(ListNode<T> node)
    {
        if (node == null)
            return;

        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;

        count++;
    }

    public void AddBefore(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddBefore(node, new ListNode<T>(value));
    }

    public void AddBefore(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            pre = pre.next;
            addNode = addNode.next;
        }

        if (addNode == null)
            return;

        pre.next = value;
        if (pre != head) value.pre = pre;
        value.next = node;
        node.pre = value;

        count++;
    }

    public void AddAfter(ListNode<T> node, T value)
    {
        if (node == null)
            return;

        AddAfter(node, new ListNode<T>(value));
    }

    public void AddAfter(ListNode<T> node, ListNode<T> value)
    {
        if (node == null || value == null)
            return;

        ListNode<T> addNode = First;
        while (addNode != null && addNode != node)
        {
            addNode = addNode.next;
        }

        if (addNode == null)
            return;

        ListNode<T> next = node.next;
        node.next = value;
        value.pre = node;
        value.next = next;
        if (next == null) tail.pre = value;

        count++;
    }

    public void DeleteNode(T value)
    {
        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode.value.CompareTo(value) != 0)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    public void DeleteNode(ListNode<T> node)
    {
        if (node == null)
            return;

        ListNode<T> pre = head;
        ListNode<T> deleteNode = First;
        while (deleteNode != null && deleteNode != node)
        {
            pre = pre.next;
            deleteNode = deleteNode.next;
        }

        if (deleteNode == null)
            return;

        DeleteNode(pre, deleteNode);
    }

    private void DeleteNode(ListNode<T> pre, ListNode<T> deleteNode)
    {
        if (pre == null || deleteNode == null)
            return;

        ListNode<T> next = deleteNode.next;
        pre.next = next;
        if (pre != head) next.pre = pre;

        count--;
    }

    public ListNode<T> Find(T value)
    {
        ListNode<T> node = First;
        while (node != null && node.value.CompareTo(value) != 0)
        {
            node = node.next;
        }

        return node;
    }

    public void Clear()
    {
        head.next = tail;
        tail.pre = head;
        count = 0;
    }
}

栈

先进后出

应用

  1. 基于栈实现的UI框架
  2. 编辑器中撤回和重做的操作
  3. 括号合法检查
  4. 基于栈实现简单的表达式计算

数组实现

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
public class Stack<T>
{
    private T[] array;
    private int count;

    public int Count => count;

    private static T[] emptyArray = new T[0];

    public Stack()
    {
        array = emptyArray;
        count = 0;
    }

    public Stack(int capacity)
    {
        array = new T[capacity];
        count = 0;
    }

    public bool IsEmpty()
    {
        return count <= 0;
    }

    public T Peek()
    {
        if (count == 0)
        {
            throw new Exception("Stack count is 0.");
        }
        else
        {
            return array[count - 1];
        }
    }

    public void Push(T t)
    {
        if (count == array.Length)
        {
            Resize((array.Length == 0) ? 4 : (2 * array.Length));
        }

        array[count++] = t;
    }

    public T Pop()
    {
        if (count == 0)
        {
            throw new Exception("Stack count is 0.");
        }

        T t = array[--count];
        array[count] = default(T);

        if (count > 0 && count == array.Length / 4)
        {
            Resize(array.Length / 2);
        }

        return t;
    }

    private void Resize(int count)
    {
        T[] _array = new T[count];
        Array.Copy(array, 0, _array, 0, this.count);
        array = _array;
    }
}

链表实现

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
public class Stack<T>
{
    private class ListNode<Y>
    {
        public ListNode<Y> next;
        public Y value;

        public ListNode(Y value)
        {
            this.value = value;
        }

        public ListNode(ListNode<Y> node, Y value)
        {
            this.next = node;
            this.value = value;
        }
    }

    private ListNode<T> first;
    private int count;

    public int Count => count;

    public bool IsEmpty()
    {
        return first == null;
    }

    public T Peek()
    {
        if (first == null)
        {
            throw new Exception("Stack count is 0.");
        }
        else
        {
            return first.value;
        }
    }

    public void Push(T value)
    {
        ListNode<T> oldFirst = first;
        first = new ListNode<T>(value);
        first.next = oldFirst;

        count++;
    }

    public T Pop()
    {
        if (count == 0)
        {
            throw new Exception("Stack count is 0.");
        }

        T value = first.value;
        first = first.next;

        count--;

        return value;
    }
}

队列

先进先出

应用

  1. 消息队列，降低峰值
  2. 动画队列，按顺序逐个播放动画
  3. BFS
  4. 排队问题等

数组实现

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
public class Queue<T>
{
    private int front;
    private int rear;
    private T[] array;

    private static T[] emptyArray = new T[4];

    public int Capacity => array.Length;
    public int Count => (rear + Capacity - front) % Capacity;
    public bool IsEmpty => front == rear;
    private bool IsFull => (rear + 1) % Capacity == front;

    public Queue()
    {
        array = emptyArray;
        front = 0;
        rear = 0;
    }

    public Queue(int capacity)
    {
        array = new T[capacity];
        front = 0;
        rear = 0;
    }

    public void Enqueue(T value)
    {
        if (IsFull)
        {
            Resize(Capacity * 2);
        }

        array[rear] = value;
        rear = (rear + 1) % Capacity;
    }

    public T Dequeue()
    {
        if (IsEmpty)
        {
            throw new Exception(("Queue count is 0."));
        }

        T value = array[front];
        array[front] = default(T);
        front = (front + 1) % Capacity;

        if (Count > 0 && Count == Capacity / 4)
        {
            Resize(Capacity / 2);
        }

        return value;
    }

    public T Peek()
    {
        if (IsEmpty)
        {
            throw new Exception("Queue count is 0.");
        }

        return array[front];
    }

    private void Resize(int size)
    {
        T[] newArray = new T[size];
        Console.WriteLine(("resize:" + Capacity + " to:" + size));

        int index = front;
        int newIndex = 0;
        while (newIndex < Count)
        {
            newArray[newIndex++] = array[index];
            index++;
        }
        front = 0;
        rear = newIndex;
        array = newArray;
    }
}

链表实现

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
public class Queue<T>
{
    private class Node<Y>
    {
        public Node<Y> next;
        public Y value;

        public Node(Y value)
        {
            this.value = value;
        }

        public Node(Node<Y> node, Y value)
        {
            this.next = node;
            this.value = value;
        }
    }

    private Node<T> first;
    private Node<T> last;
    private int count;

    public int Count => count;
    public bool IsEmpty => first == null;

    public void Enqueue(T value)
    {

        Node<T> oldLast = last;
        last = new Node<T>(value);
        if (IsEmpty)
        {
            first = last;
        }
        else
        {
            oldLast.next = last;
        }

        count++;
    }

    public T Dequeue()
    {
        if (IsEmpty)
        {
            throw new Exception("Queue count is 0.");
        }

        T value = first.value;
        first = first.next;

        if (IsEmpty)
            last = null;

        count--;
        return value;
    }

    public T Peek()
    {
        if (IsEmpty)
        {
            throw new Exception("Queue count is 0.");
        }

        return first.value;
    }
}

双端队列

双端队列同时具有栈的先进后出特性，也具有队列的先进先出特性。

应用

  1. KTV式可插歌的点歌系统
  2. LRU