[Algorithm]그림으로 배우는 알고리즘 제 3장: 자료구조 (4)

그림으로 배우는 알고리즘 제 3장: 자료구조 (4)

29. N번째 요소의 참조가 빠른 것은 배열, 느린 것은 리스트 구조

• N번째 요소 조회
• 예: 나열된 데이터에서 5번째 요소를 조회
  • 배열
    • 요소 번호를 사용해 바로 찾아낼 수 있다. ARRAY[5]
    • 어떠한 요소를 조회하더라도 모든 시간적 비용은 동일하다.
  • 리스트: 1번째 데이터부터 차례대로 끄능ㄹ 따라가야한다.
    • 1번째 요소를 조회한다.
    • 1번째 요소의 끈을 따라 2번째 요소를 조회한다.
    • 2번째 요소의 끈을 따라 3번째 요소를 조회한다.
    • 3번째 요소의 끈을 따라 4번째 요소를 조회한다.
    • 4번째 요소의 끈을 따라 5번째 요소를 조회한다.
    ⇒ 요소의 수가 많을 수록 느려진다.

30. 데이터의 삽입/삭제가 빠른 것은 리스트, 느린 것은 배열

1. 데이터 삽입
   • 새로운 데이터를 순서대로 나열된 데이터 열의 특정 위치에 삽입
     • 배열: 삽입 위치 다음에 존재하는 모든 데이터를 뒤로 이동시켜야 한다(예: 삽입 데이터 뒤에 1,000개 데이터 존재 시 데이터 이동 작업 1,000번 반복).
     • 리스트: 삽입 데이터의 앞뒤 데이터를 연결하고 있는 끈을 잘라 새로운 데이터에 연결하기만 하면 된다(1번 작업)
2. 데이터 삭제
   • 배열: 삭제 데이터 뒤에 있는 모든 데이터를 앞으로 옮겨야한다.
   • 리스트: 제거하고자 하는 데이터의 끈을 자른 후 앞 뒤 데이터를 이어 붙이기만 하면 된다.