16. 배열 및 연결 리스트 구현하기

1. 배열 구현하기

Array의 특징

1. 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조

2. 정해진 크기가 있음

3. 요소의 추가와 제거 시 다른 요소 이동 필요

4. 배열의 i 번째 요소를 찾는 인덱스 연산이 빠름

5. jdk 클래스 : ArrayList, Vector

2. 연결 리스트(LinkedList) 구현하기

LinkedList 특징

1. 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조

2. 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크(포인터)가 있음

3. 자료가 추가될 때 노드만큼의 메모리를 할당 받고 이전 노드의 링크로 연결함(정해진 크기가 없다)

4. 연결 리스트의 i 번째 요소를 찾는데 걸리는 시간은 요소의 개수에 비례 : O(n)

5. jdk 클래스 : LinkedList