diff options
author | David E. O'Brien <obrien@FreeBSD.org> | 2007-11-02 00:34:44 +0000 |
---|---|---|
committer | David E. O'Brien <obrien@FreeBSD.org> | 2007-11-02 00:34:44 +0000 |
commit | ed741d4e2df893bf9a78016eee08a469056846e8 (patch) | |
tree | dd9eb83925028fb4589fca25af2a849c65191ca2 /share/man/man3/queue.3 | |
parent | b58389792dff6c1ab0ea44104164b1192536d2d1 (diff) | |
download | src-ed741d4e2df893bf9a78016eee08a469056846e8.tar.gz src-ed741d4e2df893bf9a78016eee08a469056846e8.zip |
Don't imply O(n) removal for the doubly linked data structures.
Notes
Notes:
svn path=/head/; revision=173267
Diffstat (limited to 'share/man/man3/queue.3')
-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 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: |