Basic DS

Question 1

What are the key 3 differences between an array and a list?

Answer 1

An array is of static size, while a list has a dynamic size. Also, all indices of an array are accessible with O(1) . Lastly, you can’t have any implicit null space between elements in a list

Question 2

What is a link list?

Answer 2

A list that consists of nodes with a data field and a pointer to the next node

Question 3

What is a singly-linked list?

Answer 3

A list where each node points to the next in a single direction

Question 4

What special nodes are included in a linked list field to allow traversal?

Answer 4

A head node @ the beginning or a tail node @ the end

Question 5

How do doubly-linked nodes and singly-linked nodes differ?

Answer 5

doubly-linked nodes have a previous feild

Question 6

What special cases arise for the list add/contains method?

Answer 6

null parameter, which is signalled with a IllegalArgumentException

Question 7

What special cases arise for the remove method?

Answer 7

invalid position & empty list which are signalled by IndexOutOBoundsException

Question 8

What fields does an array implemented list have in general?

Answer 8

An array that holds the data and a numItems feild

Question 9

How does a circularly list node differ from a regular linked list?

Answer 9

A circularly linked node’s last node points to the first & vice versa if it is also doubly-linked

Question 10

What type is a stack?

Answer 10

Last-In-First-Out (LIFO)

Question 11

What three unique operations does a stack have?

Answer 11

• push: adds to the top of the stack
• pop: remove and returns the top of the stack
• peek: returns the top of the stack

Question 12

What type is a queue?

Answer 12

First-In-First-Out (FIFO)

Question 13

What two operations does a queue have?

Answer 13

• enqueue: add to the rear

- dequeuer: removes from the front

Question 14

To implement a queue with a linked list, what must be done to make the methods efficient?

Answer 14

Create a circularly linked list

Question 15

What fields are included in the linked list constructor?

Answer 15

A reference to a header node and/or tail pointer and a numItems variable

Question 16

What type of variables ARE the members of a list with the array implementation vs. the linked list implementation?

Answer 16

arbitrary object, list node object that holds an arbitrary object (with a next field)

Question 17

What iterator must be used to traverse a list?

Answer 17

An indirect iterator, since the array is not accessible by the iterator class since the data is only accessible through the list field in the iterator class

Question 18

What main problem does a doubly linked node fix?

Answer 18

The need to traverse to the node just before n

Question 19

What special cases have to be dealt with when removing a node from a doubly linked list?

Answer 19

When the node is either the first or last node. Thiss can be fixed by making it circular

Question 20

What special case needs to be dealt with in the remove method of a circular list?

Answer 20

When removing the header node the header pointer needs to be adjusted

Question 21

What is one main disadvantage of a doubly linked list?

Answer 21

It takes up more memory since each node has more fields

Question 22

What does pop and peek throw?

Answer 22

EmptyStackException

Question 23

What does dequeuer throw?

Answer 23

EmptyQueueException

Question 24

What fields are in the constructor of the array implementation of a stack?

Answer 24

1. ) array of objects
2. )size constant
3. )numItems

Question 25

What location is the most efficient to have the top of the stack?

Answer 25

The end of the array so data members don’t have to be shifted

Question 26

For a DS that implements an array what options are there to expand the array?

Answer 26

shadow array (O(1)) and creating a larger array and copying the values

Question 27

Why is the top of the linked list implementation of a stack at the beginning (@header node) rather than the end?

Answer 27

Because the header node can directly access the top without traversing

Question 28

What is the problem with the naiive array implementation of the queue?

Answer 28

To remove from the front, the members have to be shifted to array[0]. This is solved by keeping a front and rear index field.

Question 29

What index points to the rear where elements are added in a queue?

Answer 29

The rear index

Question 30

When the circular array is expanded (rear & front index are adjacent) where are the new values copied to?

Answer 30

• All indexes from the front index to the end of the array are copied to the same front index
• Add values from the beginning of the array to the rear index after the first sequence of insertions

Question 31

What three fields are in the LList implementation of a queue?

Answer 31

The front node
The rear node
numItems

Question 32

What is the advantage of the array implementation of a stack and queue?

Answer 32

The indices point to the data themselves and not list nodes (this goes for any array implementation)