[알고리즘] 배열과 리스트

💡 대부분의 내용을 Do it! 알고리즘 코딩테스트 with JAVA 강의를 참고하여 정리하였습니다.

배열

배열은 연속 공간에 값이 채워져 있는 형태의 자료구조이다.

배열의 특징

• 인덱스를 사용하여 값에 바로 접근이 가능하다.
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. (연속 공간에 값이 채워져 있는 형태이기 때문)
  • 삽입 및 삭제를 원하는 인덱스 주변에 있는 값을 이동시켜야 한다.
• 배열의 크기는 선언 할 때 지정해야 하고, 한번 선언하면 크기를 늘리거나 줄일 수 없다.

 

리스트

리스트는 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조이다.

리스트의 특징

• 인덱스가 없다. 따라서 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. → 값에 접근하는 속도가 느리다.
• 포인터로 연결되어 있기 때문에 데이터를 삽입하거나 삭제하는 속도가 빠르다.
• 선언할 때 크기를 지정하지 않아도 된다. 크기가 정해져 있지 않고 가변적이다!
• 포인터를 저장할 공간이 필요하므로 배열보다 메모리를 많이 차지한다.

 

배열 vs. 리스트

❓ 코딩테스트에서, 두 자료구조 중에서 어떤 것을 선택해야 적절할까?

• 크기가 고정되어 있을 때
• 접근 횟수가 많은 알고리즘일 때

     → 배열 사용!

 

• 크기가 변할 때, 선언 시 크기를 모를 때
• 삽입과 삭제가 많을 때

     → 리스트(ArrayList, LinkedList) 사용!

 

 

Reference

https://velog.io/@minjung0/Do-it-알고리즘-코딩테스트-자바-정리본-배열과-리스트