Looks like your insert function is missing an else . You're creating a new node when each time you find an existing node in the map.