1. 개념

• Java에서의 Linked List는 데이터 요소를 연결하여 구성된 선형 자료구조이다. 각 요소는 데이터와 다음 요소를 가리키는 링크(참조)로 이루어져 있다.
• LinkedList는 더블 링크드 리스트로 구현되어 있으며, 요소의 삽입과 삭제에 효율적이다. 각 요소는 이전 요소와 다음 요소를 가리키는 링크를 유지하기 때문에 삽입과 삭제가 빠르게 이루어진다. 하지만 특정 위치의 요소에 접근하기 위해서는 첫 요소부터 순차적으로 탐색해야 하므로, 임의 접근에는 비효율적이다.
  • ArrayList는 Java에서 제공하는 동적 배열 기반의 자료구조로, 요소를 인덱스를 통해 직접 접근할 수 있기 때문에 임의의 위치에 있는 요소에 빠르게 접근할 수 있다.

2. 메소드

• add(element): 리스트의 끝에 요소를 추가한다.
• add(index, element): 지정한 인덱스에 요소를 추가한다.
• get(index): 지정한 인덱스에 있는 요소를 반환한다.
• remove(index): 지정한 인덱스에 있는 요소를 삭제한다.
• size(): 리스트의 요소 개수를 반환한다.

3. 시간 복잡도

• add(element): O(1)
• add(index, element): O(n) (인덱스를 찾기 위해 순차적으로 탐색)
• get(index): O(n) (인덱스를 찾기 위해 순차적으로 탐색)
• remove(index): O(n) (인덱스를 찾기 위해 순차적으로 탐색)
• size(): O(1)