CODEWITHSUNDEEP
data-structures
David Preston
David Preston

Reputation: 2071

Looking for a good definition of a map, and if maps can be implemented using trees

I'm going through some potential interview questions, one of which being can you implement a map or a linked list using a tree.

But even after some time googling I don't have a clear idea exactly what a map is, how it differs from an array or a hash table for example. Could anybody provide a clear description.

Can it, and a linked list be written as a tree?

Upvotes: 2

Views: 1143

Answers (2)

David Weiser
David Weiser

Reputation: 5195

Can it (a map), and a linked list be written as a tree?

Maps are usually represented with arrays. To determine where an entry goes in a map, you need to compute its key. Look here for a better explanation.

Trees (with an undetermined number of nodes) can be implemented using lists (see here for further discussion). Lists are not usually implemented as trees.

I'd encourage you to get this book which is a classic on data structures and will give you alot of really great information.

Upvotes: 0

duffymo
duffymo

Reputation: 308938

A Map, aka Dictionary or associative array, is a data structure that allows you to look up a value using a key.

A Java Map can be implemented as a HashMap or a TreeMap; that suggests that hash map is one possible implementation and yes, you can implement a Map as a tree.

Upvotes: 1

Related Questions