Term
| What are some of the advantages that linked lists have over arrays? |
|
Definition
| A linked list can easily grow or shrink in size. In fact, the programmer doesn’t need to know how many nodes will be in the list. They are simply created in memory as they are needed. Also, when a node is inserted into or deleted from a linked list, none of the other nodes have to be moved. |
|
|
Term
| What advantage does a lined list have over the STL vector? |
|
Definition
| The advantage that linked lists have over vectors, however, is the speed at which a node may be inserted into or deleted from the list. To insert a value into the middle of a vector requires all the elements below the insertion point to be moved one position toward the vector’s end, thus making room for the new value. Likewise, removing a value from a vector requires all the elements below the removal point to be moved one position toward the vector’s beginning. When a node is inserted into, or deleted from a linked list, none of the other nodes have to be moved. |
|
|
Term
|
Definition
| A pointer that simply points to the first node in the list. |
|
|
Term
| What is a self-referential data structure? |
|
Definition
| A data structure that has a pointer to a structure of the same type. |
|
|
Term
| How is the end of a linked list usually signified? |
|
Definition
| The last node in the list usually points to address 0, the null address. |
|
|
Term
| Name five basic linked list operations. |
|
Definition
| The basic linked list operations are appending a node, traversing the list, inserting a node, deleting a node, and destroying the list. |
|
|
Term
| What is the difference between appending a node and inserting a node? |
|
Definition
| Appending a node means that a new node is added to the end of the list. Inserting a node means that a new node is inserted somewhere in the middle of the list. |
|
|
Term
| What does "traversing the list" mean? |
|
Definition
| To travel through the list, node by node. |
|
|
Term
| What are the two steps required to delete a node from a linked list? |
|
Definition
- Remove the node from the list without breaking the links created by the next pointers.
- Deleting the node from memory. |
|
|
Term
| What is the advantage of using a template to implement a linked list? |
|
Definition
| The list can hold values of any data type. |
|
|
Term
| What is a singly linked list? What is a doubly linked list? What is a circularity linked list? |
|
Definition
| In a singly linked list each node is linked to a single other node. In a doubly linked list each node not only points to the next node, but also the previous one. In a circularly linked list the last node points to the first, |
|
|
Term
| What type of linked list is the STL list container? |
|
Definition
|
|
Term
| The_______ points to the first node in a linked list. |
|
Definition
|
|
Term
| A data structure that points to an object of the same type as itself is known as a(n) _________ data structure. |
|
Definition
| self-referential data structure |
|
|
Term
| After creating a linked list's head pointer, you should make sure it points to _________ before using it in any operations. |
|
Definition
|
|
Term
| After creating a linked list's head pointer, you should make sure it points to __________ before using it in any operations. |
|
Definition
|
|
Term
| ________ a node means adding it to the end of a list. |
|
Definition
|
|
Term
| ______ a node means adding it to a list, but not |
|
Definition
|
|
Term
| In a(n) __________ list, the last node has a pointer to the first node. |
|
Definition
|
|
Term
| In a(n) _________ list, each node has a pointer to the one before it and the one after it. |
|
Definition
|
|
