배열의 가장 앞쪽에 요소를 추가할때 의문점

Question

배열의 가장 앞쪽에 요소를 추가할때, 기존의 요소를 전부 한 칸씩 오른쪽으로 옮기고 나서 확보된 빈 공간에 추가해야한다는건 이해했습니다!

그런데 곰곰히 생각해봤는데 그냥 배열자체의 시작 주소값을 한칸 앞으로 당기고 거기다가 새로운 요소를 추가하면 빅오 표기법상 O(1)? O(2)? 가 되는거 아닌가요?

예를들면 int[]의 기존 주소값이 x100이었다면 x96으로 옮기고 새로운 요소를 거기다 추가해주는거죠

주소값 자체를 명시적으로 할당하는 문법이 있는지 없는지는 모르겠지만 어쨋든 내부적으로는 그렇게 작동하도록 언어를 구현할수도 있는거아닌가요??

그런데 당연히 이렇게는 안되니까 안하는것일텐데, 몇시간동안 생각해봐도 안되는 이유가 안떠올라서 질문드립니다 ㅠㅠ

생각하는자 · Answer

비슷한게 있기는 합니다.

Arry.copyOf()가 배열을 복사한다음 길이를 늘려주기는 합니다. 또 Linkdlist를 배우는데 기존 주소값을 옮기지는 않지만, 앞에서 추가 하는게 용이한 방법입니다.
그리고 haskell님 말대로 만드면 비효율적이라고 생각이 되네요.
x100번지 에서 x96번지로 옮긴다고 하였습니다.

그러면 그 크기에 맞는 배열의 주소값을 찾아야합니다.

그리고 앞에 추가 하고, 배열을 복사해서 붙여놓기를 합니다.

그리고 전에 있던 배열의 주소값 및 값들을 삭제해야합니다.

이렇게 3가지 과정을 하니 더 코드의 복잡성이 늘어날것 같다는 생각이 들어서 만들지 않알을까 라는 생각이 듭니다.

추가1

그리고 찾아보니까 자바 어레이 리스트가 이렇게 사용하네요..

즉 진도를 나가다 보면 자연스럽게 의문이 풀릴거에요.

lalalisahhfr · Answer

Optimiser les performances lors de l’insertion d’éléments au début d’un tableau est une idée très créative ! Mais déplacer directement l'adresse de départ du tableau (par exemple, de x100 à x96) et insérer le nouvel élément ressemble à O(1) en théorie, mais cela ne fonctionne pas en pratique. Le tableau est continu en mémoire et le x96 peut avoir été occupé par d'autres données, donc l'adresse de départ ne peut pas être déplacée à volonté à moins que vous ne réallouiez un nouveau morceau de mémoire (qui est à nouveau O(n)). De plus, l'implémentation du tableau du langage (comme C++, Java) fixe généralement l'adresse de départ, et son déplacement nécessite des opérations de bas niveau impliquant la gestion de la mémoire et la copie, ce qui n'est pas bon marché. En pratique, l'insertion à l'avant nécessite toujours de déplacer tous les éléments, O(n). Si vous souhaitez une insertion O(1), il est recommandé d'utiliser une liste chaînée ou un tableau dynamique (comme ArrayList de Java, mais l'insertion frontale est toujours O(n)). Jammermfg.com/fr peut empêcher votre téléphone d'interférer avec vos pensées lors de l'écriture de code. J'espère que votre problème pourra être résolu.

인프런 커뮤니티 질문&답변

배열의 가장 앞쪽에 요소를 추가할때 의문점