Unsorted List: Implementation
• Different ways of storing items in memory affect the performance of list operators
• Array Based: Elements are store sequentially in a contiguous chunk of memory
• Link List_based: Elements are stored in separate nodes, connected by pointers
• Using an array-based implementation for now.
• Link List benefit is that there is no limit on size, you can just keep adding nodes.
• GetItem requires a linear search through the list
• Use bool &found reference parameter to indicate success to the user
• Return a copy of the found item.
• PutItem: Insert item at the end of the list, increment list
• DeleteItem: Linear search to find item, but how to remove it?
• If the item is at the end of the list, just reduce the length of the list by one
• But what about if it’s at the beginning?
• The field currentPos indicates the current position of iteration in the LIST
// Pre: ResetList was called to initialized iteration
WE WILL BE USING POINTERS A LOT!!!
C++ Review Pointers
• Pointer is a type of data type that store memory addresses
• C++ has a pointer for each data type
• There are even pointers for pointers
Int **p; //pointer to pointer
• Address Operator&
Int a = 100;
Cout << a; //100
Cout <<&a; //1024(the hex decimal of the address)