ADTs

Question 1

How do you implement the code for a function that counts the elements in a linkedlist?

Answer 1

1. public driver - checks to make sure there are nodes
2. private helper - if next isn’t null, add one and count the next

Question 2

1. Why use dummy nodes?
2. How is it implemented?

Answer 2

1. The first node, last node, only node or empty list lead to special coding cases:
   
   1. lots of ifs
   2. lots of potential bugs
   3. less readable
   4. less easily and reliable to modify
2. Add a “dummy” or “header” or “trailer” node to one end or the other end or both ends of a linked list, to ensure that the nodes containing real data are never the first, last or only nodes, and that top is neve null.
   
   1. Dummy nodes may contain undefined data, but in ordered lists should have appropriate extreme data values
   2. with back linking you can tell if a node is a dummy node if one of its links is null.

Question 3

For trailer and header Nodes, where do the variables exist?

How do you code the trailer and header?

Answer 3

Inside the constructor only

Question 4

What is the code to insert an item into a header/footer ordered linkedlist?

How does it differ from a list without headers?

Answer 4

without a header we have to check if curr and prev are null etc..

With headers, that additional code is no longer necessary

Question 5

How do you delete a value by key with a linkedlist with header files?

How does this differe for an ordered/unordered list?

Answer 5

For unordered-check if curr is not the dummy trailer as well

add to while loop: prev.next.next != null

Question 6

What is a circular linked list and why use it?

Answer 6

• The last node points to the first node (not top).

How it could be useful:

• This would allow you to search the list starting at any node
• An easy way to find both ends, have top pointer point to the last node
  
  • Last node: last
  • First node: last.next

Question 7

Stack - where are new items added?

Answer 7

New elements are added at the top

LIFO - Last in first out

FILO - First in last out

Question 8

Queue - where are new items added

Answer 8

Added to the back

FIFO - first in, first out

LILO - last in, last out

Question 9

What are the stack main operations?

Answer 9

• push - add something to the top
• pop - remove something from the top
• top - only look at the top
• isEmpty
• constructor
• destructor - in languages without garbage collection
• isFull - if space is limited

Question 10

What is the text representation of a stack?

Answer 10

[5 7 3 >,

[ represents the bottom

> represents the top

Question 11

In general how do you implement a stack with an array?

Answer 11

• The bottom of the stack is always index-0
• The stack class needs an int variable called “top” that contains the index o the top of the stackin the array
• limitation - fixed size

Question 12

What is the code for the class implementation of a Stack using an array?

Answer 12

Question 13

Draw the ?variable record? diagram for a stack using an array

Answer 13

Question 14

In general, how would you implement a stack using a linkedlist

Answer 14

• each node contains an item in the stack
• the front of the list (the top pointer) is the top of the stack

Question 15

What is the code for the class implementation of a stack using a linkedlist

Answer 15

Question 16

Draw the ?variable record? for stack using a linkedlist

Answer 16

Question 17

What is the pseudo code for implementing the bracket matching example

Answer 17

Question 18

What is the text representation of a queue

Answer 18

< 7 3 4 <

the 7 would be at the front, the 4 would be at the end

angle brackets point in the direction that items move through the queue

Question 19

What are queue basic operations?

Answer 19

• Enter (or enqueue) - add item
• Leave (or dequeue) - remove item
• Front - loop only at the front of the queue(without removing it)
• isEmpty

Question 20

ADT Queue - LinkedList

Draw a general linkedlist style 1 using both a front and end pointer

Answer 20

Question 21

What is the class code for a queue linked list style 1 (front and end pointer)

Answer 21

Question 22

Queue - Linkedlist style 1 - front and end pointer

Draw a ?varaible record? of what the implementation looks like

Answer 22

Question 23

Queue - LinkedList Style 2 (circular)

Draw the implementation of a queue using a circular linkedlist

Answer 23

Question 24

Queue - LinkedList Style 2 (circular)

Draw the general implementation of a queue using a circular linkedlist to Enqueue(enter) an item.

Answer 24

Question 25

Queue - LinkedList Style 2 (circular)

Draw the general implementation of a queue using a circular linkedlist to dequeue(leave) and element

Answer 25

Question 26

In general, what would a array queue implementation look like

Answer 26

Question 27

What are the bad implmentations of array queue?

Answer 27

1. leave from index-0 and shift all elements over over (O(n)).
2. Let the front move position (array moves right continually)

Question 28

How do you implement a circular array with Mod?

Answer 28

Implement a front and end for the array.

end = (end+1) % queueArray.length;

(The result is an integer in the range 0..queueArray.length-1)

Question 29

How does the mod operation table work/look?

Answer 29

Question 30

What are the solutions to using a circular array and distinguise between a full and empty array?

Answer 30

1. Keep a third variable in addition to front and end.
   
   • positiblities
     
     • empty or full, a boolean flag
     • count(an int), the number of elements.
2. Simply do not allow the n^th element to be used.
   
   • Example: If the array has space for 8 elements, then the queue can only hold 7
   • Always leave at least one empty space
3. Make end point to the first empty slot(the next ont to be filled by an entering element)
   
   • Use with solution 2

Question 31

How fast should all queue operations be and how do you ensure that is achieved?

Answer 31

O(1)

Before you program, think about which end you should do insertions and deletions at to make sure that NO loops are needed