algorithm - how to sort data at the time of adding it, not later? -

i new algorithms please forgive me if sounds basic or stupid.

i want know : instead of adding data kind of list , performing sort on list, there method (data structure+algorithm) lets me sort data @ time of adding itself, or put way, inserts data in proper place?

eg: if want add '3' {1,5,6}, instead of adding @ start or end , sorting list, want '3' go after '1' "directly".

thanks

if use binary search tree instead of array, sorting happen "automatically", because it's done insert method of nodes. binary tree sorted, , it's easy traverse. problem when have (more or less) sorted data, tree becomes inbalanced (which red-black-trees , other variations come play).