Week 9: Linked Lists

Question 1

Nodes for a linked list will be _____ dynamically created or deleted in the ______

Answer 1

Nodes for a linked list will be OBJECTS dynamically created or deleted in the HEAP

Question 2

In SINGLY linked lists, nodes will contain:

Answer 2

Two member variables:

• Item value
• NODE* next

Question 3

In node objects, data objects can be either

Answer 3

Simple or complex data structures

Question 4

For singly linked lists. If you have a LIST structure, you should keep track of the _____ and ____

Answer 4

Head node and count

Question 5

A createList() function should take in what parameter?

Answer 5

void

Question 6

A createList() function has what return type?

Answer 6

LIST*

list pointer

Question 7

A createList() function does what after dynamically creating the list?

Answer 7

Have an if statement checking whether or not the list was properly created

Question 8

A createList() function should do what after creating the list and ensuring it was created?

Answer 8

Set head to NULL and count to 0

Question 9

An insertList() function to insert a node to a list has what parameters

Answer 9

LIST* pointer to a list and a void* data item pointer

Question 10

An insertList() function to insert a node to a list, what are the steps that must be taken?

Answer 10

1. Create a NODE* pointer
2. Assign the new NODE* pointer’s data pointer to the data item parameter
3. Assign the new NODE* pointer’s next pointer to the list’s head
4. Assign the LIST* head pointer to the new node
5. Increment the list count

Question 11

To search for an item in a linked list, you must begin the search at the ____ of the list

Answer 11

Head of the list

Question 12

For a searchList() function, what are the parameters?

Answer 12

LIST* pointer and the value to be searched for

Question 13

For a searchList() function, what is the variable created in the function?

Answer 13

A node pointer NODE* nP to traverse the list

Question 14

For a searchList() function, what is used to traverse the list? What does it look like?

Answer 14

A for loop

for (NODE* nP = LIST->head; nP != NULL; nP = nP->next)

or

NODE* nP;

for (nP = LIST->head; nP != NULL; nP = nP->next)

Question 15

For a searchList() function, what is within the for loop?

Answer 15

if (nP->dataPtr == value) return nP;

Question 16

For a searchList() function, what should return at the end of the function and when would this be the case?

Answer 16

NULL should return and it will only be reached if the item is not found within the list

Question 17

To remove a node from a list you must traverse the list while keeping track of the ____

Answer 17

Previous node

Question 18

To fully free a node from a list, you must…

Answer 18

free the data pointer AND the node itself

Question 19

You must always remember to do what after removing a node from a list?

Answer 19

Decrement the counter

and free the memory

Question 20

For a deleteNode() function, the type of iteration used is ___. What does it look like and why?

Answer 20

For loop iteration;

NODE* nP, prev;

for(nP = list->head, prev = NULL; nP != NULL && nP->dataPtr != value; prev = nP, nP = nP->next)

THERE IS NOTHING CONTAINED WITHIN THE FOR LOOP AS IT WILL RETURN REGARDLESS AND THE RETURN VALUE INDICATES WHETHER OR NOT THE VALUE WAS FOUND

Question 21

For a deleteNode() function, after the ____ loop, the three possibilities are…

What do they mean?

Answer 21

1. current == NULL

Indicates the list is empty OR the item was not found

2. previous == NULL

Indicates the item was found at the beginning of the list

3. Neither of the above

The item was found somewhere in the middle of the list

Question 22

For a deleteNode() function, after the ____ loop, the three ____ statements are…

Answer 22

FOR LOOP

if (current == NULL) {…}

if (previous == NULL) {…}

else {..}

Question 23

For a deleteNode() function, after the ____ loop, if curr == NULL what does that mean and what code should execute?

Answer 23

It means that either the list was empty or that the item was found.

If this is the case, the only statement should be:

return list;

Question 24

For a deleteNode() function, after the ____ loop, if previous == NULL what does that mean and what code should execute?

Answer 24

This means that the value was found in the first node of the list.

If this is the case, the following lines ofcode should execute:

list->head = current->next;

Question 25

For a deleteNode() function, after the ____ loop, if the else statement executes what does that mean and what code should execute?

Answer 25

This means the value was found somewhere in the middle of the list.

In this case, the following lines of code should execute:

previous->next = current->next;

Question 26

For a deleteNode() function, if an item is deleted, what happens next?

Answer 26

This means that an item needs to be freed:

free(node->dataPtr);

free(node);

Question 27

A doubly linked list typically has pointers to both the ____ and ____ of the list as well as both ____ and ____ varibales in the node structure.

Answer 27

A doubly linked list typically has pointers to both the HEAD and TAIL of the list as well as both NEXT and PREVIOUS varibales in the node structure.

Question 28

A tradeoff to making a doubly-linked list is that it requires…

Answer 28

Additional bytes to store the PREVIOUS variable

Question 29

Circularly linked lists avoid the use of ____ references in the list

Answer 29

Avoid the use of NULL references in the list

Question 30

In a doubly-linked circular node, the predecessor of the head node is the ___ node and the successor of the tail node is the ____ node

Answer 30

In a doubly-linked circular node, the predecessor of the head node is the tail node and the successor of the tail node is the head node