DS&A

Exercises: List Data Structures

Before attempting these exercises, you should read the posts about array-lists and linked lists.

Exercises

1. 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.)
   1. ‘Get’ from an array-list, or ‘get’ from a linked list?
   2. ‘Set’ or ‘insert’ in an array-list?
   3. ‘Insert’ or ‘remove’ near the start of an array-list?
   4. ‘Insert’ near the start of an array-list, or near the end?
   5. ‘Insert’ near the start of a linked list, or near the end?
2. Which list data structure usually uses more memory — an array-list, or a linked list? Explain your answer. (Hint: consider box-and-pointer diagrams.)
3. Suppose that an array-list initially uses an array of length 4, and this length is doubled when necessary. We append "eggs" once to the array-list, and then append "spam" 1,000 times.
   1. How many times will "eggs" be copied from one array to another?(1)
   2. (Challenge:) How many times will "spam" be copied?

Footnotes

1. Technically, the list contains a reference to the string "eggs", so how many times is the reference copied?

• Tags: 
• exercises, data structures, array-lists, linked lists, lists