Shared Flashcard Set

Details

COSC II Chapter 17
Computer Science for COSC II
20
Computer Science
Undergraduate 2
05/07/2017

Additional Computer Science Flashcards

 


 

Cards

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
What is a list head?
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
A doubly linked list.
Term
The_______ points to the first node in a linked list.
Definition
head pointer
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
NULL
Term
After creating a linked list's head pointer, you should make sure it points to __________ before using it in any operations.
Definition
Appending
Term
________ a node means adding it to the end of a list.
Definition
Inserting
Term
______ a node means adding it to a list, but not
Definition
Traversing
Term
In a(n) __________ list, the last node has a pointer to the first node.
Definition
Circular
Term
In a(n) _________ list, each node has a pointer to the one before it and the one after it.
Definition
Doubly-Linked
Supporting users have an ad free experience!