Data Structures and Algorithms

Exercises: List Data Structures

Feb 192018

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


  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?


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

There are no published comments.

New comment

Your comment will not appear until a moderator approves it.


hosted on werp.site