[자료구조] Array vs ArrayList vs LinkedList

• Array는 index로 빠르게 값을 찾는 것이 가능함
• LinkedList는 데이터의 삽입 및 삭제가 빠름
• ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림
  
  

배열

int arr[10];
String arr[5];

• 선언할 때 크기와 데이터 타입을 지정해야 함
• 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조다.
• 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합
• 중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적
• 특정 인덱스에 새로운 값을 넣어야 한다면 원래 값을 밀어내고 덮어씌워야 함
• 인덱스가 존재하기 때문에 위치를 바로 알 수 있어 검색이 편함

→ 이를 해결하기 위해 나온 것이 List

arrayList

• 배열처럼 크기를 정하지 않아도 됨
• 배열에서 인덱스가 중요하다면 리스트에서는 순서가 중요
• 크기가 정해져있지 않기 때문에 중간에 데이터 추가/삭제 용이
• 인덱스를 가지고 있어서 검색도 빠름
• 그러나 중간에 데이터를 추가/삭제할 때 시간이 오래 걸림
  
  

연결 리스트

• 단일, 다중 등
• 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식
• 단일은 뒤에 노드만 가리키고, 다중은 앞뒤 노드를 모두 가리키는 차이
• 특정 값을 찾는 건 비효율적
• 배열과 arrayList에서는 인덱스가 있어서 검색이 빠르지만 연결 리스트는 순차검색에 있어서는 시간이 더 걸림