1. List

• List는 indexing을 통해 접근 가능한 연속적인 데이터 값을 의미하며, 최소한 다음의 동작들이 가능해야한다.

  1. addAtIndex: 리스트의 특정 인덱스에 주어진 데이터를 저장
  2. removeAtIndex: 리스트의 특정 인덱스에 저장되어 있는 데이터를 삭제
  3. get: 리스트의 특정 인덱스에 저장된 데이터를 반환
  4. isEmpty: 리스트가 비어있는지 그렇지 않은지에 따라 T&F값을 반환
  5. clear: 리스트에 저장된 데이터를 모두 비우고 새로 정의
  6. size: 리스트 내부에 저장되어 있는 데이터의 수를 반환

• List는 추상적 데이터 타입인 만큼, 실제 구현하는 방법은 여럿 있을 수 있다. 이하의 ArrayList와 LinkedList 또한 ADT로, List의 범주에 속하지만 몇몇 특징이 다르다.

2. ArrayList

• Array를 기반으로 구현한 List로, 기본적인 특징과 한계를 Array와 많이 공유한다.

• 데이터가 반드시 연속적으로 저장되어야 하며, index 0부터 시작해야 한다. 그래서 데이터를 지웠을 경우, 뒷 부분에 저장되어있는 데이터를 앞으로 당겨줘야한다. 이를 위해 현재 ArrayList 클래스는 인스턴스로 size를 저장하고 있어야하며, 매번 바꿔줘야한다.

• 데이터를 더할 경우에도 데이터는 반드시 연속적이어야하고, 0부터 시작해야한다. 그래서 데이터를 더할 경우, 효율적인 사용을 위해선 항상 차례대로 데이터를 더해야한다. 예를 들어, 빈 ArrayList면 0번, 그 다음은 1번, 그 다음은 2번에 데이터를 더해야하는 것이다. 필수는 아니지만, 그렇지 않을 경우 새 배열을 선언한 뒤 데이터를 복사해서 저장해야한다.

• 정리하면, 현존하는 데이터의 바로 뒤에 저장하는 addToBack 동작은 대부분 O(1), 저장공간이 가득 찼을 경우에만 O(n)이기에 Amortized 로 계산하면 O(1)*로 효율성을 유지할 수 있다. 그렇지 않고 addToIndex의 경우는 항상 O(n)이다.

• 데이터를 지우는 동작도 비슷하다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xI+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.