Exercises: List Data StructuresFeb 192018
Before attempting these exercises, you should read the posts about array-lists and linked lists.
- Which is more efficient — or are they about the same?
Explain your answers.
(Hint: use the interactive models of array-lists and linked lists, and see what steps are taken to perform these operations.)
- ‘Get’ from an array-list, or ‘get’ from a linked list?
- ‘Set’ or ‘insert’ in an array-list?
- ‘Insert’ or ‘remove’ near the start of an array-list?
- ‘Insert’ near the start of an array-list, or near the end?
- ‘Insert’ near the start of a linked list, or near the end?
- Which list data structure usually uses more memory — an array-list, or a linked list?
Explain your answer.
(Hint: consider box-and-pointer diagrams.)
- Suppose that an array-list initially uses an array of length 4, and this length is doubled when necessary.
"eggs" once to the array-list, and then append
"spam" 1,000 times.
- How many times will
"eggs" be copied from one array to another?(1)
- (Challenge:) How many times will
"spam" be copied?