Stack和LinkedList的区别

发表于 | 分类于 |
字数统计: 404 字 | 阅读时长 ≈ 2 分钟

前言

栈有两种实现方式：Stack 和 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
import java.util.LinkedList;
import java.util.Stack;

public class StackTest01 {
  public static void main(String[] args) {
    // add测试
    // 结论：add测试一样
    LinkedList<Integer> linkedList = new LinkedList<>();
    linkedList.add(1);
    linkedList.add(2);
    linkedList.add(3);
    System.out.println("linkedList add:" + linkedList); // linkedList add:[1, 2, 3]

    Stack<Integer> stack = new Stack<>();
    stack.add(1);
    stack.add(2);
    stack.add(3);
    System.out.println("stack add:" + stack); // stack add:[1, 2, 3]

    // push测试
    // 结论：测试不一样，linkedlist的push是addFirst；stack是在数组尾部addElement
    linkedList.push(4);
    linkedList.push(5);
    linkedList.push(6);
    System.out.println("linkedList push:" + linkedList); // linkedList push:[6, 5, 4, 1, 2, 3]

    stack.push(4);
    stack.push(5);
    stack.push(6);
    System.out.println("stack push:" + stack); // stack push:[1, 2, 3, 4, 5, 6]
  }
}

结论：

  • LinkedList 和 Stack 的 add ，结果都是一样的
  • LinkedList 和 Stack 的 push ，有区别

源码粗读

add

LinkedList 底层是双向链表，Stack 底层是数组，它们的 add 方法都是在末尾添加元素，前者尾插法，后者数组扩容

LinkedList

1
2
3
4
public boolean add(E e) {
  linkLast(e); // 尾插法，在链表末尾加元素
  return true;
}

Stack

1
2
3
4
5
6
public synchronized boolean add(E e) {
  modCount++;
  ensureCapacityHelper(elementCount + 1); // 数组扩容
  elementData[elementCount++] = e; // 把e放在数组最后一位
  return true;
}

push

看源码得知，LinkedList 的 push 用的头插法，Stack 的 push 和 add 一样，都是数组扩容，从尾部添加

LinkedList

1
2
3
public void push(E e) {
  addFirst(e);
}

Stack

1
2
3
4
5
6
7
8
9
public E push(E item) {
  addElement(item);
  return item;
}
public synchronized void addElement(E obj) {
  modCount++;
  ensureCapacityHelper(elementCount + 1);
  elementData[elementCount++] = obj;
}

参考文章

linkedlist和stack异同

Java- Stack与LinkedList实现。