배열

• 모든 원소의 주소값을 알고 있다. (임의 접근이 가능)

• 원소를 추가하기 힘들다.(모든 원소의 위치를 바꿔야하고 추가할 주소에 이미 값이 할당되어 있다면 배열 자체의 주소를 옮겨야한다.)

• 원소를 삭제하기 힘들다.(모든 원소의 위치를 바꿔야한다.)

연결 리스트

• 다음 원소의 주소값을 알고 있다.

• 새로운 원소 추가하기 용이하다.(남은 메모리를 할당한 뒤 주소값을 저장하면 된다.)

• 원소를 삭제하기 용이하다.(주소값을 삭제하면 된다.)

• 순차 접근만 가능(10번째 원소를 읽기 위해 1 부터 9개의 원소를 모두 읽어야한다.)

즉, 배열은 읽기가 빠르고, 리스트는 삽입과 삭제가 빠르다.

선택 정렬

• O(n2)