diff options
author | obrien <obrien@FreeBSD.org> | 2007-11-02 00:34:44 +0000 |
---|---|---|
committer | obrien <obrien@FreeBSD.org> | 2007-11-02 00:34:44 +0000 |
commit | cf14784fcb6abf01e302afe1079b36a532dc3ab3 (patch) | |
tree | dd9eb83925028fb4589fca25af2a849c65191ca2 /share/man/man3 | |
parent | f99a913488ed0201021205f193c9902c7f34b123 (diff) | |
download | FreeBSD-src-cf14784fcb6abf01e302afe1079b36a532dc3ab3.zip FreeBSD-src-cf14784fcb6abf01e302afe1079b36a532dc3ab3.tar.gz |
Don't imply O(n) removal for the doubly linked data structures.
Diffstat (limited to 'share/man/man3')
-rw-r--r-- | share/man/man3/queue.3 | 10 |
1 files changed, 8 insertions, 2 deletions
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3 index b92cf74..b4556e5 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: |