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;
For a deleteNode() function, after the ____ loop, if the else statement executes what does that mean and what code should execute?
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;
For a deleteNode() function, if an item is deleted, what happens next?
This means that an item needs to be freed:
free(node->dataPtr);
free(node);
A doubly linked list typically has pointers to both the ____ and ____ of the list as well as both ____ and ____ varibales in the node structure.
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.
A tradeoff to making a doubly-linked list is that it requires…
Additional bytes to store the PREVIOUS variable
Circularly linked lists avoid the use of ____ references in the list
Avoid the use of NULL references in the list
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
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
