Linear Lists

Question 1

What is an essential property of linear lists?

Answer 1

That the data structures contained within them are linear in function.

Question 2

What things can be restricted when it comes to linear lists?

Answer 2

Access to a node
Insertion of a node
Deletion of a node

Question 3

What are the three linear lists structures of most interest

Answer 3

Stack
Deque
Queue

Question 4

The stack operation takes what parameters?

Answer 4

The name of the stack you are inserting on.
The name of the node.
stack(A, p)

Question 5

The unstack operation takes what parameters?

Answer 5

None. The operation is a removal.

Question 6

What is often instantiated when unstacking? Why?

Answer 6

A variable is usually instantiated so that the data that is returned from the stack is not totally lost after the deletion.

Question 7

What is the queue mnemonic?

Answer 7

First
In
First
Out

Question 8

How is a queue restricted?

Answer 8

Deletions usually happen at the front.

Insertions happen at the rear.

Question 9

Explain how a shopping queue could be useful when understanding how queues work?

Answer 9

People enter from the back and are dealt with at the front.

Question 10

Name the operations associated with a queue.

Answer 10

Queue

Unqueue

Question 11

How do you add to a queue? What parameters?

Answer 11

Queue operation.
Name of queue.

Queue(A, the node)

Question 12

What part of a queue does the Queue operation affect?

Answer 12

The rear of the queue.

Remember first in first out.

Question 13

What does the unqueue operation do?

Answer 13

Removes the first node at the front of the queue.

Question 14

What is the unqueue operation similar to?

Answer 14

Unstack.

Removing an element and returning the element (often to a variable)

Question 15

What is a deque otherwise known by?

Answer 15

Double-ended queue.

Question 16

In a general deck, where do insertions and deletions occur?

Answer 16

Both left and right sides.

Question 17

What are the specific properties of an input-restricted deque?

Answer 17

Input restricted to one side.

Deletion at both sides.

Question 18

What is specific about an output restricted deque

Answer 18

Deletion restricted to one side.

Input can happen anywhere.

Question 19

What are the four operations with a deque?

Answer 19

Left insert
Right insert
Left delete
Right delete

Question 20

What are the parameters associated with insertion?

Answer 20

type_of_insertion([name of deque], [node])

Question 21

What are the parameters associated with deletion?

Answer 21

None. Usually something returned to a variable outside of the deque.