array vs (array)list vs linkedlist

Array

• 메모리 공간에 할당할 사이즈를 미리 정해놓음
• index로 빠르게 찾을 수 있음 (random access)
• 삽입, 삭제 시 번거로움

(Array)List

• 사이즈 상관없으나 순서는 중요
• index 검색 가능 (random access)
• 삽입, 삭제 시 번거로움

LinkedList

• data, pointer로 구성된 노드
• 단일: 뒤 노드만, 다중: 앞, 뒤 노드를 가리킴
• index 검색 X, 순차검색 시 시간 걸림 (sequential access만 가능)
• 삽입, 삭제 시 용이
• 저장공간에 불연속 단위로 저장됨. 연속적인 기억장소 할당이 필요없지만 노드 접근 시 arraylist 보다는 소요됨
• 참조자를 위한 추가적인 메모리 할당 필요

 

References

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

https://www.nextree.co.kr/p6506/

자료구조: Linked List 대 ArrayList