data_structures - matthew9510/Studies GitHub Wiki

Arrays

• contiguous area of memory
• consisting of equal-size elements indexed by contiguous integers.
• Constant-time access to any element.
• Constant time to add/remove at the end.
• Linear time to add/remove at an arbitrary location.

ArrayList

• Simplest class that implements the List interface
• Arrays have a fixed size, will require creating a new array inorder to support adding elements if
• Constant time access to elements
• Removal is linear
• Insertion is quadratic

LIST API

PushFront(Key) add to front

Key TopFront() return front item

PopFront() remove front item

PushBack(Key) add to back

Key TopBack() return back item

PopBack() remove back item

Boolean Find(Key) is key in list?

Erase(Key) remove key from list

Boolean Empty() empty list?

AddBefore(Node, Key) adds key before node

AddAfter(Node, Key) adds key after node