[자료구조] Array vs List, ArrayList vs LinkedList

배열(Array)

---

→ 크기를 정해서 사용할 수 있는 연속적인 저장 공간

• Array 선언 시 같은 자료형으로 메모리 상에 연속적으로 데이터를 저장할 수 있는 공간이 확보된다.

• 배열 초기화 시 메모리에 할당되어 ArrayList보다 속도가 빠르다.

• 시간 복잡도는 O(1)

• 단점

  • 크기가 고정적이므로 고정된 크기보다 더 많은 데이터를 받으려는 경우 새로운 공간을 만들어 기존 데이터를 복사해주어야 한다.
  • 효율적인 탐색을 위해 Array 데이터 사이에 비는 공간을 없이 만든다면 Array 중간에 데이터를 추가하거나 삭제할 때 빈 공간이 없도록 다수의 데이터를 옮겨야 한다.

 

List(Linear List)

---

→ 데이터의 크기가 정해져 있지 않고, 삽입 삭제가 많이 일어나며, 검색이 적은 경우 유리.

• 항목들은 순서 또는 위치를 가진다.

• 순서가 있는 원소의 모임

• ArrayList, LinkedList는 List 인터페이스를 구현한 Collection 구현체

• 장점

  • 포인터로 다음 데이터의 위치를 가리켜 삽입, 삭제 용이
  • 크기 정해져 있지 않음
  • 메모리 관리 편리

• 단점

  • 검색 성능 안 좋음
  • 포인터로 다음 데이터를 가리키므로 추가적인 메모리 공간 발생

 

ArrayList

---

• 배열 리스트
• 각각 인덱스를 가지고 있어 조회하는데 매우 유리하다.
• 동적으로 크기를 늘릴 수 있다.
• 추가 삭제 시 메모리를 재할당하기 때문에 속도가 배열보다 느리다.

 

LinkedList

---

• 자료의 주소 값으로 노드를 이용해 서로 연결되어 있는 구조다.
• 크기에 제한이 없다.
• 삽입, 삭제 시 이전 값과 다음 값이 수정해 연결하면 되기 때문에 빠르다.
• 원하는 값을 찾기 위해서 최소 한 번은 리스트를 순회해야 하므로 O(n)의 시간 복잡도를 가진다.

 

 

참조

gyoogle.dev/blog/

https://www.geeksforgeeks.org/linked-list-vs-array/

https://www.studytonight.com/data-structures/linked-list-vs-array

https://alwayspr.tistory.com/28