Java Reference
In-Depth Information
7.9 Comparisons of core data-structures
We have described several data-structures for organizing a collection of
objects that provide basic operations such as inserting/deleting and searching
whether a given query element belongs to the collection. We have seen that
arrays are well-suited to static data-sets but fail short in case we need to
delete/add elements. Linked lists have then be introduced for fully maintaining
the collection of elements. However, searching using linked lists could be
tricky. We finally combined both array and linked list technique in the
hashing framework showing clearly its advantages when no collisions occur.
The table 7.1 quickly summarizes the various time complexity operations of
respective data-structures.
Data-structure
Initialization
Search
Insert
Delete
Array
O(1)
O(n)
O(1)
O(n)
Sorted array
O(n log n)
O (log n)
O(n)
O(n)
Hashing
O(1)
Almost O(1)
Almost O(1)
Almost O(1)
(Chained list)
List
O(1)
O(n)
O(1)
O(n)
Table 7.1
Performance of various data-structures
7.10 Exercises
Exercise 7.1 (Linked lists for intervals)
Write a class
Interval
that stores the range
min
/
max
of intervals. Create
a linked list of intervals. Provide the usual functions:
add
,
remove
,
length
and
display
.
Exercise 7.2 (Doubly linked lists)
A polygon is a piecewise linear non-self-intersecting closed curve. We
consider modeling a polygon by its set of vertices (2D points stored in
an array) with a linked list of vertex indices (integers). Write a class
Polygon
with a constructor that takes as its argument an array of 2D
points describing the cyclic sequence of vertices. The linked list shall be
bidirectional using the
prev
and
succ
fields.
Search WWH ::
Custom Search