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 mak-
ing 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 dele-
tion 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 pro-
gram 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 effi-
ciently. 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 Stor-
age Rule is followed, then there are efficient algorithms for reaching values stored
in the tree.
