Re: [algogeeks] fastest sequential access
i) vector = A non synced data structure good for random access and bad for insertions,deletions and sequential scans. ii) Singly linked list = Bad for random access, good for one way sequential access, good for insertions in the middle. iii) Doubly linked list = Bad for random access, best for two way sequential access, good for insertions in the middle. Pralay Biswas MS-CS, University of California Irvine On Wed, Nov 21, 2012 at 6:51 AM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- --
Re: [algogeeks] fastest sequential access
I am sorry, vectors are synced and hence slow (concurrency overhead, arraylists are non synced). Rest remain the same, if your application demands frequent two way sequential scans, go for DLL. Pralay Biswas MS-CS, University of California Irvine On Wed, Nov 21, 2012 at 6:57 AM, Pralay Biswas pralaybiswas2...@gmail.comwrote: i) vector = A non synced data structure good for random access and bad for insertions,deletions and sequential scans. ii) Singly linked list = Bad for random access, good for one way sequential access, good for insertions in the middle. iii) Doubly linked list = Bad for random access, best for two way sequential access, good for insertions in the middle. Pralay Biswas MS-CS, University of California Irvine On Wed, Nov 21, 2012 at 6:51 AM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- --
Re: [algogeeks] fastest sequential access
i would rather suggest vector for FAST SEQUENTIAL ACCESS as Vector contain elements in contiguous memory locations...so cache locality is good in case of it as in case of Singly Linked List or Doubly Linked List,, cached locality is not good,, Sequntial access would not be fast in a long run.. On Thu, Nov 22, 2012 at 1:12 PM, atul anand atul.87fri...@gmail.com wrote: @shady : as subject says fastest sequential access , then if i am not getting it wrong.we only care of sequential access a value not modifying the linked list. so i guess double linked list would be helpful 1) bcozz it can move in both the direction , so if linked list is sorted then it would be a great help 2) if you want to insert element at the end of linked list then if will be better than vector so i guess it required 1-2 more parameter to decide ,which one to use. On Wed, Nov 21, 2012 at 8:21 PM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- -- -- *ATul Singh** Software Engineer**, Interra Systems* Mobile : +91-9410826039 www.interrrasystems.com [image: Facebook] http://www.facebook.com/atulsingh7890 [image: Twitter]http://www.twitter.com/atulsng [image: LinkedIn] http://www.linkedin.com/in/atulsingh7890 --
Re: [algogeeks] fastest sequential access
@Pralay.. can u give a more detail about non synced data structure --
Re: [algogeeks] fastest sequential access
Also, vectors are not contiguously memory slotted always. Its a expanding array where the resizing takes place on demand. There are times when the array backing the vector is resized and re-allocated, but even then the amortized cost of insertion stays linear (O(n)). Although it makes sense to think that since all the microprocessor requires to do is an index*datasize calculation in case of an array or a vector, it would be interesting to note what happens to the execution runtime of two-way sequential access when there are frequent insertion-deletion-sequential-access cycles. My guess is that since there would be frequent insertions, that would trigger a vector doubling frequently (which translates to resizing and reallocation, an expensive operation). I guess if the application does frequent random insertions and random deletions and then looks for sequential accesses, DLL can beat vector. On Fri, Nov 23, 2012 at 9:00 AM, Atul Singh atulsingh7...@gmail.com wrote: @Pralay.. can u give a more detail about non synced data structure -- --
Re: [algogeeks] fastest sequential access
assume there are no additional insertions, so we care about only accessing an element. On Sat, Nov 24, 2012 at 12:30 AM, Pralay Biswas pralaybiswas2...@gmail.comwrote: non synced data structure = not thread safe in most prog languages! On Fri, Nov 23, 2012 at 9:00 AM, Atul Singh atulsingh7...@gmail.comwrote: @Pralay.. can u give a more detail about non synced data structure -- -- --
Re: [algogeeks] fastest sequential access
The answer should be a vector because it uses an array to store the elements internally and since an array consists of contiguous memory locations, sequential access will be the fastest. In contrast to SLL or a DLL, the nodes may be at random memory locations and will not provide the fastest sequential access. On Thu, Nov 22, 2012 at 1:12 PM, atul anand atul.87fri...@gmail.com wrote: @shady : as subject says fastest sequential access , then if i am not getting it wrong.we only care of sequential access a value not modifying the linked list. so i guess double linked list would be helpful 1) bcozz it can move in both the direction , so if linked list is sorted then it would be a great help 2) if you want to insert element at the end of linked list then if will be better than vector so i guess it required 1-2 more parameter to decide ,which one to use. On Wed, Nov 21, 2012 at 8:21 PM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- -- -- Cheers Praveen --
Re: [algogeeks] fastest sequential access
singly linked list On Wed, Nov 21, 2012 at 8:21 PM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- --
Re: [algogeeks] fastest sequential access
@shady : as subject says fastest sequential access , then if i am not getting it wrong.we only care of sequential access a value not modifying the linked list. so i guess double linked list would be helpful 1) bcozz it can move in both the direction , so if linked list is sorted then it would be a great help 2) if you want to insert element at the end of linked list then if will be better than vector so i guess it required 1-2 more parameter to decide ,which one to use. On Wed, Nov 21, 2012 at 8:21 PM, shady sinv...@gmail.com wrote: which data structure among the follow has fastest sequential access ? i) vector ii) Singly linked list iii) Doubly linked list it won't be doubly linked list as it involves more pointer manipulations than singly linked list... -- --
