List

순서가 있고, 중복을 허용하는 자료구조를 List 라 한다.

• ArrayList 와 LinkedList 는 사용자 입장에서는 기능이 똑같다.
• 내부 구현만 다르므로 성능이 달라질 수 있다.

 

배열 리스트와 연결리스트 성능 비교

	ArrayList	LinkedList
인덱스 조회	O(1)	O(n)
데이터로 검색	O(n)	O(n)
앞에 추가/삭제	O(n)	O(1)
뒤에 추가/삭제	O(1)	O(n)
평균 추가/삭제	O(n)	O(n)

ArrayList 배열리스트

• 배열로 구성
• 인덱스를 통해 추가/삭제할 위치를 O(1) 로 빠르게 찾는다
• 추가 시, 데이터를 전부 한 칸씩 밀어야 해서 O(n)으로 오래 걸린다
• 배열이라서 메모리 상에서 연속적으로 위치하여 CPU 캐시 효율이 좋고 메모리 접근 속도가 빠르다.

LinkedList 연결리스트

• 이중 연결리스트로 구현되어 있다
• LinkedList 는 개별 노드가 앞/뒤 노드의 참조를 관리하므로 메모리 접근 속도가 배열에 비해서는 떨어진다
  • 인덱스를 제공하지 않으므로 순회해야 위치를 찾을 수 있다. O(n) 소요
  • 추가 시, O(n)으로 오래 걸린다
  • 해당 위치 찾는데 O(n) 소요되고, 참조 변경은 O(1) 소요
• 만약, 데이터를 앞쪽에 자주 추가/삭제 할 일이 있다면, 연결 리스트를 고려하자