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.
24.5 Stacks and Queues
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