prev up next   top/contents search

comp.lang.c FAQ list · Question 13.10

Q: How can I sort a linked list?

A: Sometimes it's easier to keep the list in order as you build it (or perhaps to use a tree instead). Algorithms like insertion sort and merge sort lend themselves ideally to use with linked lists. If you want to use a standard library function, you can allocate a temporary array of pointers, fill it in with pointers to all your list nodes, call qsort, and finally rebuild the list pointers based on the sorted array.

Additional links: example by Chris Torek

References: Knuth Sec. 5.2.1 pp. 80-102, Sec. 5.2.4 pp. 159-168
Sedgewick Sec. 8 pp. 98-100, Sec. 12 pp. 163-175

prev up next   contents search
about this FAQ list   about eskimo   search   feedback   copyright

Hosted by Eskimo North