Thread: General explanation to common collection data structures

Page 1 of 2 12 LastLast
Results 1 to 10 of 12
  1. #1 General explanation to common collection data structures 
    Registered Member
    Join Date
    Jun 2011
    Posts
    33
    Thanks given
    0
    Thanks received
    14
    Rep Power
    74
    Hi, I'm 't4' from moparisthebest:

    Intro:
    Hello Rune-server! I've made this topic to provide an explanation to certain data structures that are found in many languages and in the Java API. I plan to cover Arrays, ArrayLists, LinkedLists, and HashMaps and plan to discuss the pros and cons in terms of time complexity and memory usage to each type of collection structure along with example usage; but first, I wish to direct your attention to big O notation.

    What is 'Big O'?
    'Big O' notation is a common notation found in mathematics and computer science that describes a function in terms of a more simplistic one. For those who have any background in pre-calculus, think of limits. As you can imagine, this notation can be very handy for visualizing the behavior of potentially complex equations.


    A mathematical example of Big O: f(x) = x + 23 is of linear order (also know as O(x)) because the equation is best fit by f(x) = x.
    A computer science example of Big O: for(int i = 0; i < x; ++i); is of linear order (also know as O(n)) because the program must iterate x times.

    Big O in computer science refers to the amount of operations needed to be done to complete a task. Obviously, a lesser amount of operations generally yields a lesser amount of time spent - which is a good thing!

    Below are common time complexities found in algorithms along with their nomenclature (order from lowest to highest time complexity):
    • * O(1) - constant
      * O(log(n)) - logarithmic
      * O(n^1/c) - fractional power
      * O(n) - linear
      * O(n^c) - polynomial
      * O(c^n) - exponential
      * O(n!) - factorial


    Note: n is the variable and c is a known constant.

    Generally in computer science, one wishes to find and use the algorithm with the lowest time complexity, however as one can imagine, it isn't always possible. One thing to note is that exponential and factorial functions can be EXTREMELY slow - sometimes on the order of 20 minutes, to days, to years depending on how large c is.

    Now that the concepts of efficiency are out of the way, we can now effectively discuss each collection structure...


    Arrays:
    Code:
    int[] array = new int[300];
    This is an array. The above example show an array of integers that is 300 in length. In memory, all 300 integers are allocated next to each other. Integers are 4 bytes in length, thus the above array is utilizing 4 * 300 = 1,200 (1.2kb) bytes of memory. Because of the structure, accessing and modifying elements in the array for a particular index is very trivial. The location in memory of any given index is always array_start_address + (4 * index). In Java, this is all done for you when you use array[idx]. As you could imagine, this makes arrays quite fast for read and write access. Please note, arrays are backed with SIGNED integer indices - this means arrays have a maximum length of 2^31 = 2,147,483,647 elements (Integer.MAX_VALUE). If you have data that is a predictable size and you need quick access to its elements, I would recommend this structure.


    ArrayLists:
    Code:
    ArrayList<Integer> arraylist = new ArrayList<Integer>();
    This is an array list. An array list is quite like an array; under the hood there is an array that is wrapped in a templated (also know as Type Erasure/Java generics) class that provides functionality as dictated by the Java API's Collection interface. The main difference between an array list and an array is the fact that an array list's size is controlled by the structure - this means that the array list will resize itself when it has been filled. Consequentially, this also means that that the structure will allocate more space than it might need, thus 'wasting' resources. This is a good thing, though - especially if you have a set of data with a very variable size. In order to expand it self, the array list must copy all of the existing element to a new location in memory (which costs CPU time). Bear in mind, though - the extra features of an array list aren't free. I would use this in the same context of an array, except only when I cannot predict the size of the data.


    LinkedLists:
    Code:
    LinkedList<Integer> linkedlist = new LinkedList<Integer>();
    Linked lists are very different beasts from arrays. Essentially, they are a series of nodes that reference each other (typically forward) and encapsulate data for that specific location. A good visualization is a chain link:
    [HEAD] -> [NODE 1] -> [NODE 2] -> ... [NODE n]. The nice thing about linked lists is the fact that operations (adding and removing) on the head or tail (depending on implementation) are VERY fast. This is very helpful for more tailored structures such as stacks and queues (which are in fact LinkedLists with specific behaviors). As hinted, I would recommend this structure if you need to quickly access the head or tail of a collection.

    A note about stacks and queues… stacks and queues are a set of standard functionalities usually wrapping a linked list. Stacks are a LIFO (Last In First Out) structure in which data is normally accessed from the head by popping it. What this means is the most recent element of the list is removed and returned to the program. To imagine how a stack looks, think of a stack of dishes – you want to take the top dish off and the top dish is always the one you put on last. Queues are a very similar beast, but they are a FIFO (First In First Out) structure. What this means is the element added first in the list is removed and returned to the program. To imagine this, think of a road toll – there is a line of cars lined up to the booth, each paying in the order that they arrived (assuming no one cuts in line – then you’d have a priority queue hehe).


    HashMaps:
    Code:
    HashMap<String, Integer> hashmap = new HashMap<String, Integer>();
    HashMaps are different than the aforementioned structures, but surprisingly similar. Unlike the other structures, hash maps are templated with two elements (key and value). To make it simple, basically imagine a situation where you'd like to use an array to store your data, but your indices aren't integers; how about Strings! So imagine you want to make "Dog" correspond to the number 24 (key=String, value=Integer). What hashmap does for you is it produces a hash for the key (in this case "Dog") that is an integer value. This now makes it possible for you to index the underlying array by things other than integers. I would suggest using this structure if you have two sets of data that correspond to each other and need to address them quickly.

    One thing to take note is that the hashing function in hash map is not perfect; meaning that the same result can occur on different data. This is known as a collision. To remedy this problem, hash map utilizes chaining – which basically creates a linked list of the keys that map to multiple colliding values. Because of this, lookups on keys that collide can reach O(n) time complexity. Most of the time one doesn’t have to worry about the aforementioned. Please note: just because hash map uses chaining, it doesn’t mean you can put multiple values within the hash table on the same key.


    Side note:
    Generics must be Objects (primitives will not do). Luckily for Java programmers, containers such as Integers are automatically unboxed (as well as their primitives, in this case int, boxed) when needed. This means that the following is completely valid:
    Code:
    ArrayList<Integer> example1 = new ArrayList<Integer>();
    int x = 1;
    example1.add(x);
    
    ArrayList<Long> example2 = new ArrayList<Long>();
    long y = example2.get(0);
    Below is a table of time complexities for all structures covered:
    Time Complexities:



    Conclusion:
    In all, I feel as if I've bastardized and skipped over a lot of nitty-gritty content for a few of the structure (in particular hashmap). If you have any questions (even if it's advice for what to use in a certain scenario) or wish to bring up a point OR even make correction feel free. I hope you've learned something.
    Reply With Quote  
     


  2. #2  
    Registered Member
    Join Date
    Jun 2012
    Posts
    175
    Thanks given
    32
    Thanks received
    47
    Rep Power
    35
    uh this isn't really a snippet (basic java knowledge) but I guess thanks for making this community less idiotic.
    Reply With Quote  
     

  3. #3  
    SERGEANT OF THE MASTER SERGEANTS MOST IMPORTANT PERSON OF EXTREME SERGEANTS TO THE MAX!

    cube's Avatar
    Join Date
    Jun 2007
    Posts
    8,871
    Thanks given
    1,854
    Thanks received
    4,745
    Rep Power
    5000
    [noparse] is the bbcode if you ever feel like fixing it, [list][*] for lists

    Good read though

    Attached image

    Reply With Quote  
     

  4. #4  
    Registered Member
    Join Date
    Nov 2009
    Posts
    3,052
    Thanks given
    112
    Thanks received
    838
    Rep Power
    740
    wrong section, shud be in informative.
    Reply With Quote  
     

  5. Thankful user:


  6. #5  
    Why are you looking here?


    Join Date
    Jul 2012
    Age
    30
    Posts
    3,214
    Thanks given
    830
    Thanks received
    357
    Rep Power
    559
    Really good,thanks
    Reply With Quote  
     

  7. #6  
    Registered Member
    Join Date
    Jun 2011
    Posts
    33
    Thanks given
    0
    Thanks received
    14
    Rep Power
    74
    [QUOTE=S Quare Quxx;3544302][noparse] is the bbcode if you ever feel like fixing it, [list][*] for lists

    Good read though [/QUOTE]

    fixed
    Reply With Quote  
     

  8. Thankful user:


  9. #7  
    Community Veteran

    Exploiter's Avatar
    Join Date
    Oct 2006
    Posts
    956
    Thanks given
    447
    Thanks received
    650
    Rep Power
    5000
    This isn't MoparScape.
    Reply With Quote  
     

  10. #8  
    Registered Member
    Join Date
    Jun 2011
    Posts
    33
    Thanks given
    0
    Thanks received
    14
    Rep Power
    74
    Quote Originally Posted by Purehit View Post
    This isn't MoparScape.
    it was copy and pasted from the original thread, i'll edit it if it annoys you that much.
    Reply With Quote  
     

  11. #9  
    Registered Member
    Join Date
    Aug 2012
    Posts
    28
    Thanks given
    32
    Thanks received
    1
    Rep Power
    10
    Thank you
    Reply With Quote  
     

  12. #10  
    Registered Member
    Join Date
    Jun 2011
    Posts
    33
    Thanks given
    0
    Thanks received
    14
    Rep Power
    74
    Quote Originally Posted by Grundig View Post
    Thank you
    hope it helped!
    Reply With Quote  
     

Page 1 of 2 12 LastLast

Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Similar Threads

  1. Replies: 0
    Last Post: 06-19-2011, 11:34 PM
  2. Statistics Data Collection
    By The Myth in forum Homework
    Replies: 12
    Last Post: 01-06-2010, 11:16 PM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •