
| List | Stack | |
|---|---|---|
| create | O(1) | O(1) | 
| delete | O(1) | O(1) | 
| add | O(n) | O(1) | 
| remove | O(n) | O(1) | 
| traversal | O(1) | na | 
| navigation | O(1) | na | 
| dynamic | No | No | 
| List | Stack | Stack | |
|---|---|---|---|
| (Array) | (List) | ||
| create | O(1) | O(1) | O(1) | 
| delete | O(1) | O(1) | O(1) | 
| add | O(n) | O(1) | O(1) | 
| remove | O(n) | O(1) | O(1) | 
| traversal | O(1) | na | na | 
| navigation | O(1) | na | na | 
| dynamic | No | No | Yes | 
| List | Stack | Stack | Stack | |
|---|---|---|---|---|
| (Array) | (List) | (DArray) | ||
| create | O(1) | O(1) | O(1) | O(1) | 
| delete | O(1) | O(1) | O(1) | O(1) | 
| add | O(n) | O(1) | O(1) | O(1)* | 
| remove | O(n) | O(1) | O(1) | O(1)* | 
| traversal | O(1) | na | na | na | 
| navigation | O(1) | na | na | na | 
| dynamic | No | No | Yes | Yes | 
* Amortized.
| int f() int i, j double x // whatever 
 | 
 
 | 
| 
 
 | 
 
 | 
a()
  a() calls b()
    b() calls c()
      c() returns
    b() returns
  a() returns