(5) Lists

Question 1

Definition List/ Linked List

Answer 1

A list or linked list is a dynamic data structure that allows to dynamically manage data.

Pro: arbitrary insertion of elements
Con: more complex management, overhead

Question 2

Definition Node

Answer 2

Consists of two parts:

• data
• reference to the next node

Every node references its successor node (but doesn’t know predecessor

Question 3

What are the steps to search for an element in a list?

Answer 3

1. current_node = head 2. If current_node == nil
   element not found
2. If current_node.data == e, you are done, element is found
3. If current_node.data ≠ e
   current_node = current_node.next
4. Go to step 2 (with the new current_node)

Question 4

What are the steps to delete a node in a list?

Answer 4

1. node_to_delete = current_node.next
2. current_node.next = node_to_delete.next
3. Delete node_to_delete
4. You are done

Question 5

Which ways exist to insert an element into a list?

Answer 5

• Insert element at head position

- Insert elements while maintaining an order

Question 6

What are the steps to insert a node at the head of a list?

Answer 6

1. current_node = head
2. new_node.next = current_node
3. head = new_node
4. You are done

Question 7

What does a node consist of?

Answer 7

A node has the two attributes “data” and “next”

Question 8

What is the time efficiency for searching, inserting and deleting in a list?

Answer 8

Searching: O(n)
Inserting: O(n) (except inserting at head O(1))
Deleting: O(n)