delorie.com/archives/browse.cgi   search  
Mail Archives: djgpp/1997/06/06/12:56:49

Message-Id: <339840F5.4280@juno.com>
Date: Fri, 06 Jun 1997 09:55:17 -0700
From: Ben Shadwick <bshadwick AT juno DOT com>
Mime-Version: 1.0
To: djgpp AT delorie DOT com
Subject: Re: LinkedLists
References: <Pine DOT SGI DOT 3 DOT 91 DOT 970604225308 DOT 25744A-100000 AT neutrino DOT phys DOT laurentian DOT ca>

Timothy Robb wrote:
> I've given up on Quick Sorting my list because I will be adding one item
> at a time to it and the add function will call the sort function, as a
> result Insertion Sort would probably be the best method.
> 
> My next problem is binary searching through a linked list....

You'd probably be better off turning your linked list into a binary search tree (a 
sorted tree), which, if a good tree is built, yields a searching performance comparable 
to that of a binary search when used on contiguous lists (arrays). Binary search and 
quicksort are really bad for use on linked lists because the elements in a linked list 
cannot each be accessed in the same amount of time (i.e. linked lists don't have random 
access).

Ben Shadwick, Sysop, Mars Base BBS, (360)882-0773, Vancouver, WA, USA
email: bshadwick AT juno DOT com >> SPAMMING WILL NOT BE TOLERATED <<
Have a nice day!

- Raw text -


  webmaster     delorie software   privacy  
  Copyright 2019   by DJ Delorie     Updated Jul 2019