[DS] Array / ArrayList / LinkedList

배열(Array)이란?
동일한 타입을 가진 요소들의 모음

Array의 특징으로는

• 빠른 접근: index를 가지고 있어 빠르게 값을 찾을 수 있음(검색이 빠름)
• 메모리 관리: 연속된 메모리 공간에 데이터들이 들어있으므로 메모리 관리가 효율적임
• 선언할 때 크기와 데이터 타입을 지정해줘야 함
  메모리 공간(heap)에 크기를 미리 할당한다.
  ex) int arr[5];, String arr[10];

Array의 단점으로는

• 중간에 데이터 삽입, 삭제 시 매우 비효율적이다.
  중간에 새로운 데이터를 넣으려면 원래값을 뒤로 밀어내고 해당 index에 덮어씌워야 한다.
  

이를 해결하기 위해 나온 것이 리스트(List)이다. = (ArrayList)

리스트(List)란?
어떤 순서가 있는 데이터의 집합

List는 크기를 정해주지 않아도 되는 가변 배열이라고 생각하면 편하다.

List의 특징으로는

• 크지를 정하지 않아도됨
• 순서가 중요함
• (크기가 정해져 있지 않으므로) 중간에 데이터를 추가/삭제해도 문제 없음
• index를 가지고 있어 검색이 빠름

(▲array와 형태는 같다.)

단점으로는

• 중간에 데이터를 추가, 삭제할 때 시간이 오래걸림
  더하거나 뺄때마다 연산이 추가, 메모리 낭비

연결리스트(LinkedList)란?
불연속적으로 저장된 데이터를 서로 연결한 형태로 구성된 리스트

LinkedList의 특징으로는

• 크기가 가변적임
• 단일, 다중 등 여러가지가 존재함
• 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식
  → 데이터 중간에 삽입/삭제 하더라도 전체를 돌지 않아도됨. 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 됨. 따라서 빠르게 진행됨
  

단점은

• index 없이 연결로 이루어져있기 때문에 n번째 값을 찾아야하는 경우 처음부터 살펴봐야해(순차) 시간이 더 걸림