개념

List

• 값(value)들을 저장하는 추상자료형(ADT)
• 순서가 있음
• 중복을 허용

언제 쓸까?

Set이나 Map이 더 적절한 상황이 아니라면,
거의 대부분 List를 사용한다고 봐도 된다.

• 객관식 문제의 정답을 List로 관리할 수 있음
• 일반적으로 사용되는 프로그래밍 언어 순위를 순서대로 저장할 수 있음
• DB에서 데이터를 여러 개의 읽어와서 그것을 담을 수 있음

List 구현체

Array list

• 배열(array)을 사용하여 List를 구현
• 연속적인 메모리 공간에 데이터를 저장

Linked list

• 노드를 연결(linked)시키는 형태로 구현
• 노드 각각이 각 포인터를 통해 다음 노드를 가리키는 구조
• 메모리 공간에 띄엄 띄엄 저장
• 확장팩들
  • circular linked list
    • tail이 가리키는 마지막 노드가 첫번째 노드를 가리킴
      (head 라는 포인터를 관리할 필요 없음)
  • doubly linked list
    • 양방향 통행 (앞뒤 이동으로 빨리 접근 가능)
  • circular doubly linked list

Array list vs. Linked list

구현

• 배열(array) 사용 vs. 노드를 연결(linked)

데이터 접근 시간

• 모든 데이터 상수 시간 접근 vs. 위치에 따라 이동 시간 발생

삽입/삭제 시간

• 공통점: 삽입삭제 자체는 상수 시간
• 삽입/삭제 시 데이터 시프트가 필요한 경우, 추가 시간 발생
  vs. 삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생

리스트 크기 확장

• 배열 확장이 필요한 경우, 새로운 배열에 복사하는 추가 시간 발생
  vs. 없음

검색

• 공통점: 최악의 경우, 리스트에 있는 아이템 수 만큼 확인

CPU cache

• CPU cache 이점 활용 vs. 없음