# DS&A

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.

### 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?

## New comment

Your comment will not appear until a moderator approves it.

Atom

hosted on werp.site