첫 번째는 ArrayList이고 두 번째가 LinkedList이다.
ArrayList의 연산방식이다.
ArrayList는 배열과 같다고 했기 때문에 중간이나 앞쪽에 연산이 들어가면 O(N)의 연산이 발생하게 된다.
위 그림처럼 새로운 공간을 끼워넣기 위해서 새롭게 할당 후 저장해야하기 때문이다.
반대로 맨 끝을 지운다던가, 맨 끝에 값을 넣는 것은 딱히 새로운 공간을 만들 필요가 없기 떄문에 O(1)이다.
배열의 큰 특징은 바로 메모리에 저장된 값을 빠르게 불러올 수 있는 것이다.
마찬가지로 ArrayList또한 메모리에 저장된 값을 빠르게 불러올 수 있다. O(1)의 연산
연결리스트는 value : node의 쌍으로 이루어져 있다. 서로 떨어져 있지만 연결점이 있다는 뜻
LinkedList는 노드로 이루어져 있다. 각 노드들이 실로 연결되어 있다고 생각하자.
중간에 하나를 삽입하고싶다. 라면 실을 끊고 삽입한 뒤 이어주면 된다.
즉, 삽입하려는 위치만 알고있다면 O(1)에 끝낼 수 있다는 의미이다.
조회에서는 조금 다른데 인덱스의 위치로 바로 접근하는 것이 아니라 head에서 끝까지 쭉쭉 탐색하다가 원하는 값을 찾으면 return한다.
즉 조회는 O(N)의 시간 복잡도를 가진다는 의미이다.