# Shared Flashcard Set

## Details

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

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
 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