Linked data structures - ch15

Question 1

linked data structure

Answer 1

consists of capsules of data known as nodes that are connected via links

Question 2

link

Answer 2

references

• memory address and is stored in a variable of a class type
• link is an instance variable of the node class type itself

Question 3

nodes

Answer 3

objects of the node class

Question 4

data in a node is stored as,,,

Answer 4

stored via instance variables

Question 5

linked list

Answer 5

consist of single chain of nodes each connected to the next via a link - first node: head node, last node: end marker

Question 6

how to traverse through a linked list

Answer 6

while (position != null) { count++ /count is an int initialized to 0/; position = position.getLink( ); return count; }

Question 7

getLink( )

Answer 7

returns an instance of a class - someone can change the class? Privacy leak -- to fix this: make the node class private and inside linked list class -create node class
All you need for a node class- (you don’t need accessor or mutator methods)

Question 8

indicating the end of the linked list

Answer 8

link instance variable equal to null… == not .equals

Question 9

adding a node

Answer 9

adds node to the start of the linked list - the new node is now the head node

Question 10

deleting a head node

Answer 10

deleteHeadNode removes the first node from the linked list

Question 11

what happens when using deleteHeadNode()

Answer 11

leaves the head var pointing to the old second node
the deletes one will automatically be collected and its memory recycled along with any other nodes that are no longer accessible - automatic garbage collection

Question 12

node inner classes

Answer 12

have the node class be inner classes of the linked list class

Question 13

generic linked list

Answer 13

can hold objects of any class type - including types that contains multiple instance variables

Question 14

the copyOf method

Answer 14

The private helping method copyOf takes an argument that is a reference to a head node of a linked list, and returns a reference to the head node of a copy of that list

Question 15

shallows and deep copy constructors, publicly cloneable , clone method, equals method

Answer 15

do examples - see notes

Question 16

what is an iterator

Answer 16

any object that enables a list to be traversed

a linked list can be created with an iterator inner class

Question 17

what are the basic methods used by an iterator

Answer 17

restart
next
hasNext

Question 18

what is an iterator usually used for?

Answer 18

adding and deleting nodes

Question 19

how does deleting a node at a certain position work

Answer 19

bypassing that particular node and change the node - does the node disappear - not immediately, it then becomes garbage

Question 20

explicit memory management

Answer 20

when the programmer has to keep track of the deleted nodes and explicitly return their memory for recycling

Question 21

adding a node to a specific position

Answer 21

previous will point to the node before the insertion point, and position will point to the node after the insertion point Node temp = new Node(newData,position);
previous.link = temp;

Question 22

how does it work when adding a node to a certain position

Answer 22

create a node with the link the the current position node
makes the previous node link to the reference of the new node
it now flows

Question 23

what is a doubly linked list

Answer 23

each node knows what the next and previous nodes are - 2 way node chain

Question 24

adding, deleting and inserting a node to a doubly linked list

Answer 24

google simpler thing

Question 25

stack data structure

Answer 25

Removes items in the reverse order - Last in first out LIFO
Implementing linked list without the iterator - basically implementing a stack
Inserting a node - push
Pop - deletes the head node
Can create own stack using an array

Question 26

queue data structure

Answer 26

FIFO - first in first out
Can use a linked list - we are inserting at the tail - we need to be able to add to the end of the queue and then we remove from the head
Dequeue - add to both ends of the queue
Queue in Java is actually an interface that can be implemented
ArrayDequeue class - implements your queue as an array

Question 27

what is dequeue

Answer 27

Dequeue - add to both ends of the queue