Arrays Vs Linked Lists

This is a discussion on Arrays Vs Linked Lists within the C++ Programming forums, part of the General Programming Boards category; I have a question, more to gauge the opinions of board users. I have a simple 'relational' database of information ...

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    4

    Arrays Vs Linked Lists

    I have a question, more to gauge the opinions of board users.

    I have a simple 'relational' database of information stored in multiple structs, the information from these structs is stored in separate files. The size of these files will always stay fairly small, not more than 200-250 entries in the largest file. I think this is small enough to hold in memory during the operation of the program, and only write back to file when closing the app. Any new information would be added at the end of the memory rather than part way through (that is, any new structure dumped at the end of the array/linked list).

    In these circumstances, which would be the suggested route for storage, an array of structs, or a linked list of structs? I assume both have advantages and disadvantages, arrays would probably be faster and could be extended with realloc (or whatever the C++ version is), but it would be difficult to remove items in the array as the memory used is contiguous. Linked lists would probably be the slower but offer more flexibility to add/remove items. I am not sure which way to go as both are possible (although the linked lists would be easier I suspect), so if anyone has any strong feelings one way or the other I would be interested in hearing what you have to say.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    Try them both, and learn some first hand experiences about which is best for a given circumstance so that you'll be better able to answer the "which do I use questions" in future.

    In the meantime, read the first couple of responses from Zach here
    linked list versus array
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >not more than 200-250 entries in the largest file
    Then it really doesn't matter what data structure you use unless the entries are HUGE, where the constant shifting of elements in an array will be noticeably expensive. The differences in data structures typically only show up as the number of items grows beyond, for example, 5000. So use whichever is simplest.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    128
    In my case, the one mentioned in the linked article, I opted for using vectors and have been happy with the results.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Doubly linked lists
    By mohanlon in forum C Programming
    Replies: 8
    Last Post: 12-08-2010, 12:01 AM
  2. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 10:32 PM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. Replies: 1
    Last Post: 03-21-2002, 05:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21