Node cur = dummyHead.next; for(int i = 0 ; i < index ; i ++) cur = cur.next; cur.e = e; }
// 查找链表中是否有元素e publicbooleancontains(E e){ Node cur = dummyHead.next; while(cur != null){ if(cur.e.equals(e)) returntrue; cur = cur.next; } returnfalse; }
// 从链表中删除index(0-based)位置的元素,返回删除的元素 // 在链表中不是一个常用的操作,练习用的 public E remove(int index){ if(index < 0 || index >= size) thrownew IllegalArgumentException("Remove failed. Index is illegal.");
Node prev = dummyHead; for(int i = 0 ; i < index; i++) prev = prev.next;
@Override public E pop(){ return list.removeFirst(); }
@Override public E peek(){ return list.getFirst(); }
@Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Stack: top "); res.append(list); return res.toString(); }
publicstaticvoidmain(String[] args){
LinkedListStack<Integer> stack = new LinkedListStack<>();
for(int i = 0 ; i < 5 ; i++){ stack.push(i); System.out.println(stack); }
stack.pop(); System.out.println(stack); } }
我对比了一下动态数组栈和链表栈的时间输出结果截图
链表的操作中包含更多的new操作,在数值大的时候,会比动态数组的栈速度慢个1.x倍
测试时间代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14
// 测试使用stack运行opCount个push和pop操作所需要的时间,单位:秒 privatestaticdoubletestStack(Stack<Integer> stack, int opCount){
long startTime = System.nanoTime();
Random random = new Random(); for(int i = 0 ; i < opCount; i ++) stack.push(random.nextInt(Integer.MAX_VALUE)); for(int i = 0 ; i < opCount; i ++) stack.pop();
评论