Traverse the nodes, going to the next node i times
Search() find value in list: O(N)
Traverse whole list looking for value
Best case if found in first position: O(1), worst case not found: O(N)
insert() at i: O(i)
Empty list: head and tail = new node
Insert at 0: new node → head node, head = new node
Insert at tail: tail node → new node, tail = new node
Insert at i: get(i-1), new node → node i, node i-1 → new node
remove() at i: O(i)
Remove at 0: head = head.next, del head
Remove at i: get(i-1), node i-1 → node i+1, del node i
Remove at tail: get(n-2), node n-2 → null, del tail, tail = node n-2
Stack
Is a SLL where we are only allowed to get(0), insert at 0 and remove at 0
Postfix expression is a mathematical expression in: operand1 operand2 operator format which is different from what human is most comfortable at, the Infix expression: operand1 operator operand2: 2 3 + 4 * is postfix of (2+3)*4 . Solve by pushing operands onto the stack. When operator is encountered, pop 2 operands, perform operation, then push result back onto stack