[자료구조] Array vs List

Array

 

• 연속된 메모리 공간에 순차적으로 저장된 선형 자료구조
• 논리적 저장순서와 물리적 저장 순서가 일치
• 따라서 index로 원소에 접근 가능
• 정의와 동시에 길이 지정 (고정길이)

장점

• 인덱스를 통한 검색 용이
• 연속적이여서 메모리 관리 편리

단점

• 크기 변경 불가
• 메모리 낭비 (원소 삭제 후 해당 공간이 빈 상태로 유지됨)

시간복잡도

• 조회 : O(1)
• 삽입/삭제 :
  - 맨 앞 혹은 중간 삽입/삭제 시 : O(n) ⟹ 삽입/삭제 O(1) + 위치조정 O(n)
  - 맨 뒤 삽입/삭제 시 : O(1)

---

List

 

• 연결된 노드의 연속으로 이루어진 선형 자료구조
• 각 노드는 데이터와 다음 노드의 주소를 저장 
• 논리적 저장순서와 물리적 저장 순서가 불일치

장점

• 포인터를 통해 다음 데이터의 위치를 가리키고 있어 삽입/삭제 용이
• 불연속적 데이터 공간 사용으로 메모리 관리 편리

단점

• 검색 성능이 좋지 않음
• 포인터 저장으로 추가적인 메모리 공간 발생

시간복잡도

• 조회 : O(n)
• 삽입/삭제 : 
  - 맨 앞 삽입/삭제 시 : O(1) ⟹ head 위치 알고있음
  - 맨 뒤 혹은 중간 삽입/삭제 시 : O(n)  ⟹ 삽입/삭제 대상 조회 O(n) + 삽입/삭제 O(1)

---

비교결과 

	Array	List
메모리 할당 효율		✔️
데이터 저장 값	✔️
비순차적 추가/삭제		✔️
순차적 추가/삭제	✔️

 

---

reference

 

https://laboputer.github.io/ps/2017/09/05/array-and-list/

https://yongkis.tistory.com/22