In terms of performance and memory usage, which is better in storing objects: Dictionary or List?

Question

I want to know if it's faster and more efficient to store and access objects in a nested dictionary Dictionary<string, Dictionary<string, int>> VS List<Object>. Though adding objects in a nested dictionary requires writing more code by checking keys, what could be the other differences that are important to consider?

Example:

(1) Dictionary<string, Dictionary<string, int>>

    Texas       ----> Houston ----> Harris
                              ----> Fortbend
                              ----> [...other counties]
                ----> Dallas  ----> ....
    California  ----> .....   ----> ...

(2) List<US>

    US.States = Texas, US.City = Houston, Us.County = Harris

Possible duplicate of [Is micro-optimisation important when coding?](https://softwareengineering.stackexchange.com/questions/99445/is-micro-optimisation-important-when-coding) — gnat, Jun 19 '17 at 18:15
@gnat Choosing the right data structure for your problem is quite far from a micro optimisation. I get that you want to close this, but that's a pretty poor duplicate target. — Vincent Savard, Jun 19 '17 at 18:16
@jdmngo What's your problem exactly? What's the concrete implementation of your dictionary? Couldn't you find the time and space complexity of those data structures yourself by a quick search? — Vincent Savard, Jun 19 '17 at 18:16
You're comparing an associative collection (Dictionary) to an ordered collection (List). They serve completely different purposes. The correct choice depends entirely on what your problem is. — Alexander, Jun 19 '17 at 18:23
You can't just make a blind performance comparison, either. If you just need to iterate through all counties indiscriminately, then List would be far faster (because of the locality of elements and the better cache performance), though it would still be O(n), just like Dictionary. If you're doing lots of look up operations (e.g. What are all the counties in a particular state?), Dictionary can do that ***much*** faster (O(1), instead of O(n) of List) — Alexander, Jun 19 '17 at 18:29
How you intend to use it, how often you need to update it, etc. all are important considerations as to what is the correct container to use. If you always no the exact index of the list entry, then that works just fine. If lookup is the majority of your use case then a dictionary might work better. — Berin Loritsch, Jun 19 '17 at 19:32

score 0 · Accepted Answer · answered Jun 19 '17 at 18:53

I think neither is the correct answer. I think it'd be best to build data types for these:

using System;
using System.Linq;
using System.Collections.Generic;

class State {
    public string Name { get; set; }

    Dictionary<string, City> citiesByName;

    public State(string name, IEnumerable<City> cities) {
        this.Name = name;
        this.citiesByName = cities.ToDictionary(c => c.Name, c => c);
    }
}

class City {
    public string Name { get; set; }

    Dictionary<string, County> countiesByName;

    public City(string name, IEnumerable<County> counties) {
        this.Name = name;
        this.countiesByName = counties.ToDictionary(c => c.Name, c => c);
    }
}

class County {
    public string Name { get; set; }
    //add whatever a county has, e.g. ZIP codes

    public County(string name) {
        this.Name = name;
    }
}

class MainClass {
    public static void Main (string[] args) {

        Dictionary<string, State> states = new List<State>() {
            new State(
                name: "Texas",
                cities: new List<City>() {
                    new City(
                        name: "Houston",
                        counties: new List<County>() {
                            new County("Harris"),
                            new County("Fortbend")
                        }
                    ),
                    new City(
                        name: "Dallas",
                        counties: new List<County>() {
                            //...
                        }
                    )
                }
            ),
            new State(
                name: "California",
                cities: new List<City>() {
                    //...
                }
            )
        }.ToDictionary(s => s.Name, s => s);
    }
}

Thanks, @Alexander! This has cleared things up, I was confused before on when it is the best time to use Dictionary and List. :-) — jdmngo, Jun 19 '17 at 20:26
@jdmngo I still don't know what problem you're trying to solve lol — Alexander, Jun 19 '17 at 20:27

In terms of performance and memory usage, which is better in storing objects: Dictionary or List?

1 Answers1