[CS] Array & ArrayList vs LinkedList

배열(Array)

• 기본 개념

1. 배열이란 같은 데이터 타입의 변수들로 이루어진 자료구조며,자바에서 기본 제공한다.

2. 배열에서의 위치를 가리키는 숫자 index(인덱스)라고 부른다.

3. 배열은 참조 객체이므로 배열을 가리키는 참조 변수는 스택 영역에 할당,이 참조 변수가 가리키고 있는 주소값은 실제 힙 영역에서 생성되는 배열의 주소 값이다.

4. 배열의 index는 0부터 시작하며, 대부분 언어에서도 비슷하다,단 파이썬의 경우배열과 비슷한 list 맨 끝의 원소를 가리키는 인덱스 -1도 존재하는데
   JAVA배열의 인덱스는 0을 포함한 양의 정수만 가질 수 있다.

---

배열(Array) 특징

1. 배열을 선언하는 순간 크기르 지정,선언 이후 변경 X. 즉, 배열 크기가 고정적이다.
2. 배열의 물리 주소와 논리 주소는 동일하다. (덕분에 인덱스 연산자 사용가능)
3. 메모리 공간이 연속적으로 구성된다.
4. 선언할 때 별도의 초기화를 해주지 않는다면 배열에는 배열의 크기만큼 기본값이 채워진다

---

배열 리스트(ArrayList)

• 개념 및 특징

1. 내부적으로 Array을 이용하여 요소를 저장하는 자료구조, 배열의 정적인 크기라는 한계점을 극복하기 위해 생겨난 자료구조이다.
2. 내부적으로 Array을 사용함에도 불구하고 배열 리스트를 선언할 때
   크기 설정을 할 필요가 없고 관리해줄 필요도 없다.
   배열 리스트에서 데이터를 삽입하거나 삭제할 때, 연산 잏 가지고 있어야 할 원소의 개수만큼 딱 맞게 배열의 크기를 조정해준다.
3. 내부적으로 배열을 사용하기 때문에 배열 리스트 또한 물리 공간과 논리 공간이 동일하며 , 그에 따라 인덱스 연산자를 활용할 수 있습니다. 다만, 직접 활용하는 것이 아니라 get 또는 set 메서드를 활용합니다.

---

연결 리스트 (LinkedList)

• 개념 및 특징
  1.배열 리스트는 배열의 정적인 크기라는 한계를 극복하기 위해 탄생했지만 아직 원소를 삽입하거나 삭제할 때 새로운 저자 공간을 재할당하여 시간 복잡도가 O(n)이라는 한계가 있다. 연결 리스트는 그 한계점을 극복하기 위해 탄생한 자료구조이다.

2. 일반적인 자료구조에서 연결 리스트는 단방향 연결 리스트(Singly Linked List)와 양향뱡 연결 리스트(Doubly Linked List)가 존재한다
   자바에서 LInkedList컬렉션 클래스는 는 양뱡향 연결 리스트로 만들어졌다.

---

ArrayList vs LinkedList 비교

-> 이처럼 조회시에는 ArrayList가 우위에 있지만,
삽입/삭제 시에는 LinkedList가 뛰어난 성능을 보여준다.

-> 소량의 데이터를 가지고 사용할 때는 사실 큰 차이가 없지만,
정적인 데이터를 활용하면서 조회가 빈번하다면 ArrayList를 사용하는 것이 좋고 , 동적으로 추가/삭제 요구사항이 빈번하다면 LinkedList를 사용하는 것이 좋다.

결론

• 1. Array는 index로 빠르게 값을 찾는 것이 가능함
• 2. LinkedList는 데이터의 삽입 및 삭제가 빠름
• 3. ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림
• 4. 순차적으로 추가/삭제하는 경우 ArrayList가 LinkedList보다 빠르다.
• 5. 중간 데이터(비 순차적)를 추가/삭제하는 경우 Linked가 ArrayList보다 빠르다.