p223, last paragraph. implies that deletion of an item from a doubly (but not singly) linked list can be accomplished in O(1). Don't you still have to find the item in the list before you can delete it (taking O(n)), regardless of the linking? Thus the whole operation takes O(n) regardless of linking.