Linked Lists

Question 1

What are some problems that arrays/arraylists have that linked lists solve?

Answer 1

• adding or deleting elements from the middle or the front requires other elements to be shifted, which consumes resources
• adding another element when full requires a complete re-build of the array into a new one

Question 2

What is a Node?

Answer 2

An object that contains some data (or a reference to it) and a reference to the next Node in the list (or null if there isn’t one)

Question 3

Why do Nodes make an exception to the “instance variables must be private” rule?

Answer 3

Because Nodes are useless without lists, so you can control all use of nodes by simply keeping them private to the linked list. This means that you must never return a node from a method in a linked list

Question 4

What are some cases you must consider for an add function of a linked list?

Answer 4

• if the list is empty
• if the requested position does not exist
• if the position is 0

Question 5

Compare adding with an array to adding with a linked list

Answer 5

array:
- must “shuffle” all elements after (loop needed)
- can access the desired position directly
- might get full and require expansion of the array
- easiest to add to the end

list:
- no need to shuffle; very quick insertion
- must follow the chain through all previous elements to find
the right position (loop needed)
- can’t get full (unless you completely run out of memory)
- easiest to add to the beginning

Question 6

What are some cases to consider when removing an item from a linked list?

Answer 6

• if the list is empty
• if the first node is the one requested to remove
• if the item doesn’t exist

Question 7

What searching algorithm should be used on a linked list?

Answer 7

Binary search is impossible on a linked list, so for now, use linear search