What is the major difference between list of tuples and a dictionary?

Question

For example:

a = (1,2,3)
b= (5,6,7)
c=zip(a,b)
[(1,5),(2,6),(3,7)]

A dictionary would have {1:5, 2:6, 3:7}

Answer 1

A list of pairs is not a fundamental data structure. You may choose to use it if you want, but it's just like making a list of lists, or a list of dicts. A list is a data structure meant to store linear data: data that would make sense to write out on a number line, labeling each piece of data 0,1,2,3,...

A dictionary is a hash table, built for O(1) lookup time. A dictionary is also known as a 'map' data structure, because it implements a mapping (like a function), specifically a goes to 1, b goes to 2, and thus dictionaries have an implies direction (in this case, abc->123, not 123->abc). A hash table has no concept of index.

To compare:

myDictionary = {'a':1, 'b':2, 'c':3}
myDictionary['a']

input:a,b,or c           output:1,2,or 3

    e.g. "what does 'a' map to?"

            'a'
             |
             \
              \---> [speedy hash table] 
                          below
                            |
                            | math extracts data
                            |
                  ____________________
                 /                    \
                {             a:1      }
                { b:2              c:3 }
                 \____________________/
                from nebulous magic cloud
                            |
                            \
                             \-----> 1

Now a list:

myList = ['a', 'b', 'c']

in memory: ['a',  'b',  'c']
            0     1     2 <-- indices

>>> myList[1]
'b'

(sidenote: what we actually show above is an array, which is contiguous in memory... a list may not actually be contiguous in memory (and often is not), but it will often 'act' like it is, e.g. it takes O(1) time to look up an element by its index (this is NOT the same as a dictionary index, which is 'a','b','c' in our example; the list indices are always 0,1,2,3,4,... nomatter what data you're storing). To elaborate, we can instantly look up the third item in the list, or the second-to-last item, or the middle item.)

A list of pairs is just a normal list... of pairs:

[('a',1), ('b',2), ('c',3)]

in memory:  [  pair0  ,  pair1  ,  pair2  ]
               0         1         2
elsewhere in memory:
  pair0 --> ('a',1)
elsewhere in memory:
  pair1 --> ('b',2)
  pair2 --> ('c',3)

Finding something in a list will take time proportional to how many items are in the list. It is like finding a needle in a haystack; you have to examine every single piece of hay to find a needle. We use lists for linear ordered data, like graphs of temperature where each element in the list is a unit of time, or holding email messages in some order.

To answer the question you may be trying to ask, "When do I use a list of pairs or a dictionary if I am having trouble deciding between the two?", as a very soft fuzzy rule you will want to use a list of pairs when either

1. you care about the order of your data (e.g. you want to look up which pair comes before or after a pair), or
2. your data cannot be held in a dictionary, e.g. you have duplicate values, like

 

{'a':1, 'a':2, 'b':3, 'c':4}  #this would make no sense to put in a dictionary

myDict = {}
myDict['a'] = 1
myDict['a'] = 2  #overwrites previous mapping!
myDict['b'] = 3
myDict['c'] = 4

>>> myDict
{'a':2, 'b':3, 'c':4}

There may also be times when you need a data structure which is not a list or a dictionary, such as a tree. Sometimes, you may want to use both a list and a dictionary.

Answer 2

A dictionary is a datastructure that is fundamentally based on a hash table, which means that when you look up any particular key, the key is mathematically processed so that it outputs a location in memory where the value is stored. We can then use this location in memory to go directly to where the value is stored. If we want to look up a value in the dictionary based on a key, say 3 in your example, we can go directly to the location of 7 in memory because the 3 hashes to a location in memory.

A list of tuples is an array-like data-structure. This means that if we want to look up a key (referring to the first entry in the tuple), we have to look through every value in the list until we find the matching tuple. In this case, we have to check (1,5), (2,6), and (3,7)! This takes a lot more time, and thus one of the advantages of a dictionary is that looking up values doesn't take much time at all!

Specifically, for a dictionary, searching for a value based on key is O(1) on average, while it is O(n) for a list. There are also differences between the two algorithms in the time that it takes to do access, insertion, and deletion, but many of the specifics of these depend on how the list is implemented under the hood (i.e. is it a singly linked list, doubly linked list, re-sized array, or a skip-list). Check out this page for more details on the differences in speed for various operations across data structures.

Answer 3

c is still a list of tuples, each with its own pair of indices. You access them by subscript, and the elements are not dependent on one another.

c[0][0] is 1
c[0][1] is 5
c[2][1] is 7

In the dictionary, the first element is the index to the second.

d[1] is 5
d[2] is 6
d[3] is 7

The dictionary has no value of 1, 2, or 3.

Does that clear things up for you?