elementary data structures Flashcards
advantages of arrays
memory efficient
can access any key quickly
disadvantages of arrays
cannot grow or shrink
removal and deletion is only efficienet for the element at the very end
advantages of linked lists
can grow and shrink as necessary
can remove and insert keys efficiently anywhere in the list
disadvantages of linked lists
larger memory overhead
cannot access all keys quickly
running time for searching in linked list
O(n)
running time for searching in array
O(1)
running time for insertion and deletion in (doubly) linked list
O(1)
running time for insertion and deletion in array and singly linked list
O(n)?
stack
LIFO
queue
FIFO
infix to postfix conversion algorithm + worst case
the shunting-yard algorithm
worst case: O(n)
worst case for computing postfix expression
O(n)
