Your reasoning isn't wrong. Deep Neural Networks (DNNs) have a much larger capacity than simpler ML algorithms (excluding NNs) and can easily memorize even a very complex dataset and overfit.
DNNs, however, are so effective because they usually are applied on tasks that are harder, so it's not as easy to overfit. For example an image classifier might be trained on a dataset with millions of images; a task much harder to overfit on.
In cases where this isn't possible (e.g. an image classification task with a couple thousand images), transfer learning is used. You can initialize your weights from a model pre-trained on a large dataset, use its already-trained feature extraction layers and simply fine tune the last layer.
Data augmentation also helps a lot here, which effectively increases size of the training set and discourages the DNN from memorizing the samples. It is so effective that it is used even in large datasets, where it is harder to overfit.
Additionally, DNNs employ several methods to prevent them from overfitting. The most prominent of these is dropout, which is a very effective regularizer. Batch Normalization has also proven an effective regularizer. SGD allows you to explore more parameters than GD, which also is effective against overfitting. Finally, early stopping and parameter norm penalties aren't uncommon in DNNs.