Property/Data Structure | Array | Vector | Linked List |
Contiguous in memory | X | X | |
Can access an element in O(1) time | X | X | |
Length can change | X | X | |
Causes fragmentation of the free store | X | ||
Can add a new element to the front of the list in O(1) time | X |
Discussion:
myArray
is an int
array of length 10,
and if an int
requires 4 bytes,
then the address of
myArray[1]
will be 4 higher
than the address of
myArray[0]
.
myArray[k]
is
the address of
myArray[0]
plus 4k
.
Ask for help with this question.
LinkedList
:
insertBefore (Object& target, Object& newObject)
:newObject
into the list immediately before the node containing
target
,
or throws a
LinkedListNotFound
exception.
template <class Object> void LinkedList<Object>::insertBefore ( Object& target, Object& newObject) { // LinkedList<Object>::insertBefore if (isEmpty()) throw LinkedListNotFoundException(); if (*_info == target) add(newObject); else { if (_next == NULL) throw LinkedListNotFoundException(); _next->insertBefore(target, newObject); } // if (*_info == target)...else } // LinkedList<Object>::insertBefore
insertAfter (Object& target, Object& newObject)
:newObject
into the list immediately after the node containing
target
,
or throws a
LinkedListNotFound
exception.
template <class Object> void LinkedList<Object>::insertAfter ( Object& target, Object& newObject) { // LinkedList<Object>::insertAfter if (isEmpty()) throw LinkedListNotFoundException(); if (*_info == target) { if (_next == NULL) _next = new LinkedList(newObject); else _next->add(newObject); } // if (*_info == target) else { if (_next == NULL) throw LinkedListNotFoundException(); _next->insertAfter(target, newObject); } // if (*_info == target)...else } // LinkedList<Object>::insertAfter
remove (Object& target)
:target
from the list.
template <class Object> void LinkedList<Object>::remove (Object& target) { // LinkedList<Object>::remove if (isEmpty()) return; if (*_info == target) { Object temp = remove(); } // if (*_info == target) if (_next != NULL) _next->remove(target); } // LinkedList<Object>::remove
==
operator
to determine whether two linked lists are equivalent.
You should not assume that either list has a particular order,
nor that the two lists have the same order.
template <class Object> bool LinkedList<Object>::operator== (LinkedList<Object>& ll) { // LinkedList<Object>::operator== if (isEmpty() && ll.isEmpty()) return true; if (isEmpty() || ll.isEmpty()) return false; try { Object temp = ll.find(*_info); } // try catch (LinkedListNotFoundException e) { return false; } // catch (LinkedListNotFoundException e) if ((_next == NULL) && (ll._next == NULL)) return true; if ((_next == NULL) || (ll._next == NULL)) return false; return _next->operator==(ll); } // LinkedList<Object>::operator==
Ask for help with this question.
insertBefore (Object& target, Object& newObject)
:
O(n)target
is found.
It then uses the add
method,
which takes
O(1)
time,
to insert the element immediately before
the target element that it has found.
insertAfter (Object& target, Object& newObject)
:
O(n)target
is found.
It
then
either
uses the add
method,
which takes
O(1)
time,
to insert the element immediately before the next element,
or, if there is no next element,
simply allocates a new element
and places it after the target element that it has found,
which also takes
O(1)
time.
remove (Object& target)
:
O(n)target
is found,
it removes that element,
which takes
O(1)
time,
because the element it intends to remove is always at the front of the list.
operator== (LinkedList& target)
:
O(n^{2})*this
,
which appears on the left side of the ==
operator
in the call to operator==
),
which takes
O(n)
time.
For each element in this traversal,
the method invokes
the find
method
of the other linked list, ll
(which appears on the left side of the ==
operator
in the call to operator==
),
which takes
O(n)
time.
Thus, there are
O(n)
calls to a method that takes
O(n)
time,
so the total time is
O(n^{2}).
Remark: In general, we ignore the best case, because it occurs so infrequently.
Ask for help with this question.
LinkedList
method
infoAt
?
What is the time complexity of binary search?)
Note: you do not have to implement the linked list binary search function.
Answer: O(nlogn)
The time complexity of the
LinkedList
method
infoAt
is
O(n),
by the same reasoning as for insertBefore
, above.
The time complexity of binary search is O(logn), as explained in OODS, Chapter 3.
The binary search algorithm requires examining the kth element of the list for each iteration of the binary search; specifically, k is the midpoint of the portion of the list currently being examined.
So, each of the
O(logn)
iterations of the binary search algorithm
requires a call to
infoAt
,
each of which takes
O(n)
time.
Because binary search on a linked list requires O(logn) calls to a method that takes O(n) time for each call, the algorithm takes O(nlogn) time.
Remark:
Not surprisingly, binary search is not a popular approach to searching
a sorted linked list,
because a simple linear traversal
takes only
O(n)
time,
which is substantially more efficient than
O(nlogn).
Ask for help with this question.
merge
function
(OODS, chapter 3)
to operate on two linked lists instead of two arrays.
You may assume that both linked lists are sorted in ascending order.
Note: because this question may appear on an exam, a solution is not provided here.
References
S. Rhadakrishnan, L. Wise & C. N. Sekharan,
Object-Oriented Data Structures Featuring C++,
1999.
A. Drozdek,
Data Structures and Algorithms in C++,
PWD Publishing Co., New York,
1996.