LinkedList (2) 썸네일형 리스트형 [JAVA] List - ArrayList, LinkedList 1. ArrayList ArrayList 는 기존의 Vector 를 개선한 것으로 Vector 의 구현원리와 기능적인 측면이 동일하다. ArrayList 는 List 인터페이스를 구현한 클래스이기 때문에 저장된 값의 순서를 유지하고 중복을 허용한다. ArrayList 는 Object 배열을 이용하여 데이터를 순차적으로 저장한다. 입력되는 객체들은 배열에 순서대로 저장되며, 배열의 길이를 넘어가면 더 큰 배열을 새로 생성하여 기존의 값들을 복사한 다음에 값을 저장한다. 값을 삭제하면 삭제된 값의 공간이 빈다. 그러면 나머지 값들이 자리이동을 진행하여 빈 공간을 채운다. ArrayList 나 Vector 와 같이 배열을 이용하여 데이터를 저장하는 자료구조는 인덱스를 사용해 값을 읽어오고 저장하는 작업에는 효.. [DS] Array & Linked List 1. Array 가장 기본적인 자료구조로 메모리 상에 같은 타입의 데이터가 연속적으로 저장되어 있다. 이러한 구조는 첫번째 원소의 위치를 기본 index로 offset을 더하여 이어지는 원소들의 위치를 계산하기에 쉽다. 이때문에 array는 논리적 저장순서와 물리적 저장순서가 일치한다. 따라서 index를 통해서 원소에 랜덤하게 접근이 가능하다. 따라서 검색 time complexity 는 O(1) 이다. 검색과 달리 삭제와 삽입 등의 과정에서는 해당 원소에 접근하여 작업을 완료한 후 빈 공간에 대해서 다른 원소들을 shifting 해줘야 하는 cost가 발생하고 이 경우의 시간 복잡도는 O(N)이 된다. 그렇기 때문에 array 값의 삽입, 삭제의 Time complexity는 O(N) 이다. 2. L.. 이전 1 다음
