Java Reference
In-Depth Information
A
doubly linked list
contains nodes with two pointers. One points to the next node and the
other to the previous node, as shown in Figure 24.18b. These two pointers are conveniently
called
a forward pointer
and
a backward pointer
. Thus, a doubly linked list can be traversed for-
ward and backward. The
java.util.LinkedList
class is implemented using a doubly linked
list, and it supports traversing of the list forward and backward using the
ListIterator
.
A
circular
,
doubly linked list
is like a doubly linked list, except that the forward pointer of
the last node points to the first node and the backward pointer of the first pointer points to the
last node, as shown in Figure 24.18c.
The implementations of these linked lists are left as exercises.
24.12
✓
✓
Both
MyArrayList
and
MyLinkedList
are used to store a list of objects. Why do
we need both types of lists?
Check
Point
24.13
Draw a diagram to show the linked list after each of the following statements is executed.
MyLinkedList<Double> list =
new
MyLinkedList<>();
list.add(
1.5
);
list.add(
6.2
);
list.add(
3.4
);
list.add(
7.4
);
list.remove(
1.5
);
list.remove(
2
);
24.14
What is the time complexity of the
addFirst(e)
and
removeFirst()
methods in
MyLinkedList
?
24.15
Suppose you need to store a list of elements. If the number of elements in the pro-
gram is fixed, what data structure should you use? If the number of elements in the
program changes, what data structure should you use?
24.16
If you have to add or delete the elements at the beginning of a list, should you use
MyArrayList
or
MyLinkedList
? If most of the operations on a list involve retriev-
ing an element at a given index, should you use
MyArrayList
or
MyLinkedList
?
24.17
Simplify the code in lines 75-80 in Listing 24.6 using a conditional expression.
Stacks can be implemented using array lists and queues can be implemented using
linked lists.
Key
Point
A stack can be viewed as a special type of list whose elements are accessed, inserted, and
deleted only from the end (top), as shown in Figure 10.11. A queue represents a waiting list.
It can be viewed as a special type of list whose elements are inserted into the end (tail) of the
queue, and are accessed and deleted from the beginning (head), as shown in Figure 24.19.
Data1
Data2
Data3
Data3
Data2
Data2
Data1
Data1
Data1
Data3
Data3
Data2
Data1
Data2
Data3
F
IGURE
24.19
A queue holds objects in a first-in, first-out fashion.
Search WWH ::
Custom Search