From ed741d4e2df893bf9a78016eee08a469056846e8 Mon Sep 17 00:00:00 2001 From: "David E. O'Brien" Date: Fri, 2 Nov 2007 00:34:44 +0000 Subject: Don't imply O(n) removal for the doubly linked data structures. --- share/man/man3/queue.3 | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) (limited to 'share/man/man3/queue.3') diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3 index b92cf74f46f2..b4556e57d3f1 100644 --- a/share/man/man3/queue.3 +++ b/share/man/man3/queue.3 @@ -179,22 +179,28 @@ Insertion of a new entry after any element in the list. .It O(1) removal of an entry from the head of the list. .It -O(n) removal of any entry in the list. -.It Forward traversal through the list. .El .Pp +O(n) removal of any entry in the list. Singly-linked lists are the simplest of the four data structures and support only the above functionality. Singly-linked lists are ideal for applications with large datasets and few or no removals, or for implementing a LIFO queue. +Singly-linked lists add the following functionality: +.Bl -enum -compact -offset indent +.It +O(n) removal of any entry in the list. +.El .Pp Singly-linked tail queues add the following functionality: .Bl -enum -compact -offset indent .It Entries can be added at the end of a list. .It +O(n) removal of any entry in the list. +.It They may be concatenated. .El However: -- cgit v1.2.3