Java Reference
In-Depth Information
T
ABLE
24.1
Time Complexities for Methods in
MyArrayList
and
MyLinkedList
Methods
MyArrayList/ArrayList
MyLinkedList/LinkedList
add(e: E)
O
(1)
O
(1)
add(index: int, e: E)
O
(
n
)
O
(
n
)
clear()
O
(1)
O
(1)
O
(
n
)
O
(
n
)
contains(e: E)
get(index: int)
O
(1)
O
(
n
)
indexOf(e: E)
O
(
n
)
O
(
n
)
isEmpty()
O
(1)
O
(1)
O
(
n
)
O
(
n
)
lastIndexOf(e: E)
remove(e: E)
O
(
n
)
O
(
n
)
size()
O
(1)
O
(1)
remove(index: int)
O
(
n
)
O
(
n
)
O
(
n
)
O
(
n
)
set(index: int, e: E)
addFirst(e: E)
O
(
n
)
O
(1)
removeFirst()
O
(
n
)
O
(1)
24.4.5 Variations of Linked Lists
The linked list introduced in the preceding sections is known as a
singly linked list
. It contains
a pointer to the list's first node, and each node contains a pointer to the next node sequentially.
Several variations of the linked list are useful in certain applications.
A
circular, singly linked list
is like a singly linked list, except that the pointer of the last
node points back to the first node, as shown in Figure 24.18a. Note that
tail
is not needed
for circular linked lists.
head
points to the current node in the list. Insertion and deletion take
place at the current node. A good application of a circular linked list is in the operating system
that serves multiple users in a timesharing fashion. The system picks a user from a circular list
and grants a small amount of CPU time, then moves on to the next user in the list.
Node 1
Node 2
Node
n
head
...
element1
next
element2
next
element
n
next
(a) Circular linked list
Node 1
element1
next
null
Node 2
element2
next
previous
Node
n
element
n
null
previous
head
...
tail
(b) Doubly linked list
Node 1
element1
next
previous
Node 2
element2
next
previous
Node
n
element
n
next
previous
head
...
(c) Circular doubly linked list
F
IGURE
24.18
Linked lists may appear in various forms.
Search WWH ::
Custom Search