Java Reference
In-Depth Information
Chapter Summary
•
A
linked list
is a data structure consisting of objects known as
nodes
, such that each
node contains data and also a reference to one other node so that the nodes link
together to form a list.
•
Setting a link instance variable to
null
indicates the end of a linked list (or other
linked data structure).
null
is also used to indicate an empty linked list (or other
empty linked data structure).
•
You can make a linked list (or other linked data structure) self-contained by making
the node class an inner class of the linked list class.
•
In many situations, a
clone
method or copy constructor is best defined so that it
makes a deep copy.
•
You can use an
iterator
to step through the elements of a collection, such as the
elements in a linked list.
•
Nodes in a
doubly linked list
have two links—one to the previous node in the list and
one to the next node. This makes some operations, such as insertion and deletion,
slightly easier.
•
A
stack
is a data structure in which elements are removed in the reverse of the order
they were added to the stack. A
queue
is a data structure in which elements are
removed in the same order that they were added to the queue.
•
Big-O notation
specifies an upper bound for how many steps or how long a program
will take to run based on the size of the input to the program. This can be used to
analyze the efficiency of an algorithm.
•
A
hash table
is a data structure that is used to store objects and retrieve them efficiently.
A
hash function
is used to map an object to a value that can then be used to index the
object.
•
Linked lists can be used to implement sets, including common operations such as
union, intersection, and set membership.
•
A
binary tree
is a branching linked data structure consisting of nodes that each have
two link instance variables. A tree has a special node called the
root node
. Every node
in the tree can be reached from the root node by following links.
•
If values are stored in a binary tree in such a way that the
Binary Search Tree
Storage Rule
is followed, then there are efficient algorithms for reaching values stored
in the tree.
