| 1 |
.\" Copyright 1993, The Regents of the University of California. |
| 2 |
.\" Copyright, the authors of the Linux man-pages project |
| 3 |
.\" |
| 4 |
.\" SPDX-License-Identifier: BSD-3-Clause |
| 5 |
.\" |
| 6 |
.TH queue 7 2025-05-17 "Linux man-pages 6.18" |
| 7 |
.SH NAME |
| 8 |
queue \- implementations of linked lists and queues |
| 9 |
.SH DESCRIPTION |
| 10 |
The |
| 11 |
.I <sys/queue.h> |
| 12 |
header file provides a set of macros that |
| 13 |
define and operate on the following data structures: |
| 14 |
.TP |
| 15 |
SLIST |
| 16 |
singly linked lists |
| 17 |
.TP |
| 18 |
LIST |
| 19 |
doubly linked lists |
| 20 |
.TP |
| 21 |
STAILQ |
| 22 |
singly linked tail queues |
| 23 |
.TP |
| 24 |
TAILQ |
| 25 |
doubly linked tail queues |
| 26 |
.TP |
| 27 |
CIRCLEQ |
| 28 |
doubly linked circular queues |
| 29 |
.P |
| 30 |
All structures support the following functionality: |
| 31 |
.IP \[bu] 3 |
| 32 |
Insertion of a new entry at the head of the list. |
| 33 |
.IP \[bu] |
| 34 |
Insertion of a new entry after any element in the list. |
| 35 |
.IP \[bu] |
| 36 |
O(1) removal of an entry from the head of the list. |
| 37 |
.IP \[bu] |
| 38 |
Forward traversal through the list. |
| 39 |
.\".IP \[bu] |
| 40 |
.\" Swapping the contents of two lists. |
| 41 |
.P |
| 42 |
Code size and execution time |
| 43 |
depend on the complexity of the data structure being used, |
| 44 |
so programmers should take care to choose the appropriate one. |
| 45 |
.SS Singly linked lists (SLIST) |
| 46 |
Singly linked lists are the simplest |
| 47 |
and support only the above functionality. |
| 48 |
Singly linked lists are ideal for applications with |
| 49 |
large datasets and few or no removals, |
| 50 |
or for implementing a LIFO queue. |
| 51 |
Singly linked lists add the following functionality: |
| 52 |
.IP \[bu] 3 |
| 53 |
O(n) removal of any entry in the list. |
| 54 |
.SS Singly linked tail queues (STAILQ) |
| 55 |
Singly linked tail queues add the following functionality: |
| 56 |
.IP \[bu] 3 |
| 57 |
Entries can be added at the end of a list. |
| 58 |
.IP \[bu] |
| 59 |
O(n) removal of any entry in the list. |
| 60 |
.IP \[bu] |
| 61 |
They may be concatenated. |
| 62 |
.P |
| 63 |
However: |
| 64 |
.IP \[bu] 3 |
| 65 |
All list insertions must specify the head of the list. |
| 66 |
.IP \[bu] |
| 67 |
Each head entry requires two pointers rather than one. |
| 68 |
.P |
| 69 |
Singly linked tail queues are ideal for applications with |
| 70 |
large datasets and few or no removals, |
| 71 |
or for implementing a FIFO queue. |
| 72 |
.SS Doubly linked data structures |
| 73 |
All doubly linked types of data structures (lists and tail queues) |
| 74 |
additionally allow: |
| 75 |
.IP \[bu] 3 |
| 76 |
Insertion of a new entry before any element in the list. |
| 77 |
.IP \[bu] |
| 78 |
O(1) removal of any entry in the list. |
| 79 |
.P |
| 80 |
However: |
| 81 |
.IP \[bu] 3 |
| 82 |
Each element requires two pointers rather than one. |
| 83 |
.SS Doubly linked lists (LIST) |
| 84 |
Linked lists are the simplest of the doubly linked data structures. |
| 85 |
They add the following functionality over the above: |
| 86 |
.IP \[bu] 3 |
| 87 |
They may be traversed backwards. |
| 88 |
.P |
| 89 |
However: |
| 90 |
.IP \[bu] 3 |
| 91 |
To traverse backwards, an entry to begin the traversal and the list in |
| 92 |
which it is contained must be specified. |
| 93 |
.SS Doubly linked tail queues (TAILQ) |
| 94 |
Tail queues add the following functionality: |
| 95 |
.IP \[bu] 3 |
| 96 |
Entries can be added at the end of a list. |
| 97 |
.IP \[bu] |
| 98 |
They may be traversed backwards, from tail to head. |
| 99 |
.IP \[bu] |
| 100 |
They may be concatenated. |
| 101 |
.P |
| 102 |
However: |
| 103 |
.IP \[bu] 3 |
| 104 |
All list insertions and removals must specify the head of the list. |
| 105 |
.IP \[bu] |
| 106 |
Each head entry requires two pointers rather than one. |
| 107 |
.SS Doubly linked circular queues (CIRCLEQ) |
| 108 |
Circular queues add the following functionality over the above: |
| 109 |
.IP \[bu] 3 |
| 110 |
The first and last entries are connected. |
| 111 |
.P |
| 112 |
However: |
| 113 |
.IP \[bu] 3 |
| 114 |
The termination condition for traversal is more complex. |
| 115 |
.SH STANDARDS |
| 116 |
BSD. |
| 117 |
.SH HISTORY |
| 118 |
.I <sys/queue.h> |
| 119 |
macros first appeared in 4.4BSD. |
| 120 |
.SH NOTES |
| 121 |
Some BSDs provide SIMPLEQ instead of STAILQ. |
| 122 |
They are identical, but for historical reasons |
| 123 |
they were named differently on different BSDs. |
| 124 |
STAILQ originated on FreeBSD, and SIMPLEQ originated on NetBSD. |
| 125 |
For compatibility reasons, some systems provide both sets of macros. |
| 126 |
glibc provides both STAILQ and SIMPLEQ, |
| 127 |
which are identical except for a missing SIMPLEQ equivalent to |
| 128 |
.BR STAILQ_CONCAT (). |
| 129 |
.SH SEE ALSO |
| 130 |
.BR circleq (3), |
| 131 |
.BR insque (3), |
| 132 |
.BR list (3), |
| 133 |
.BR slist (3), |
| 134 |
.BR stailq (3), |
| 135 |
.BR tailq (3) |
| 136 |
.\" .BR tree (3) |