linked lists, stacks, queues

Node

Element with data + pointer to next

Head

First node in a linked list

Tail

Last node (points to null or head)

Normal Linked List

Last node points to null

Circular Linked List

Last node points to head

Insert in Ascending Order

Traverse until current > new, insert before

Insert in Descending Order

Traverse until current < new, insert before

Delete Node by Value

Find node with value, bypass it in links

Stack

LIFO structure (last in, first out)

Push

stack.push(element)

Pushes to the top of the stack (head)

Pop

stack.pop()

removes from the top of the stack, returns the element

throws emptystackexception

Peek

stack.peek()

returns the top of the stack wo removing

throws emptystackexception

infix expression

Operators between operands A+B

Postfix Expression

Operators after operands (A B +)

Convert Infix to Postfix

Use stack for operators, follow precedence and parentheses

Evaluate Postfix

Use stack, push numbers, pop and apply operators

Queue

FIFO structure (first in, first out)

Enqueue

Add item at rear

add(element) - type, what it does

Queues

adds to queue. if failure, throws exception

AddException

offer(element) - type, what it does

Queues

inserts, if failure, returns false

remove() - type, what it does

Queues

deletes head, if failure throws exception

add and remove throw a hissy fit

poll() - type, what it does

Queues

deletes head, if failure returns null

remove(element)

queues

deletes the first instance of element

limitation of linear queues

after multiple pops the space is wasted, cannot reuse

circular queue

rear points to head to reuse space

full circular queue condition

(rear+1) % size == front

what does head = head.next mean

deletes head node

what happens if you forget to update prev.next when deleting

node stays in the list—not actually removed

circular lists: how to check end of list

curr.next == head

what happens if delete last node in circular list, but don’t update the tail

tail points to deleted memory and everything explodes

insert at beginning of a singly list

newNode.next = head;

head = newNode;

stack underflow

pop on empty stack—error

infix to postfix—where do we pop operators from

stack

what to do when see ) in infix

pop until see (

ex stack:

)

2

+

1

(

pop from ) to ( to get (1+2)

what does front == rear mean in a circular queue

empty

What if you insert at head but forget newNode.next = head?

You lose the rest of the list — only the new node remains

What's the tail’s .next in a circular list?

Points to the head

How do you delete the head in a circular list with one node?

Set head = null

like any other list you stupid bumbling oaf