C++: Linked Lists, Stacks, and Queues

Define Linked List

A Data structure used to implement a list of items arranged in some kind of order

Components of linked list

Nodes

first node of linked list

head pointer

last node of linked list

tail pointer

What is a NULL pointer?What library is it used in?

A NULL pointer is a C++ pointer value that can be used for a pointer that doesnt point anywhere. it is used in the <cstdlib> library

what is the symbol -> ?
provide an example.

member selection operator. allows you to select a member of the pointer in a class
ex: head_ptr->data() activates the data function of the node pointed to by head_ptr.

Why is a pointer to a node with a const keyword necessary for certain functions.

It allows a user to call a function with a pointer and not change the value of the pointer.

write code to implement the following function:
void list_head_insert(node*& head_ptr, const node::value_type& entry);

void list_head_insert(node*& head_ptr, const node::value_type& entry)
{node *insert_ptr;

insert_ptr = new node(entry, head_ptr);
head_ptr = insert_ptr;
}

write code to implement the following function:
void list_insert(node* previous_ptr, const node::value_type& entry)

void list_insert(node* previous_ptr, const node::value_type& entry)
{
insert_ptr = new node;
insert_ptr->set_data(entry)
insert_ptr->set_link( previous_ptr->link());
previous_ptr->set_link(insert_ptr);
}

Which of the following are better for random access?
-dynamic arrays
-Linked lists
-doubly linked lists

dynamic arrays

Which is better at insertion/deletion at a cursor?
-dynamic arrays?
-Linked lists?
-double linked lists?

linked lists

4. Answer true or false for this statement: For all possible inputs, a linear algorithm to solve a problem must perform faster than a logarithmic algorithm to solve the same problem.

FALSE

6. What term is used to describe an O(Logn) algorithm.
A. Constant
B. Linear
C. Logarithmic
D. Quadratic

C. logarithmic

9. Suppose cursor points to a node in a linked list (using the node definition with member functions called data and link). What statement changes cursor so that it points to the next node?
A. cursor++;
B. cursor = link( );
C. cursor += link( );
D. cursor = cursor->link( );

D. cursor = cursor->link( );

What is a Stack?

a data structure of ordered entries such that entries can be inserted and removed only one end, called the top. (first in, last out).

what does the function pop() do in a stack?

removes the top item from the class

what is stack underflow, and what is stack overflow?

underflow is the condition from trying to access an item from an empty stack.
overflow is the condition resulting from trying to push an item onto a full stack.

List two ways of implementing stacks.

-static implementation: using a fixed size arrray.
-dynamic implementation using a linked list.