Week 9: Linked Lists Flashcards
Nodes for a linked list will be _____ dynamically created or deleted in the ______
Nodes for a linked list will be OBJECTS dynamically created or deleted in the HEAP
In SINGLY linked lists, nodes will contain:
Two member variables:
- Item value
- NODE* next
In node objects, data objects can be either
Simple or complex data structures
For singly linked lists. If you have a LIST structure, you should keep track of the _____ and ____
Head node and count
A createList() function should take in what parameter?
void
A createList() function has what return type?
LIST*
list pointer
A createList() function does what after dynamically creating the list?
Have an if statement checking whether or not the list was properly created
A createList() function should do what after creating the list and ensuring it was created?
Set head to NULL and count to 0
An insertList() function to insert a node to a list has what parameters
LIST* pointer to a list and a void* data item pointer
An insertList() function to insert a node to a list, what are the steps that must be taken?
- Create a NODE* pointer
- Assign the new NODE* pointer’s data pointer to the data item parameter
- Assign the new NODE* pointer’s next pointer to the list’s head
- Assign the LIST* head pointer to the new node
- Increment the list count
To search for an item in a linked list, you must begin the search at the ____ of the list
Head of the list
For a searchList() function, what are the parameters?
LIST* pointer and the value to be searched for
For a searchList() function, what is the variable created in the function?
A node pointer NODE* nP to traverse the list
For a searchList() function, what is used to traverse the list? What does it look like?
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)
For a searchList() function, what is within the for loop?
if (nP->dataPtr == value) return nP;
For a searchList() function, what should return at the end of the function and when would this be the case?
NULL should return and it will only be reached if the item is not found within the list
To remove a node from a list you must traverse the list while keeping track of the ____
Previous node
To fully free a node from a list, you must…
free the data pointer AND the node itself
You must always remember to do what after removing a node from a list?
Decrement the counter
and free the memory
For a deleteNode() function, the type of iteration used is ___. What does it look like and why?
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
For a deleteNode() function, after the ____ loop, the three possibilities are…
What do they mean?
- current == NULL
Indicates the list is empty OR the item was not found
- previous == NULL
Indicates the item was found at the beginning of the list
- Neither of the above
The item was found somewhere in the middle of the list
For a deleteNode() function, after the ____ loop, the three ____ statements are…
FOR LOOP
if (current == NULL) {…}
if (previous == NULL) {…}
else {..}
For a deleteNode() function, after the ____ loop, if curr == NULL what does that mean and what code should execute?
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;
For a deleteNode() function, after the ____ loop, if previous == NULL what does that mean and what code should execute?
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;
