Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Tim Chase Newsgroups: comp.lang.python Subject: Re: PEP Request: Advanced Data Structures Date: Sat, 16 Jul 2016 19:45:10 -0500 Lines: 34 Message-ID: References: <21fcec53-cf5b-4529-9790-63a1c46f534b@googlegroups.com> <20160716194510.6283c8f4@bigbox.christie.dr> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Trace: news.uni-berlin.de b72ntorBwq6eil0S7SyJ5gQ9DszI5g9Z5oyWmHV7K8UA== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.003 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'list?': 0.07; 'subject:PEP': 0.07; 'alternatives': 0.09; '-tkc': 0.16; 'bisect': 0.16; 'deque': 0.16; 'from:addr:python.list': 0.16; 'from:addr:tim.thechases.com': 0.16; 'from:name:tim chase': 0.16; 'heapq': 0.16; 'n),': 0.16; 'pypi.': 0.16; 'received:10.21': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'skip:{ 30': 0.16; 'subject:Advanced': 0.16; 'time"': 0.16; 'wrote:': 0.16; 'nested': 0.18; 'algorithm': 0.20; 'handles': 0.20; 'fairly': 0.22; 'for?': 0.23; 'header:In-Reply-To:1': 0.24; 'rest': 0.26; 'chris': 0.26; 'specifically': 0.28; 'actual': 0.28; 'regular': 0.29; "i'm": 0.30; 'usually': 0.33; 'lists': 0.34; 'something': 0.35; 'instead': 0.36; 'there': 0.36; 'serve': 0.36; 'basic': 0.36; 'modules': 0.36; 'structures': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'beyond': 0.37; 'charset :us-ascii': 0.37; 'anything': 0.38; 'log': 0.38; 'why': 0.39; 'to:addr:python.org': 0.40; 'where': 0.40; 'some': 0.40; 'linked': 0.63; 'times': 0.63; 'subject:Data': 0.66; 'wanting': 0.66; 'received:23': 0.84 X-Sender-Id: wwwh|x-authuser|tim@thechases.com X-Sender-Id: wwwh|x-authuser|tim@thechases.com X-MC-Relay: Neutral X-MailChannels-SenderId: wwwh|x-authuser|tim@thechases.com X-MailChannels-Auth-Id: wwwh X-MC-Loop-Signature: 1468716312250:853861079 X-MC-Ingress-Time: 1468716312249 In-Reply-To: X-Mailer: Claws Mail 3.11.1 (GTK+ 2.24.25; x86_64-pc-linux-gnu) X-AuthUser: tim@thechases.com X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Mailman-Original-Message-ID: <20160716194510.6283c8f4@bigbox.christie.dr> X-Mailman-Original-References: <21fcec53-cf5b-4529-9790-63a1c46f534b@googlegroups.com> Xref: csiph.com comp.lang.python:111547 On 2016-07-17 08:19, Chris Angelico wrote: > Why do you need a linked list? That's an implementation detail; why > not simply use a regular list? > > Not trolling, genuinely asking. Is there something that you > specifically need those exact structures for? I know there have been times I want known performance characteristics. My main reason for wanting linked lists is usually for stacks/queues with O(1) push/pop, and I understand that a deque handles most of that fairly efficiently ("approximately the same O(1) performance in either direction"). The bisect and heapq modules also help with some of my usual use-cases for BSTs (presuming "BST" unpacks as "binary search tree"), while nested arrays/dicts usually serve for most of the rest of my other tree/trie needs. So usually I'm less concerned with the actual algorithm name than I am with the "I want to {push,pop,search,insert,delete} in O(f) time" where O(f) is usually either O(1) or O(N log N), instead of the alternatives which might use O(N), O(N**k), or worse, O(k**N). For anything beyond those basic CS data-structures, there's usually something conveniently in PyPI. -tkc