Linked data structures - ch15 Flashcards
linked data structure
consists of capsules of data known as nodes that are connected via links
link
references
- memory address and is stored in a variable of a class type
- link is an instance variable of the node class type itself
nodes
objects of the node class
data in a node is stored as,,,
stored via instance variables
linked list
consist of single chain of nodes each connected to the next via a link - first node: head node, last node: end marker
how to traverse through a linked list
while (position != null) { count++ /count is an int initialized to 0/; position = position.getLink( ); return count; }
getLink( )
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)
indicating the end of the linked list
link instance variable equal to null… == not .equals
adding a node
adds node to the start of the linked list - the new node is now the head node
deleting a head node
deleteHeadNode removes the first node from the linked list
what happens when using deleteHeadNode()
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
node inner classes
have the node class be inner classes of the linked list class
generic linked list
can hold objects of any class type - including types that contains multiple instance variables
the copyOf method
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
shallows and deep copy constructors, publicly cloneable , clone method, equals method
do examples - see notes
what is an iterator
any object that enables a list to be traversed
a linked list can be created with an iterator inner class
what are the basic methods used by an iterator
restart
next
hasNext
what is an iterator usually used for?
adding and deleting nodes
how does deleting a node at a certain position work
bypassing that particular node and change the node - does the node disappear - not immediately, it then becomes garbage
explicit memory management
when the programmer has to keep track of the deleted nodes and explicitly return their memory for recycling
adding a node to a specific position
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;
how does it work when adding a node to a certain position
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
what is a doubly linked list
each node knows what the next and previous nodes are - 2 way node chain
adding, deleting and inserting a node to a doubly linked list
google simpler thing
stack data structure
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
queue data structure
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
what is dequeue
Dequeue - add to both ends of the queue
