From owner-freebsd-hackers@FreeBSD.ORG  Fri Apr 23 18:21:52 2010
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: freebsd-hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 56E9B1065672
	for <freebsd-hackers@freebsd.org>; Fri, 23 Apr 2010 18:21:52 +0000 (UTC)
	(envelope-from pieter@degoeje.nl)
Received: from smtp.utwente.nl (smtp1.utsp.utwente.nl [130.89.2.8])
	by mx1.freebsd.org (Postfix) with ESMTP id CBE498FC20
	for <freebsd-hackers@freebsd.org>; Fri, 23 Apr 2010 18:21:51 +0000 (UTC)
Received: from nox.student.utwente.nl (nox.student.utwente.nl [130.89.165.91])
	by smtp.utwente.nl (8.12.10/SuSE Linux 0.7) with ESMTP id
	o3NILQcn002591; Fri, 23 Apr 2010 20:21:36 +0200
From: Pieter de Goeje <pieter@degoeje.nl>
To: freebsd-hackers@freebsd.org
Date: Fri, 23 Apr 2010 20:21:25 +0200
User-Agent: KMail/1.9.10
References: <l2ga2585ef1004090709u821fc979i226a3125d9da8251@mail.gmail.com>
	<i2za0777e081004230818y9008c7b7yc574298df85933dc@mail.gmail.com>
	<20100423154012.GA10560@britannica.bec.de>
In-Reply-To: <20100423154012.GA10560@britannica.bec.de>
MIME-Version: 1.0
Content-Type: text/plain;
  charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <201004232021.26160.pieter@degoeje.nl>
X-UTwente-MailScanner-Information: Scanned by MailScanner. Contact
	icts.servicedesk@utwente.nl for more information.
X-UTwente-MailScanner: Found to be clean
X-UTwente-MailScanner-From: pieter@degoeje.nl
X-Spam-Status: No
Cc: Leinier Cruz Salfran <salfrancl.listas@gmail.com>,
	Joerg Sonnenberger <joerg@britannica.bec.de>
Subject: Re: c question
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 23 Apr 2010 18:21:52 -0000

On Friday 23 April 2010 17:40:12 Joerg Sonnenberger wrote:
> On Fri, Apr 23, 2010 at 06:18:46PM +0300, Eitan Adler wrote:
> > > - use a matrix is faster than use a linked list?
> >
> > For what?
> > For insertion and deletion no - linked list is faster. For sequential
> > access they are the same speed (forgetting look-ahead caching). For
> > random access matrix is faster.
>
> Actually -- it depends. Removing the tail and inserting at tail is
> amortised constant time for arrays if done using the double-on-full
> trick. In that case, array can be the faster datastructure too.

Random deletes can be made O(1) if you don't care about the order of the 
elements in an array.

- Pieter